Java Notes

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.