Choosing an implementation
By now you should understand that there are really only three container components: Map, List, and Set, but more than one implementation of each interface. If you need to use the functionality offered by a particular interface, how do you decide which implementation to use?
To understand the answer, you must be aware that each different implementation has its own features, strengths, and weaknesses. For example, you can see in the diagram that the “feature” of Hashtable, Vector, and Stack is that they are legacy classes, so that old code doesn’t break. On the other hand, it’s best if you don’t use those for new code.
The distinction between the other containers often comes down to what they are “backed by”; that is, the data structures that physically implement your desired interface. This means that, for example, ArrayList and LinkedList implement the List interface, so the basic operations are the same regardless of which one you use. However, ArrayList is backed by an array, and LinkedList is implemented in the usual way for a doubly linked list, as individual objects each containing data along with references to the previous and next elements in the list. Because of this, if you want to do many insertions and removals in the middle of a list, a LinkedList is the appropriate choice. (LinkedList also has additional functionality that is established in AbstractSequentialList.) If not, an ArrayList is typically faster.
As another example, a Set can be implemented as either a TreeSet, a HashSet, or a LinkedHashSet. Each of these have different behaviors: HashSet is for typical use and provides raw speed on lookup, LinkedHashSet keeps pairs in insertion order, and TreeSet is backed by TreeMap and is designed to produce a constantly sorted set. The idea is that you can choose the implementation based on the behavior you need. Most of the time, the HashSet is all that’s necessary and should be your default choice of Set.
