Now that you understand some of the essentials in the underlying implementation of data structures, this section describes some of the key concepts in Java's implementation of collection classes.
Java defines an interface called java.util.List, which is implemented by various collection classes that are responsible for presenting an ordered collection of data. These classes are summarized in Table 11.1.
Table 11.1. List Classes
An ArrayList is similar in concept to an array in that it presents an indexed collection of elements; the distinguishing factor is that an array list does not have a predetermined size and can grow as needed.
A Vector is almost identical to an ArrayList, but it is considered safe to use in multithreaded applications.
A LinkedList, as its name implies, implements the functionality of a linked list; you can add, remove, or get the element at the beginning or end of the list. Furthermore, it permits functionality described in the queue data structure.
A Stack is a variation of a Vector that implements the functionality of the stack data structure.
Although a list is an ordered collection of elements, a set is a collection of unique elements. A set models the mathematical set abstraction. Furthermore, a set can have at most one null value. Two classes implement the Set interface and are.
HashSet: As its name implies a HashSet is a set backed by a hash table, so the data in a hash set is not ordered. It can contain the null value and the order of the elements retrieved from the set, but is not guaranteed to be consistent.
TreeSet: As its name implies a TreeSet is a set backed by a tree, so the data in a TreeSet is ordered. The order of the elements retrieved from a tree set is guaranteed to be in ascending order.
A map is an object that maps keys to values; all keys must be unique. The two main classes that implement the Map interface are
HashMap: The hash map class maintains its collection of keys in a hash table; the order of the keys is in no particular order, and might not be consistent over time.
TreeMap: The tree map class maintains its collection of keys in a tree; the order of the keys is guaranteed to be in ascending natural order.
At any time the keys from a map can be obtained as a class implementing the Set interface.
An Iterator is an interface used for traversing a collection. Each collection class has a method called iterator() that returns an instance of the Iterator class. The Iterator class has three methods:
hasNext(): The hasNext() method returns true if there are more elements in the collection.
next(): The next() method returns the next element in the collection.
remove(): The remove() method removes the last element returned by the iterator.
Although each collection class provides a proprietary mechanism for accessing its data, each supports iterators. This enables you to use any collection class in one consistent mechanism.