Collections Class

The java.util.Collections class contains static utility methods for manipulating collections.

 

Some useful Collections methods

Assume the following declarations have been made, where T is a class or interface type.

   int i; 
   List<T> listC;   // List of the Comparable objects.
   List<T> list;   // Any kind of list.  Need not be Comparable.
   Comparator<T> comp; 
   T key; 
   T t;
   Collection<T> coll;  // Any kind of Collection (List, Set, Deque).
   Collection<T> collC; // Any kind of Collection implementing Comparable. 

Rearranging - Sorting, Shuffling, . . .

Collections.sort(listC)
Sorts listC. Elements must be Comparable<T>. Stable, O(N log N).

Collections.sort(list, comp)
Sorts list using a comparator.

Collections.shuffle(list)
Puts the elements of list in random order.

Collections.reverse(list)
Reverses the elements of list.

Searching

i =
Collections.binarySearch(listC, key)
Searches list for key. Returns index of element or negative value if not found. See Binary Search.

i =
Collections.binarySearch(list, key, comp)
Searches in list for key using Comparator comp.

t =
Collections.max(collC)
Returns maximum valued Comparable object in collC.

t =
Collections.max(coll, comp)
Maximum valued object in coll using Comparator comp.

t =
Collections.min(collC)
Returns minimum valued Comparable object in collC.

t =
Collections.min(coll, comp)
Minimum valued object in coll using Comparator comp.

There are many additional methods in Collections, but the above are a good start.

 

Searching may also be implemented in data structure classes

All List and Set classes implement the contains() method, which performes a linear search on lists (O(N)), a binary search for TreeSets (O(log N)), and a hashed search for HashSets (O(1)).

Maps define get() to search for the key. For HashMaps the search is O(1), and for TreeMaps the search is O(log N).

 

Sorting may be implicit in a data structure class

TreeSet data and TreeMap keys are sorted at all times. They are implemented as binary trees, so insertion and search are both O(log N). An iterator can be used to get retrieve the data (TreeSets) or keys (TreeMaps) in sorted order. Either the element class must be Comparable, or a Comparator must be supplied.