The Java Collections Framework

The Java collections framework consists of interfaces that specify various types of generic maps and collections, classes that provide standard implementations of these interfaces, iterators, and generic algorithms:

Documentation

Complete documentation for the Java Collections Framework (JCF) is online at:

http://java.sun.com/j2se/1.4.2/docs/guide/collections/index.html

The same documentation is probably on your computer if you downloaded the documentation with the SDK. For example, on my computer the JCF documentation is located at:

C:\Program Files\j2sdk1.4.2_03\docs\guide\collections\index.html

The index page contains links to the JCF APIs and a JCF tutorial. Please study all of this material plus the overview.

Interfaces

Collections are specified by the following properties:

Duplicates = are duplicate elements allowed?
Ordered = can users insert elements at specified positions?
Modifiable = can users add and remove elements?
Access = random, sequential, associative, unspecified

Access

Access may be:

positional
sequential
random
associative
unspecified

Duplicates may be permitted, not permitted, or unspecified (?)

Order may be:

insertion order
natural or logical order
ordered by hash code or some other internal mechanism
unspecified

Here's a summary:

			Interfaces
Property	Collection	Set	SortedSet	List	Map	SortedMap
Duplicates?	unspecified	no	no	yes	no	no
Ordering	unspecified	unspecified	logical	insertion	unspecified	logical
Modifiable?	optional	optional	optional	optional	optional	optional
Access	positional	positional	positional	positional	associative	associative

Multi-Set

A collection implements the interface:

public interface Collection {
// Basic Operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(Object element); // Optional
boolean remove(Object element); // Optional
Iterator iterator();

// Bulk Operations
boolean containsAll(Collection c);
boolean addAll(Collection c); // Optional
boolean removeAll(Collection c); // Optional
boolean retainAll(Collection c); // Optional
void clear(); // Optional

// Array Operations
Object[] toArray();
Object[] toArray(Object a[]);

// Overrides
boolean equals(Object o);
int hashCode();
}

Iterators

An iterator is an object that points at elements in a collection. An iterator divides the collection into the elements it has "seen" and the elements that it has not seen. An iterator points at the next unseen element:

The Java Collections Framework includes the Iterator interface:

interface Iterator {
boolean hasNext(); // = true if more unseen elements
Object next(); // = see next unseen element
void remove(); // removes last seen element
}

Here's a typical example of iterating through a collection:

Collection book = new TreeSet();
book.add("This");
book.add("is");
book.add("the");
book.add("end");
// etc.
Iterator p = book.iterator();
while(p.hasNext()) {
String word = (String)p.next();
System.out.println(word);
}

Here's the output produced. Notice that the order of elements has changed:

This
end
is
the

Be careful, iterators can become obsolete. The following code:

p = book.iterator();
Iterator q = book.iterator();
p.next();
p.remove();
System.out.println(q.next());

produces the error:

Exception in thread "main" java.util.ConcurrentModificationException

For this reason Java iterators are sometimes called fail-fast iterators.

Sets

The Set interface extends the Collection interface, but adds no new methods:

interface Set extends Collection { }

Instead, restrictions are placed on the implementations of the methods. For example, the add method, if it's implemented, ignores attempts to add duplicate elements.

A set uses the equals predicate of its elements to determine if two elements are the same (i.e., logical equality).

A set uses the hash code to determine the position of an element. For this reason it's important to make sure that to elements that are logically unequal have unequal hash codes.

Sorted sets are sets whose elements must be comparables. In this case elements are placed in the set according to the order given by the compareTo method.

Example

Study the following canonical class declaration:

class Cell implements Comparable {
private int val;
public Cell(int val) { this.val = val; }
public Cell() { this(0); }
public String toString() {
return "Cell[" + val + "]";
}
public int getVal() { return val; }
public boolean equals(Object o) {
if (o == null) return false;
Class c1 = getClass();
Class c2 = o.getClass();
if (!c1.equals(c2)) return false;
Cell other = (Cell)o;
return val == other.val;
}
public int hashCode() {
return toString().hashCode();
}
public int compareTo(Object o) {
if (o == null) throw new ClassCastException();
Class c1 = getClass();
Class c2 = o.getClass();
if (!c1.equals(c2)) throw new ClassCastException();
Cell other = (Cell)o;
if (equals(other)) return 0;
if (val < other.val) return -1; else return 1;
}
}

In addition, we declare a comparator for Cell:

class CellComparator implements Comparator {
public int compare(Object o1, Object o2) {
if (o1 == null) {
if (o2 == null) return 0;
throw new ClassCastException();
}
Class c1 = o1.getClass();
Class c2 = o2.getClass();
Class c3 = (new Cell()).getClass();
if (!c1.equals(c2) || !c1.equals(c3)) {
throw new ClassCastException();
}
int arg1 = ((Cell)o1).getVal();
int arg2 = ((Cell)o2).getVal();
if (arg1 < arg2) return 1;
if (arg2 < arg1) return -1;
return 0;
}
public boolean equals(Object o) {
return o == this; // for now
}
}

