11.8 Working with Collections

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)

The first method sorts the elements in the list according to their natural order. The second method does the sorting according to the total ordering specified by the comparator (see Section 11.6).

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 methods use a binary search to find the index of the obj element in the specified sorted list. The first method requires that the list is sorted according to natural order, whereas the second method requires that it is sorted according to the total ordering dictated by the comparator.

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)

The one-argument methods require that the elements have a natural ordering. The other methods require that the elements have a total ordering enforced by the comparator.

The time for the search is proportional to the size of the collection. The methods are applicable to any collection, regardless of any ordering.

Calling any of the method with an empty collection as parameter results in an NoSuchElementException .

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)

Adds the elements from the src list to the dst list.

static void fill(List list, Object o)

Replaces all of the elements of the list with the specified element.

static List nCopies(int n, Object o)

Creates an immutable list with n copies of the specified object.

static void reverse(List list)

Reverses the order of the elements in the list.

static Comparator reverseOrder()

Returns a comparator that enforces the reverse of the natural ordering. Useful for maintaining objects in reverse-natural order in sorted collections and arrays.

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 Integer s 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)

Randomly permutes the list, that is, shuffles the elements.

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

Replaces all elements equal to oldVal with newVal in the list; returns true if the list was modified.

static void rotate(List list, int distance)

Rotates the elements towards the end of the list by the specified distance. A negative value will rotate toward the start of the list.

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

Swaps the elements at indices i and 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.