11.2 Collections

The Collection interface specifies the contract that all collections should implement. Some of the operations in the interface are optional, meaning that a collection may choose to provide a stub implementation of such an operation that throws an UnsupportedOperationException when invoked. The implementations of collections from the java.util package support all the optional operations in the Collection interface (see Figure 11.2 and Table 11.2).

Many of the methods return a boolean value to indicate whether the collection was modified as a result of the operation.

Basic Operations

The basic operations are used to query a collection about its contents and allow elements to be added and removed from a collection.

int size()
boolean isEmpty()
boolean contains(Object element)
boolean add(Object element)        // Optional
boolean remove(Object element)     // Optional

Bulk Operations

These operations perform on a collection as a single unit.

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

Array Operations

These operations convert collections to arrays.

Object[] toArray()
Object[] toArray(Object a[])

Iterators

A collection provides an iterator which allows sequential access to the elements of a collection. An iterator can be obtained by calling the following method of the Collection interface:

Iterator iterator()

The Iterator interface is defined as follows:

boolean hasNext()

Object next()

Object remove()

After obtaining the iterator for a collection, the methods provided by the Iterator interface can be used to systematically traverse the elements of the underlying collection one by one. Example 11.1 illustrates the use of an iterator.

Example 11.1 Using an Iterator

import java.util.*;

public class IteratorUsage {
    public static void main(String[] args) {

        // (1) Create a list of Integers.
        Collection intList = new ArrayList();
        int[] values = { 9, 11, -4, 1, 13, 99, 1, 0 };
        for (int i = 0; i < values.length; i++)
             intList.add(new Integer(values[i]));

        System.out.println("Before: " + intList);         // (2)

        Iterator interator = intList.iterator();          // (3) Get an iterator.
        while (interator.hasNext()) {                     // (4) Loop
            Integer element = (Integer) interator.next(); // (5) The next element
            int value = element.intValue();
            if (value < 1 || value > 10) // (6) Remove the element if
                interator.remove();      //     its value is not between 1 and 10.
        }

        System.out.println("After:  " + intList);    // (7)
    }
}

Output from the program:

Before: [9, 11, -4, 1, 13, 99, 1, 0]
After:  [9, 1, 1]

Example 11.1 creates a list of integers and then removes from the list all integers that are not between 1 and 10, inclusive. The example uses an ArrayList for the list of integers. Since int values are not objects, they cannot be inserted into a collection. Therefore, each int value must be wrapped in an Integer object, which is then added to the collection.

The Collection interface allows arbitrary objects to be added to a collection. When inserting an element, its reference is upcasted to the type Object. On retrieval, it might be necessary to downcast the reference value of the object to invoke subtype-specific behavior.

The concrete collection classes override the toString() method to provide a textual representation of their contents. The standard textual representation generated by the toString() method for a collection is

[element₁, element₂, ..., element_n]

where each element_i is the textual representation generated by the toString() method of the individual elements in the collection. At (2) and at (7) the toString() method of the collection class is used implicitly to generate a textual representation for the collection.

In Example 11.1, an iterator is obtained at (3) and used in the loop at (4) to traverse all the elements in the integer list. The reference value of the next element is downcast at (5). It might be advisable to use the instanceof operator to check the type of a retrieved object before attempting to downcast the reference. We have not done so in this simple example because we know that the collection is guaranteed to hold only Integers.

Note that the methods are invoked on the iterator, not the underlying collection. The three methods of the iterator should be used in step inside a loop, as shown in Example 11.1.

The majority of the iterators provided in the java.util package are said to be fail-fast. When an iterator has already been obtained, structurally modifying the underlying collection by other means will invalidate the iterator. Subsequent use of this iterator will throw a ConcurrentModificationException. The remove() method of an iterator is the only recommended way to delete elements from the underlying collection during traversal with an iterator.

The order in which the iterator will return the elements from an underlying collection depends on the traversal order supported by the collection. For example, an iterator for a list will traverse the elements in the sequential order they have in the list, whereas the traversal order for the elements in an ordinary set is not predetermined. An iterator for a sorted collection will make the elements available in a given sorted order. Traversal order will be discussed together with the individual concrete classes.