A DESCRIPTION OF THE REQUEST :
There is no implementation of a collection class that combines the concepts of a Map and a List. A ListMap class should be created that maintains the original order of key/value entries added to the map so that iteration over keys or values would happen in that order.

JUSTIFICATION :
Currently there are several implementations of Map interfaces and List interfaces and both have sorting capability using comparators. List can maintain the original order of objects added to the collection when doing an iteration. However, Set and Map can only guarantee order of iteration based on comparators. While you could always wrap objects and add attributes to hold a sequence order and write a custom comparator, this is alot of code for a simple capability. Also, it is nice to have a Map capability on an ArrayList so that you can index the ordered list using a special key.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Sample implementation:

package java.util;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * An implementation of a Map that guarantees original order of keys as they
 * are added to the Map.
 */
public class ListMap<K,V> extends AbstractMap<K,V> implements Cloneable, Serializable
{
  /**
   * Version id for Serializable
   */
  private static final long serialVersionUID = -6678626872881862678L;

  protected ListSet<Entry<K,V>> entrySet = new ListSet<Entry<K,V>>();

  /**
   * Internal class to implement a Set that uses an ArrayList to keep original
   * order of keys
   */
  static protected class ListSet<T> extends AbstractSet<T>
  {
    protected ArrayList<T> entryList = new ArrayList<T>();
    
    public ListSet()
    {
      super();
    }
    
    public Iterator<T> iterator()
    {
      return entryList.iterator();
    }
    
    public int size()
    {
      return entryList.size();
    }
    
    public boolean add(T o)
    {
      boolean retVal = false;
      if (!entryList.contains(o))
      {
        retVal = entryList.add(o);
      }
      return retVal;
    }
    
    /**
     * Internal method to put the entry by looking for existing entry and
     * returning it or add new entry.
     */
    public T putEntry(T entry)
    {
      T retVal = entry;
      int index = entryList.indexOf(entry);
      if (index >= 0)
      {
        retVal = entryList.get(index);
      }
      else
      {
        entryList.add(entry);
      }
      
      return retVal;
    }
  }

  /**
   * Internal class to implement the Map.Entry interface that holds the entry
   * objects in the Map.
   */
  static protected class ListEntry<K,V> implements Entry<K,V>
  {
    protected K key = null;
    protected V value = null;
    
    public ListEntry(K pKey)
    {
      key = pKey;
    }
    
    public K getKey()
    {
      return key;
    }

    public V getValue()
    {
      return value;
    }

    public V setValue(V pValue)
    {
      V prevValue = value;
      value = pValue;
      return prevValue;
    }

    public boolean equals(Object o)
    {
      boolean retVal = false;
      Object otherKey = o;

      if (o instanceof ListEntry)
      {
        otherKey = ((ListEntry)o).getKey();
      }

      retVal = (key == null && otherKey == null) ||
               (key != null && key.equals(otherKey));

      return retVal;
    }

    public int hashCode()
    {
      return (key != null) ? key.hashCode() : 0;
    }
  }

  /**
   * Default constructor
   */
  public ListMap()
  {
    super();
  }

  /**
   * Implement put to allow this Map to be writable. If the key represents a new
   * element in the Map, then it is added to the end of the Map. Otherwise, the
   * existing entry is updated with the new value.
   *
   * @param key the key of the value to set.
   * @param value the value to set.
   * @return the previous value set at this key (null indicates new or previous
   * value was null).
   */
  public V put(K key, V value)
  {
    Map.Entry<K,V> entry = new ListEntry<K,V>(key);
    
    entry = entrySet.putEntry(entry);
    
    return entry.setValue(value);
  }

  /**
   * Return the Set that contains a list of Map.Entry objects for this Map.
   */
  public Set<Entry<K,V>> entrySet()
  {
    return entrySet;
  }
}