List vs Map/Dictionary

There are cases where you use a List, be it array or linked. There are other situations where you use a Map, in java, or Dictionary or something else similar.

Why would yo开发者_开发问答u ever use a List when a Map gives exactly the same functionality, that is access by an index (in this case integer...).

Shouldn't the Map always be prefered to the list? What do I miss here?

---

Duplicate of this question.

But to give an answer specific to your question, consider the efficiency of using a Map structure to maintain collection indexed by integer.

Consider this code:

public void add(Map map, Object o) {
    int index = map.size();
    map.put(index, o);
}

public static void add(List list, Object o) {
    list.add(o);
}

Now take a look at what the compiler turns it into (using javap or open the class file in IDE like Eclipse):

public void add(java.util.Map map, java.lang.Object o);
     0  aload_1 [map]
     1  invokeinterface java.util.Map.size() : int [16] [nargs: 1]
     6  istore_3 [index]
     7  aload_1 [map]
     8  iload_3 [index]
     9  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [22]
    12  aload_2 [o]
    13  invokeinterface java.util.Map.put(java.lang.Object, java.lang.Object) : java.lang.Object [28] [nargs: 3]
    18  pop
    19  return
      Line numbers:
        [pc: 0, line: 8]
        [pc: 7, line: 9]
        [pc: 19, line: 10]
      Local variable table:
        [pc: 0, pc: 20] local: this index: 0 type: MapListTest
        [pc: 0, pc: 20] local: map index: 1 type: java.util.Map
        [pc: 0, pc: 20] local: o index: 2 type: java.lang.Object
        [pc: 7, pc: 20] local: index index: 3 type: int

  // Method descriptor #38 (Ljava/util/List;Ljava/lang/Object;)V
  // Stack: 2, Locals: 2
  public static void add(java.util.List list, java.lang.Object o);
    0  aload_0 [list]
    1  aload_1 [o]
    2  invokeinterface java.util.List.add(java.lang.Object) : boolean [39] [nargs: 2]
    7  pop
    8  return
      Line numbers:
        [pc: 0, line: 13]
        [pc: 8, line: 14]
      Local variable table:
        [pc: 0, pc: 9] local: list index: 0 type: java.util.List
        [pc: 0, pc: 9] local: o index: 1 type: java.lang.Object

There's a good bit less work being done to maintain a collection as a List than a Map. So List is a more efficient data structure for the purpose.

---

Accessing a Map by an index is an unusual use case in my opinion. Accessing a Map by its key is a far more common use case.

In my opinion, if I need to look up an object in a structure using a well defined key, I'll use a Map. If I'll generally be wanting to iterate over the collection of objects, I'll use a List.

Using a Map where the key value is actually an index seems like you're using the wrong data structure to me.

---

The differences between Map<Integer, E> and List<E> are these, from a semantic viewpoint:

• The list contains all indices from 0 to list.size(), while the map can contain any indexes (even negative ones), with large holes.
• When adding elements to a list without an index, you automatically get a new index. For maps, there is no such operation. (You could implement it on SortedMaps easily, though.)
• When adding elements with index or removing them, in a list the subsequent indexes shift by one. In a map, there is no such shifting (and added elements may replace existing ones).

That said, I once created a sparse list (mostly containing null) backed by a HashMap<Integer, E> - but there I disabled structural modifications (similar to Arrays.asList).