The Collection Algorithms - java.util

The Collection Algorithms

The Collections Framework defines several algorithms that can be applied to collections and maps. These algorithms are defined as static methods within the Collections class. They are summarized in Table 18-15. As explained earlier, beginning with JDK 5 all of the algorithms were retrofitted for generics.

Several of the methods can throw a ClassCastException, which occurs when an attempt is made to compare incompatible types, or an UnsupportedOperationException, which occurs when an attempt is made to modify an unmodifiable collection. Other exceptions are possible, depending on the method.

One thing to pay special attention to is the set of checked methods, such as checkedCollection( ), which returns what the API documentation refers to as a “dynamically typesafe view” of a collection. This view is a reference to the collection that monitors insertions into the collection for type compatibility at run time. An attempt to insert an incompatible element will cause a ClassCastException. Using such a view is especially helpful during debugging because it ensures that the collection always contains valid elements. Related methods include checkedSet( ), checkedList( ), checkedMap( ), and so on. They obtain a type-safe view for the indicated collection.

Notice that several methods, such as synchronizedList( ) and synchronizedSet( ), are used to obtain synchronized (thread-safe) copies of the various collections. As a general rule, the standard collections implementations are not synchronized. You must use the synchronization algorithms to provide synchronization. One other point: iterators to synchronized collections must be used within synchronized blocks.

The set of methods that begins with unmodifiable returns views of the various collections that cannot be modified. These will be useful when you want to grant some process read—but not write—capabilities on a collection.

Collections defines three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. All are immutable.

The following program demonstrates some of the algorithms. It creates and initializes a linked list. The reverseOrder( ) method returns a Comparator that reverses the comparison of Integer objects. The list elements are sorted according to this comparator and then are displayed. Next, the list is randomized by calling shuffle( ), and then its minimum and maximum values are displayed.

// Demonstrate various algorithms. import java.util.*;

class AlgorithmsDemo {

public static void main(String args[]) {

     //Create and initialize linked list.

     LinkedList<Integer> ll = new LinkedList<Integer>(); ll.add(-8);

ll.add(20); ll.add(-20); ll.add(8);

     //Create a reverse order comparator.

     Comparator<Integer> r = Collections.reverseOrder();

     //Sort list by using the comparator.

     Collections.sort(ll, r);

System.out.print("List sorted in reverse: ");

for(int i : ll)

System.out.print(i+ " ");

System.out.println();

     //Shuffle list.

     Collections.shuffle(ll);

     //Display randomized list.

     System.out.print("List shuffled: "); for(int i : ll)

System.out.print(i + " ");

System.out.println();

System.out.println("Minimum: " + Collections.min(ll));

System.out.println("Maximum: " + Collections.max(ll));

}

}

Output from this program is shown here:

List sorted in reverse: 20 8 -8 -20

List shuffled: 20 -20 8 -8

Minimum: -20

Maximum: 20

Notice that min( ) and max( ) operate on the list after it has been shuffled. Neither requires a sorted list for its operation.