11.8 Working with Collections

The collection implementations can be augmented with the following functionality:

• thread-safety

• collection immutability

The collection implementation classes, except for Vector and Hashtable, are not thread-safe, that is, their integrity can be jeopardized by concurrent access. A situation might also demand that a collection be immutable. Java provides solutions to both these requirements through decorators. A decorator object wraps around a collection, modifying the behavior of the collection.

Instead of providing public decorator classes, Java provides static factory methods that return appropriately decorated collection instances. In this regard, these decorators are known as anonymous implementations. In addition to being a repository of useful utility methods, the Collections class provides decorators for making collections and maps thread-safe and unmodifiable.

Synchronized Collection Decorators

The following static factory methods from the Collections class can be utilized to create decorators that provide thread-safety for collections:

static Collection synchronizedCollection(Collection c)
static List       synchronizedList(List list)
static Map        synchronizedMap(Map m)
static Set        synchronizedSet(Set s)
static SortedMap  synchronizedSortedMap(SortedMap m)
static SortedSet  synchronizedSortedSet(SortedSet s)

All threads must access the underlying collection through the synchronized view, otherwise, non-deterministic behavior may occur.

// Create a synchronized decorator.
Collection syncDecorator = Collections.synchronizedCollection(nonsyncCollection);

In addition, for traversing a synchronized collection, the code for traversing the collection must be synchronized on the decorator:

// Each thread can only traverse when synchronized on the decorator.
synchronized(syncDecorator) {
    for (Iterator iterator = syncDecorator.iterator(); iterator.hasNext();)
        doSomething(iterator.next());
}

Unmodifiable Collection Decorators

The following static factory methods from the Collections class create views that provide read-only access to the underlying collection:

static Collection unmodifiableCollection(Collection c)
static List       unmodifiableList(List list)
static Map        unmodifiableMap(Map m)
static Set        unmodifiableSet(Set s)
static SortedMap  unmodifiableSortedMap(SortedMap m)
static SortedSet  unmodifiableSortedSet(SortedSet s)

The unmodifiable views intercept all calls that can modify the underlying collection, and throw an UnsupportedOperationException. If the view is a collection, then this restriction applies for any iterator of this collection. In the case of a map, the restriction also applies to any collections created from this map.

Sorting Collections

The Collections class provides two static methods for sorting lists.

static void sort(List list)
static void sort(List list, Comparator comp)

Searching in Collections

The Collections class provides two static methods for searching in sorted lists.

static int binarySearch(List sortedList, Object obj)
static int binarySearch(List sortedList, Object obj, Comparator comp)

The following methods find the minimum and maximum elements in a collection:

static Object max(Collection c)
static Object max(Collection c, Comparator comp)
static Object min(Collection c)
static Object min(Collection c, Comparator comp)

Singleton Collections

A singleton set, list or map (i.e., an immutable collection or map containing only one element or one entry, respectively) can be created by calling the following static factory methods of the Collections class, respectively:

static Set  singleton(Object o)
static List singletonList(Object o)
static Map  singletonMap(Object key, Object value)

For example, removing an element from a set can be done by using an immutable singleton set:

// Create a singleton set with the element to remove.
Set fishBone = Collections.singleton(bone);        // bone is a fish part.
// Remove the element
fish.removeAll(fishBone);                          // fish is a set of fish parts.

The empty set, the empty list, and the empty map are designated by the following constants:

Collections.EMPTY_SET
Collections.EMPTY_LIST
Collections.EMPTY_MAP

These constants come in handy when a collection or map is needed that cannot be populated.

Other Utility Methods in the Collections Class

Most methods accept a List, while a few operate on arbitrary Collection objects. Practically any operation on a list can be done using these methods.

static void copy(List dst, List src)

static void fill(List list, Object o)

static List nCopies(int n, Object o)

static void reverse(List list)

static Comparator reverseOrder()

The following code conjures up a modifiable list initialized with 99 null elements:

List itemsList = new ArrayList(Collections.nCopies(99, null));

This code would sort a list of Integers and an array of strings in descending order and in inverse-lexicographical order, respectively:

Collections.sort(intList, Collections.reverseOrder());
Arrays.sort(strArray, Collections.reverseOrder());

The elements in the following set would be maintained sorted in descending order:

Collection intSet = new TreeSet(Collections.reverseOrder());
intSet.add(new Integer(9));  intSet.add(new Integer(11));
intSet.add(new Integer(-4)); intSet.add(new Integer(1));
System.out.println(intSet);          // [11, 9, 1, -4]

static void shuffle(List list)

boolean replaceAll(List list, Object oldVal, Object newVal)

static void rotate(List list, int distance)

static void swap(List list, int i, int j)

The effect of these utility methods can be limited to a sublist, that is, a segment of the list. The following code illustrates rotation of elements in a list. Note how the rotation in the sublist view is reflected in the original list.

// intList denotes the following list:                          [9, 11, -4, 1, 7]
Collections.rotate(intList, 2);        // Two to the right.     [1, 7, 9, 11, -4]
Collections.rotate(intList, -2);       // Two to the left.      [9, 11, -4, 1, 7]
List intSublist = intList.subList(1,4);// Sublist:                 [11, -4, 1]
Collections.rotate(intSublist, -1);    // One to the left.         [-4, 1, 11]
                                       // intList is now:       [9, -4, 1, 11, 7]

Utility Methods in the Arrays Class

The Arrays class provides useful utility methods that operate on arrays: binary search, sorting, array comparison, array filling.

The Arrays class also provides the static asList() method, which can be used to create List views of arrays. Changes to the List view reflect in the array, and vice versa. The List is said to be backed by the array. The List size is equal to the array length and cannot be changed. The asList() method in the Arrays class and the toArray() method in the Collection interface provide the bidirectional bridge between arrays and collections.

static List asList(Object[] backingArray)

String[] jiveArray       = new String[] {"java", "jive", "java", "jive"};
Set      jiveSet         = new HashSet(Arrays.asList(jivearray));        // (1)
String[] uniqueJiveArray = (String[]) jiveSet.toArray(new String[0]);    // (2)

At (1), the jiveArray is used to create a List, which, in turn, is used to create a Set. At (2) the argument to the toArray() method specifies the type of the array to be created from the set. The final array uniqueJiveArray does not contain duplicates.

Abstract Implementations

The concrete collection implementations in the java.util package are based on abstract implementations (see Figures 11.2 and 11.3). For example, the HashSet implementation is based on the AbstractSet implementation, which, in turn, extends the AbstractCollection implementation. These abstract classes already provide most of the machinery by implementing the relevant collection interfaces, and are excellent starting points for implementing customized collections.