How can I implement a List (ordered collection) that keeps an index (i.e. a Map) of its contents?
You can't. Each of the Map and List interfaces define a remove(Object o) method. Each method returns a different type (Map returns an Object while List returns a boolean). Because the compiler doesn't permit overloaded methods that differ by only return type, you cannot create a class that implements both the List and Map interface.
If you need a Map that maintains insertion order, see the LinkedHashMap added in Java 1.4.