-
JDK 1.2 introduced support for Collections, also known as “container classes.” There are two basic interfaces that extend Collection in different directions, Set and List.
-
A List is a collection that has an order associated with its elements. That order is the order in which the elements were added to the collection. There does not need to be any logical relationship between elements.
-
The List interface is implemented by two concrete classes, LinkedList and ArrayList. LinkedList is a doubly linked list. The time to access elements depends on where they are in the list, but there is no overhead to growing or shrinking the collection. ArrayList is a list stored as an array. It provides quick access to any element, but it is expensive to grow or shrink the array.
-
A Set is a collection that never has any duplicate objects. Unlike a mathematical set, the objects may come in some order, but it is not the order in which you add them to the collection.
-
The Set interface is implemented by two concrete classes, HashSet and TreeSet. HashSet is a set backed by hash table. It is quick to add and retrieve elements, but the elements are in no particular order. TreeSet is a set backed by a red/black tree. The elements are kept in sorted order, so it costs more to insert them.
-
JDK 1.5 introduced support for generic classes, interfaces, and methods. The collection classes are the main user of these.
We saw the helper class for collections, and there is a similar one for arrays. These support some very useful sorting and extraction utilities for collections and arrays. It's possible to flatten any collection into an array, although you'll probably never need to.
All of these features together make up the Collections Framework, and there is one additional piece to it, which we will review in the next section. So far, all these data structures have dealt with individual objects. There is another interface backed by concrete classes that you can use to process pairs of key/values together. This is the Map interface.