Collections

A Collection is a data structure that can hold references to a group of objects, usually all of the same type. For example: A List contains objects in a specific order, much like an array. A Set contains no duplicates. A Map associates keys to values, e.g., id numbers to names.

In Java, Collection is an interface defining the behaviors of a collection,  including typical operations such as

List, Set and Map are defined as sub-interfaces of Collection. These interfaces are implemented by concrete classes such as ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, etc.

It is a common practice in Java programming to use a reference variable of an interface type to refer to an object of a concrete class that implements the interface. Typically, a collection is declared by including the type of element it contains within <...>, which is using Java's generics notation. For example:

// declare list to be a collection of Strings
Collection<String> list;
// initialize list to a concrete class that implements Collection
list = new ArrayList<String>();

The concrete class will determine how efficient these operations will be.

Preliminaries: Wrapper Classes and Autoboxing

Java does not support collections of primitive types. However, each primitive type has a corresponding wrapper class, e.g., Integer for ints and Double for doubles. Each wrapper class enables you to manipulate primitive type values as objects.

The conversion between primitive types and wrapper classes is mostly automatic, due to autoboxing and unboxing. Autoboxing converts a value of a primitive type to the corresponding wrapper class. Unboxing converts an object of a wrapper class to the corresponding primitive type.

Double dbox = Math.sqrt(2);  // autoboxing
double d = 1.0 / dbox;       // unboxing
The conversion is mostly transparent, but there are some bug-producing cases (e.g., using == on two different Integer objects is false, no matter their values).
Integer i1 = 42;
Integer i2 = 42;
System.out.println(i1 == i2);  // prints false

Examples

All the example programs mentioned below are in chapter16.zip.

The CollectionTest program illustrates several Collection and List methods. Alternatives for looping through the elements of a List and for removing values have been added to the program from the book. You loop through the elements of a collection using a for-each loop, or by explicitly obtaining an Iterator object and using the Iterator's hasNext and next methods. Note: The book's removeColors method is bad programming for two reasons: one is that looping through the whole collection is inefficient (what if there are 1,000,000 elements and only one element is to be removed) and the other is that the remove method of Iterator might not be supported (see the documentation)

The ListTest program illustrates additional list operators, including a ListIterator, which in addition to  hasNext and next methods also provides hasPrevious and previous methods.

The Collections class contains many static methods that are useful for collections. The Sort1 program illustrates the use of Collections.sort to sort a collection in either ascending or descending order. The Sort3 program, which uses the Time2 and TimeComparator classes, illustrates how to write objects that can compare themselves. One way is shown by Time2 implementing the Comparable interface, which consists of a compareTo method for Time2 objects within the Time2 class. The other way is to implement the Comparator interface, which consists of a compare method for Time2 objects within the TimeComparator class. Typically, Comparable is used for the "natural" ordering, and Comparator is used for alternative orderings, though in this case, the two implementations should result in the same orderings even though they are computed differently. It is also possible to have one class implement both the Comparable and Comparator interfaces and provide different ways to compare its objects. The two versions of the Collections.sort methods can be used to sort objects in a collection using the compareTo and the compare methods.

The Set interface is like List, but is intended for collections with no duplicate elements. The SetTest program illustrates HashSet, which implements Set using a hash table. The SortedSetTest program illustrates TreeSet, which implements Set using a binary search tree. TreeSet also includes methods for selecting a range of values (e.g., headSet and tailSet) and a single value (e.g., first and last, also look at ceiling, higher, floor and lower).

The Map interface specifies methods for associating keys with values. The WordTypeCount program illustrates several of these methods. Map<String,Integer> declares a mapping from Strings to ints. HashMap and TreeMap are two of the concrete classes that implement the Map interface. HashMap uses a hash table, while TreeMap uses a binary search tree. The WordTypeCount program inserts the tokens from the user into the Map, keeping track of the number of times each word appears.

The PropertiesTest program illustrates the Properties class, which is a subclass of Map. This class is especially useful for writing/reading property lists (such as user settings) to/from files.