The java.util.Collections class is a fundamental utility within the Java platform, providing a suite of static methods designed to perform various operations on collection objects. Described as offering "polymorphic algorithms," this class simplifies common tasks such as sorting, searching, modifying, and creating specialized versions of collections. While not a collection interface itself, Collections acts as a toolkit, applying its functionalities predominantly to List instances, though some methods are applicable to broader Collection types.
Specialized Collection Wrappers
The Collections class offers methods to wrap existing collections, enhancing them with specific behaviors like immutability, thread safety, or runtime type checking. These wrappers delegate operations to the underlying collection while intercepting certain actions to enforce new constraints.
Immutable Views of Collections
Methods like unmodifiableCollection(), unmodifiableSet(), unmodifiableList(), and their map counterparts provide read-only views of existing collections. Attempts to modify these wrappers will result in an UnsupportedOperationException. This is achieved through an internal wrapper class that holds a reference to the original collection and overrides all mutation methods to throw an exception.
// Example: Creating an unmodifiable list
List<String> originalList = new ArrayList<>();
originalList.add("Element A");
originalList.add("Element B");
List<String> immutableList = Collections.unmodifiableList(originalList);
// Attempting to modify the immutable view will throw an exception
try {
immutableList.add("Element C");
} catch (UnsupportedOperationException e) {
System.out.println("Cannot add to unmodifiable list: " + e.getMessage());
}
// The original list remains modifiable
originalList.add("Element C");
System.out.println("Original list: " + originalList);
System.out.println("Immutable view: " + immutableList); // Reflects changes in original list
Consider the structure of an unmodifiable wrapper, for instance, UnmodifiableCollection:
static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
private final Collection<? extends E> wrappedData;
UnmodifiableCollection(Collection<? extends E> collection) {
if (collection == null)
throw new NullPointerException();
this.wrappedData = collection;
}
public int size() { return wrappedData.size(); }
public boolean isEmpty() { return wrappedData.isEmpty(); }
// ... other query methods ...
// Mutation methods are overridden to throw an exception
public boolean add(E element) {
throw new UnsupportedOperationException();
}
public boolean remove(Object obj) {
throw new UnsupportedOperationException();
}
// ... other mutation methods ...
public Iterator<E> iterator() {
return new Iterator<E>() {
private final Iterator<? extends E> internalIterator = wrappedData.iterator();
public boolean hasNext() { return internalIterator.hasNext(); }
public E next() { return internalIterator.next(); }
// Iterator's remove method also throws an exception
public void remove() { throw new UnsupportedOperationException(); }
};
}
}
This pattern ensures that any modification attempt via the wrapper fails, though direct modifications to the underlying collection will still be reflected in the unmodifiable view.
Synchronized Collections for Thread Safety
For scenarios requiring thread-safe collections without resorting to Java's concurrent collections (like ConcurrentHashMap), Collections provides synchronization wrappers. Methods such as synchronizedCollection(), synchronizedList(), and synchronizedMap() return thread-safe equivalents of their respective collection types.
These wrappers achieve thread safety by synchronizing all access to the backing collection on an internal mutex object. While effective, this approach can introduce performance overhead due to coarse-grained locking, as every method call is synchronized. A critical caveat is that iterators and streams returned by these synchronized collections are *not* automatically thread-safe; manual synchronization is required when iterating or processing elements concurrently to prevent race conditions.
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
final Collection<E> underlyingCollection;
final Object synchronizationLock; // The mutex object
SynchronizedCollection(Collection<E> collection) {
this.underlyingCollection = Objects.requireNonNull(collection);
synchronizationLock = this; // Default mutex is the instance itself
}
SynchronizedCollection(Collection<E> collection, Object lock) {
this.underlyingCollection = Objects.requireNonNull(collection);
this.synchronizationLock = Objects.requireNonNull(lock);
}
public int size() {
synchronized (synchronizationLock) { return underlyingCollection.size(); }
}
public boolean add(E element) {
synchronized (synchronizationLock) { return underlyingCollection.add(element); }
}
// ... all other methods are synchronized ...
// IMPORTANT: Iterators and Spliterators require external synchronization!
public Iterator<E> iterator() {
return underlyingCollection.iterator(); // User must manually synchronize when iterating
}
}
Type-Checked Collections for Runtime Safety
To enforce type safety at runtime, the Collections class offers methods like checkedCollection() and checkedList(). These wrappers ensure that only elements of a specific type (or compatible subtypes) can be added to the collection. If an incompatible element is added, a ClassCastException is thrown.
public static <E> Collection<E> checkedCollection(Collection<E> baseCollection, Class<E> elementType) {
return new CheckedCollection<>(baseCollection, elementType);
}
static class CheckedCollection<E> implements Collection<E>, Serializable {
final Collection<E> delegateCollection;
final Class<E> expectedType;
CheckedCollection(Collection<E> collection, Class<E> type) {
this.delegateCollection = Objects.requireNonNull(collection, "Base collection cannot be null");
this.expectedType = Objects.requireNonNull(type, "Element type cannot be null");
}
// Helper method to validate element type
@SuppressWarnings("unchecked")
E checkElementType(Object obj) {
if (obj != null && !expectedType.isInstance(obj))
throw new ClassCastException("Attempted to insert " + obj.getClass() +
" into collection expecting type " + expectedType);
return (E) obj;
}
public boolean add(E element) {
return delegateCollection.add(checkElementType(element)); // Type check on add
}
// ... addAll, put methods also perform type checking ...
}
This is particularly useful in legacy code or when dealing with raw types, where compile-time generics might be bypassed, preventing potential ClassCastExceptions later during element retrieval.
Special Purpose Collections
The Collections class also provides static factory methods to create specialized collection instances, primarily for efficiency and convenience in specific scenarios.
Empty Collections and Iterators
Methods like emptyList(), emptySet(), and emptyMap() return immutable, empty instances of their respective types. These are highly efficient as they are pre-allocated, immutable singletons, avoiding repeated object creation for empty collections. They are useful for returning an empty result set instead of null, which can prevent NullPointerExceptions.
private static class EmptyIterator<E> implements Iterator<E> {
static final EmptyIterator<Object> INSTANCE = new EmptyIterator<>();
public boolean hasNext() { return false; }
public E next() { throw new NoSuchElementException(); }
public void remove() { throw new IllegalStateException(); }
}
Singleton Collections and Iterators
Conversely, singletonList(), singleton() (for sets), and singletonMap() create immutable collections containing only a single specified element. These are memory-efficient for representing a collection that is guaranteed to have exactly one element.
private static class SingletonList<E> extends AbstractList<E> implements RandomAccess, Serializable {
private final E soleElement;
SingletonList(E element) {
this.soleElement = element;
}
public int size() { return 1; }
public E get(int index) {
if (index != 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: 1");
return soleElement;
}
// All mutation methods throw UnsupportedOperationException
}
Common Collection Algorithms
Beyond specialized wrappers, the Collections class is renowned for its implementations of frequently used algorithms.
Sorting Elements (sort)
The sort() method reorders the elements of a List. It comes in two variants:
sort(List<T> list): Sorts elements according to their natural order, meaning elements must implement theComparableinterface.sort(List<T> list, Comparator<? super T> comparator): Sorts elements using a providedComparator, allowing custom ordering.
Internally, Collections.sort() typically delegates to the List interface's default sort() method, which converts the list to an array, sorts the array using Arrays.sort() (often an optimized merge sort or Timsort), and then updates the list from the sorted array.
// Example using natural order
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
Collections.sort(numbers); // numbers will be [1, 2, 5, 8, 9]
// Example using a custom comparator (descending order)
List<String> words = new ArrayList<>(Arrays.asList("apple", "zebra", "banana"));
Collections.sort(words, (s1, s2) -> s2.compareTo(s1)); // words will be [zebra, banana, apple]
Binary Search (binarySearch)
The binarySearch() method efficiently locates an element within a sorted List. It also has two overloads:
binarySearch(List<? extends Comparable<? super T>> list, T key): Searches a list sorted by natural order.binarySearch(List<? extends T> list, T key, Comparator<? super T> comparator): Searches a list sorted by a specificComparator.
It's crucial that the list is sorted according to the same order used for the search, otherwise, the results are undefined. The implementation leverages the RandomAccess interface: if a List implements RandomAccess (like ArrayList), index-based access is used for speed; otherwise, an iterator-based approach is employed for sequential access (like with LinkedList).
Reversing Elements (reverse)
The reverse(List<?> list) method inverts the order of elements in a list. Similar to other list-modifying algorithms, it has optimizations based on whether the list supports RandomAccess, either swapping elements directly by index or using list iterators.
List<Character> chars = new ArrayList<>(Arrays.asList('a', 'b', 'c', 'd'));
Collections.reverse(chars); // chars will be [d, c, b, a]
Shuffling Elements (shuffle)
The shuffle(List<?> list) method randomly reorders the elements in a list, often used to randomize the order of items. It has an overload that accepts a Random instance for reproducible shuffling.
List<String> deck = new ArrayList<>(Arrays.asList("Ace", "King", "Queen", "Jack"));
Collections.shuffle(deck); // deck will be randomly reordered
Swapping Elements (swap)
The swap(List<?> list, int i, int j) method exchanges the elements at two specified positions within a list. This is a basic utility often used internally by other algorithms like shuffle and reverse.
public static void swap(List<?> list, int index1, int index2) {
final List<Object> targetList = (List<Object>) list; // Unsafe cast for internal use
targetList.set(index1, targetList.set(index2, targetList.get(index1)));
}
Copying Elements (copy)
The copy(List<? super T> destination, List<? extends T> source) method copies all elements from a source list to a destination list. The destination list must be at least as large as the source list, otherwise, an IndexOutOfBoundsException is thrown. The method iterates through the source list and replaces elements in the destination list at corresponding indices.
List<String> source = Arrays.asList("Alpha", "Beta");
List<String> destination = new ArrayList<>(Arrays.asList("One", "Two", "Three"));
Collections.copy(destination, source); // destination will be ["Alpha", "Beta", "Three"]
Finding Min/Max Elements (min, max)
The min() and max() methods return smallest and largest elements, respectively, from a given Collection. Like sort(), they have overloads that accept either naturally comparable elements or a custom Comparator.
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> items) {
Iterator<? extends T> iterator = items.iterator();
if (!iterator.hasNext())
throw new NoSuchElementException();
T smallestCandidate = iterator.next();
while (iterator.hasNext()) {
T currentItem = iterator.next();
if (currentItem.compareTo(smallestCandidate) < 0)
smallestCandidate = currentItem;
}
return smallestCandidate;
}
Rotating Elements (rotate)
The rotate(List<?> list, int distance) method shifts the elements of a list cyclically. A positive distance rotates elements to the right (towards higher indices), while a negative distance rotates to the left. For example, rotating [A, B, C, D] by 1 yields [D, A, B, C].
The implementation uses different strategies based on the list's size and whether it supports RandomAccess. For RandomAccess lists or smaller lists, a direct index-based rotation is used. This involves identifying cycles within the rotation and moving elements accordingly.
private static <T> void performIndexRotation(List<T> targetList, int shiftAmount) {
int listSize = targetList.size();
if (listSize == 0) return;
shiftAmount = shiftAmount % listSize;
if (shiftAmount < 0) shiftAmount += listSize; // Normalize negative shifts
if (shiftAmount == 0) return;
for (int cycleStart = 0, elementsMoved = 0; elementsMoved != listSize; cycleStart++) {
T elementToDisplace = targetList.get(cycleStart);
int currentIdx = cycleStart;
do {
currentIdx = (currentIdx + shiftAmount) % listSize; // Calculate next position
elementToDisplace = targetList.set(currentIdx, elementToDisplace);
elementsMoved++;
} while (currentIdx != cycleStart);
}
}
Replacing All Occurrences (replaceAll)
The replaceAll(List<T> list, T oldVal, T newVal) method replaces every occurrence of a specified element (oldVal) with another element (newVal) within the list.
Filling Elements (fill)
The fill(List<? super T> list, T obj) method sets every element in the specified list to the provided object obj. This effectively overwrites the list's current contents with obj repeated across all indices.
Sublist Search (indexOfSubList, lastIndexOfSubList)
These methods search for the first (indexOfSubList) or last (lastIndexOfSubList) occurrence of one list within another. They return the starting index of the sublist or -1 if it's not found. The search requires the sublist to be a contiguous sequence of elements.
Creating N-Copies (nCopies)
The nCopies(int n, T o) method returns an immutable List consisting of n copies of the specified object o. This is useful for creating lists with repeating elements efficiently without manually adding each one.
Reverse Order Comparator (reverseOrder)
The reverseOrder() method returns a Comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface. It's a convenient way to sort in descending order.
Enumeration Utilities (enumeration, list)
The enumeration(Collection<T> c) method returns an Enumeration over the specified collection. Conversely, list(Enumeration<T> e) creates an ArrayList containing all elements returned by the given enumeration. These methods are primarily for bridging between the older Enumeration API and the more modern Collection framework.
Element Frequency (frequency)
The frequency(Collection<?> c, Object o) method counts the number of times a specified object o appears in a collection c. It uses the equals() method to compare elements.
Disjoint Collections (disjoint)
The disjoint(Collection<?> c1, Collection<?> c2) method returns true if the two specified collections have no elements in common, meaning their intersection is empty. It's optimized for efficiency, especially if one of the collections is a Set.
Bulk Addition (addAll)
The addAll(Collection<? super T> c, T... elements) method adds all of the specified elements to the given collection. It accepts a variable-length argument list (varargs), making it convenient for adding multiple elements in a single call.
Map-Backed Set (newSetFromMap)
The newSetFromMap(Map<E, Boolean> map) method creates a Set backed by the specified Map. This allows using a Map as a Set, leveraging the map's unique key property. The value associated with each key in the backing map will always be Boolean.TRUE.
LIFO Queue Adapter (asLifoQueue)
The asLifoQueue(Deque<T> deque) method returns a Queue view of a Deque (double-ended queue). While a Deque can function as both a FIFO (First-In, First-Out) queue and a LIFO (Last-In, First-Out) stack, this adapter specifically exposes it as a LIFO queue. Operations like add(), offer(), remove(), and poll() are mapped to the Deque's stack operations (e.g., push(), pop()).