Hash sets (backed by open hash tables) and Linked hash tables (backed by open hash tables with linked elements) implement Sets. Tree sets (backed by red-black trees) implement sorted sets:

Set set1 = new HashSet();
Set set2 = new LinkedHashSet();
SortedSet set3 = new TreeSet();
SortedSet set4 = new TreeSet(new CellComparator());

Let's create some cells:

Cell[] cell = new Cell[4];
cell[0] = new Cell(22);
cell[1] = new Cell(3);
cell[2] = new Cell(42);
cell[3] = new Cell(-1);

Next, we add these cells to our sets:

for(int i = 0; i < 4; i++) {
set1.add(cell[i]);
set2.add(cell[i]);
set3.add(cell[i]);
set4.add(cell[i]);
}

Displaying the sets:

System.out.println(set1);
System.out.println(set2);
System.out.println(set3);
System.out.println(set4);

produces the output:

[Cell[22], Cell[42], Cell[3], Cell[-1]]
[Cell[22], Cell[3], Cell[42], Cell[-1]]
[Cell[-1], Cell[3], Cell[22], Cell[42]]
[Cell[42], Cell[22], Cell[3], Cell[-1]]

Notice that the order of elements in set3 is determined by their natural order, i.e., the order given by the compareTo method. The order of elements in set4 is determined by the comaparator passed to the constructor, which is the reverse of the natural order. The order of elements in set2 is the insertion order. Finally, the order of elements in set1 is determined by the hash codes.

Sets ignore attempts to add duplicate elements. For example, executing the commands:

set1.add(new Cell(3));
System.out.println(set1);

produces the output:

[Cell[22], Cell[42], Cell[3], Cell[-1]]

Assume blobs aren't comparable:

class Blob { }

We can add blobs to sets, but not to sorted sets. Executing the code:

set1.add(new Blob());
set2.add(new Blob());
// set3.add(new Blob()); throws an exception
System.out.println(set1);
System.out.println(set2);

produces the output:

[Cell[22], Cell[42], Cell[3], Blob@93dee9, Cell[-1]]
[Cell[22], Cell[3], Cell[42], Cell[-1], Blob@fabe9]

Notice that cells are not mutable. Assume we provide a setVal() method:

class Cell implements Comparable {
private int val;
public void setVal(int val) { this.val = val; }
// etc.
}

After we add cells to our sets, we mutate cell[3]'s value from –1 to 500:

cell[3].setVal(500);

Notice that the order of the sets no longer follows the rules described earlier:

[Cell[22], Cell[42], Cell[3], Cell[500]]
[Cell[22], Cell[3], Cell[42], Cell[500]]
[Cell[500], Cell[3], Cell[22], Cell[42]]
[Cell[42], Cell[22], Cell[3], Cell[500]]

Lists

The list interface adds random access methods:

interface List extends Collection {
int indexOf(Object o); // = -1 if o not an element
Object get(int i); // get element at position i
void add(int i, Object o); // adds o at position i
void remove(int i); // remove element at position i
ListIterator listIterator(); // get a 2-way iterator
// etc.
}

Example

Array lists and linked lists are the major implementations of the interface:

List list1 = new ArrayList();
List list2 = new LinkedList();
List list3 = new Vector();
List list4 = new LinkedList();

The following list of planets contain duplicates:

String[] vals2 =
{"Mercury", "Venus", "Earth", "Mars", "Jupiter", "Venus"};

The order of a list is always the insertion order:

for(int i = 0; i < vals2.length; i++) {
list1.add(vals2[i]);
list2.add(vals2[i]);
list3.add(vals2[i]);
}

We can verify this by printing the lists:

System.out.println(list1);
System.out.println(list2);
System.out.println(list3);

which produces the result:

[Mercury, Venus, Earth, Mars, Jupiter, Venus]
[Mercury, Venus, Earth, Mars, Jupiter, Venus]
[Mercury, Venus, Earth, Mars, Jupiter, Venus]

Implementations

In the following table we assume:

n = number of elements in the collection
i = position
d = min(i, n – i) = distance to nearest end
o = object to be added or removed
O(f(n))_a = amortized complexity = f(n)

Generic Algorithms

The Collections class provides several mildly useful static methods for manipulating lists. For example, executing the commands:

Collections.sort(list3);
Collections.shuffle(list2);
Collections.rotate(list1, 3);

produces the output:

list1 = [Mars, Jupiter, Venus, Mercury, Venus, Earth]
list2 = [Mercury, Jupiter, Mars, Earth, Venus, Venus]
list3 = [Earth, Jupiter, Mars, Mercury, Venus, Venus]

Executing the commands:

Collections.replaceAll(list2, "Venus", "Pluto");
Collections.reverse(list1);

produces the result:

list1 = [Mars, Jupiter, Venus, Mercury, Venus, Earth]
list2 = [Mercury, Jupiter, Mars, Earth, Venus, Venus]
list3 = [Earth, Jupiter, Mars, Mercury, Venus, Venus]

The collections class allows us to create new views of existing collections:

List view1 = Collections.unmodifiableList(list1);
// view1.add("Claire"); this fails