☕ JavaCollections Framework

Collections Class

The Collections class in java.util is a utility class consisting entirely of static methods that operate on or return collections. It is the companion to the Arrays class — where Arrays serves arrays, Collections serves Collection instances. Collections provides algorithms (sort, shuffle, reverse, rotate, swap, fill, copy, frequency, disjoint), factory methods for wrapper collections (unmodifiableList, synchronizedSet, singletonList, emptyList, nCopies), and extremal-value queries (min, max). Understanding Collections means knowing which algorithm is available, how each works, what the preconditions are, and how the unmodifiable and synchronised wrappers differ from truly immutable or concurrent collections. This entry covers every major method group with precise semantics, performance characteristics, and the pitfalls of each wrapper type.

Sorting and Reordering Algorithms

Collections.sort() sorts a List in-place using the natural ordering of its elements or a supplied Comparator. It uses the same TimSort algorithm as Arrays.sort() for objects — stable, O(n log n), fast on nearly-sorted data. The list must be modifiable; sorting a list returned by Collections.unmodifiableList() or Arrays.asList() of a fixed array throws UnsupportedOperationException. Collections.sort() delegates to List.sort() since Java 8, which in turn uses the list's toArray() to sort the backing array and writes sorted elements back. This is equivalent to sorting the list but more direct. For a RandomAccess list like ArrayList, the array-based sorting is efficient. For a LinkedList, the toArray-sort-write-back round-trip is faster than any in-place linked list sort. Collections.reverse() reverses the order of elements in a List in O(n) time by swapping elements from the two ends toward the middle. Collections.shuffle() randomises element order using a random permutation (Fisher-Yates algorithm) in O(n) time. Collections.rotate() shifts all elements by a given distance — positive distance shifts elements toward higher indices (or equivalently, moves elements from the end to the beginning). Collections.swap() exchanges two elements at specified indices in O(1) time for RandomAccess lists. Collections.fill() replaces every element in a List with a single specified value. Collections.copy() copies elements from a source list into a destination list, element-by-element. The destination must be at least as large as the source; only positions 0 through source.size()-1 are written.

Java

// ── Sorting ───────────────────────────────────────────────────────────
List<Integer> numbers = new ArrayList<>(List.of(5, 2, 8, 1, 9, 3));

Collections.sort(numbers);                          // natural order
System.out.println(numbers);   // [1, 2, 3, 5, 8, 9]

Collections.sort(numbers, Comparator.reverseOrder()); // descending
System.out.println(numbers);   // [9, 8, 5, 3, 2, 1]

// Custom comparator
List<String> words = new ArrayList<>(List.of("banana", "apple", "cherry", "fig"));
Collections.sort(words, Comparator.comparingInt(String::length)
                                  .thenComparing(Comparator.naturalOrder()));
System.out.println(words);  // [fig, apple, banana, cherry]

// ── Reordering algorithms ──────────────────────────────────────────────
List<String> list = new ArrayList<>(List.of("A", "B", "C", "D", "E"));

Collections.reverse(list);
System.out.println(list);    // [E, D, C, B, A]

Collections.shuffle(list);
System.out.println(list);    // random order, e.g. [C, A, E, B, D]

Collections.shuffle(list, new Random(42));  // seeded for reproducible shuffle

// ── rotate — shift elements right by distance ─────────────────────────
List<Integer> r = new ArrayList<>(List.of(1, 2, 3, 4, 5));
Collections.rotate(r, 2);    // shift right by 2
System.out.println(r);       // [4, 5, 1, 2, 3]

Collections.rotate(r, -2);   // shift left by 2 (negative distance)
System.out.println(r);       // [1, 2, 3, 4, 5]

// ── swap and fill ──────────────────────────────────────────────────────
List<String> s = new ArrayList<>(List.of("A", "B", "C", "D"));
Collections.swap(s, 0, 3);   // swap index 0 and 3
System.out.println(s);       // [D, B, C, A]

Collections.fill(s, "X");
System.out.println(s);       // [X, X, X, X]

// ── copy — destination must be at least as large as source ────────────
List<String> src  = List.of("a", "b", "c");
List<String> dest = new ArrayList<>(List.of("X", "X", "X", "X", "X"));
Collections.copy(dest, src);
System.out.println(dest);    // [a, b, c, X, X] — only first 3 overwritten

Search and Statistics Methods

Collections.binarySearch() performs binary search on a sorted List. The list must be sorted into ascending order according to natural ordering or the same Comparator passed to binarySearch — otherwise results are undefined. The return-value contract mirrors Arrays.binarySearch(): if found, returns the index; if not found, returns -(insertion point) - 1. The List must support RandomAccess (ArrayList, not LinkedList) for O(log n) performance; on a LinkedList binary search degrades to O(n) because index access requires traversal. Collections.frequency() counts how many elements in a Collection are equal to a specified object using equals(). This is an O(n) linear scan. Collections.disjoint() returns true if two Collections have no elements in common (their intersection is empty). It iterates the smaller collection and checks membership in the larger one — O(n) overall assuming contains() is O(1) for Set-backed collections. Collections.min() and Collections.max() find the minimum and maximum elements according to natural ordering or a Comparator. Both scan all elements in O(n) time. These are simple linear scans and are not aware of whether the collection is sorted — they do not exploit sorted order. For sorted collections like TreeSet, use first() and last() instead, which are O(log n). Collections.nCopies() returns an immutable List containing n copies of a specified object. All n elements are the same object — not n distinct equal objects. This list cannot be modified but can be used to initialise an ArrayList of a given size, as an argument to addAll(), or in any context where a uniform list is needed.

Java

// ── Binary search ────────────────────────────────────────────────────
List<Integer> sorted = new ArrayList<>(List.of(1, 3, 5, 7, 9, 11));

int idx = Collections.binarySearch(sorted, 7);
System.out.println(idx);   // 3 — found at index 3

int notFound = Collections.binarySearch(sorted, 6);
System.out.println(notFound);             // -4 — not found
System.out.println(-(notFound) - 1);      // 3 — insertion point

// Custom comparator binary search
List<String> byLength = new ArrayList<>(
    List.of("fig", "apple", "cherry", "strawberry"));
Collections.sort(byLength, Comparator.comparingInt(String::length));
int pos = Collections.binarySearch(byLength, "banana",
    Comparator.comparingInt(String::length));
System.out.println(pos);   // index of "banana" or a negative insertion point

// ── Frequency and disjoint ────────────────────────────────────────────
List<String> items = List.of("apple", "banana", "apple", "cherry", "apple");
System.out.println(Collections.frequency(items, "apple"));   // 3
System.out.println(Collections.frequency(items, "grape"));   // 0

List<Integer> a = List.of(1, 2, 3, 4);
List<Integer> b = List.of(5, 6, 7, 8);
List<Integer> c = List.of(3, 4, 5, 6);

System.out.println(Collections.disjoint(a, b));  // true  — no common elements
System.out.println(Collections.disjoint(a, c));  // false — 3 and 4 in both

// ── Min and max ────────────────────────────────────────────────────────
List<Integer> values = List.of(7, 2, 9, 1, 5, 8);
System.out.println(Collections.min(values));  // 1
System.out.println(Collections.max(values));  // 9

// With comparator:
List<String> strs = List.of("banana", "apple", "cherry");
System.out.println(Collections.min(strs,
    Comparator.comparingInt(String::length)));  // apple (shortest)

// ── nCopies ───────────────────────────────────────────────────────────
List<String> fiveHello = Collections.nCopies(5, "Hello");
System.out.println(fiveHello);   // [Hello, Hello, Hello, Hello, Hello]

// Use to initialise an ArrayList of given size:
List<Integer> zeros = new ArrayList<>(Collections.nCopies(10, 0));
System.out.println(zeros);   // [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
zeros.set(3, 99);            // mutable — can modify
System.out.println(zeros);   // [0, 0, 0, 99, 0, 0, 0, 0, 0, 0]

Unmodifiable Wrappers — Not Immutable

Collections provides unmodifiableList(), unmodifiableSet(), unmodifiableMap(), and corresponding methods for SortedSet, SortedMap, NavigableSet, and NavigableMap. These return a view of the original collection that throws UnsupportedOperationException on any structural modification attempt (add, remove, set, clear). They are write-through views, not copies — they wrap the original collection. The critical distinction between unmodifiable and immutable is that unmodifiable only prevents modification through the wrapper. The underlying original collection may still be modified directly, and those modifications are immediately visible through the wrapper. If someone holds a reference to the original List and adds elements to it, all holders of the unmodifiable wrapper see those additions. Truly immutable collections (List.of(), Set.of(), Map.of() from Java 9+) do not have this problem because no mutable backing collection exists. Unmodifiable wrappers are useful for defensive publishing — returning a read-only view of an internal collection from a method to prevent external code from modifying the collection. The class retains the only reference to the mutable original and publishes only the unmodifiable wrapper. As long as no code outside the class has a reference to the original, the unmodifiable wrapper provides effective immutability. Unmodifiable wrappers add a layer of indirection to every method call, which has a slight performance cost. For performance-critical code with many reads, storing the elements in List.of() (which is backed by a native array with no indirection) may be preferable.

Java

// ── Unmodifiable wrappers — write-through views ──────────────────────
List<String> mutable = new ArrayList<>(List.of("A", "B", "C"));
List<String> readOnly = Collections.unmodifiableList(mutable);

System.out.println(readOnly);  // [A, B, C]

// Read operations work normally:
System.out.println(readOnly.get(0));    // A
System.out.println(readOnly.size());    // 3
System.out.println(readOnly.contains("B")); // true

// Write operations throw UnsupportedOperationException:
try {
    readOnly.add("D");       // throws UnsupportedOperationException
} catch (UnsupportedOperationException e) {
    System.out.println("Cannot modify");
}

// ── Critical: underlying collection CAN still change ─────────────────
mutable.add("D");   // modify the ORIGINAL
System.out.println(readOnly);  // [A, B, C, D] — wrapper sees the change!
// This is NOT immutability — only modification through the wrapper is blocked

// ── True immutability — Java 9+ List.of() ────────────────────────────
List<String> immutable = List.of("A", "B", "C");
// immutable.add("D");   // throws UnsupportedOperationException
// Cannot be modified through ANY reference — no mutable backing exists

// ── Defensive publishing pattern ──────────────────────────────────────
public class ItemRepository {

    private final List<Item> items = new ArrayList<>();

    public void add(Item item) {
        items.add(item);
    }

    // Returns unmodifiable view — external code cannot modify our list
    public List<Item> getItems() {
        return Collections.unmodifiableList(items);
    }
    // 'items' field is private — no external code can modify via original reference
}

// ── All unmodifiable variants ─────────────────────────────────────────
Set<String>            roSet    = Collections.unmodifiableSet(new HashSet<>());
Map<String, Integer>   roMap    = Collections.unmodifiableMap(new HashMap<>());
SortedSet<String>      roSorted = Collections.unmodifiableSortedSet(new TreeSet<>());
SortedMap<String, Integer> roSMap = Collections.unmodifiableSortedMap(new TreeMap<>());
Collection<String>     roColl   = Collections.unmodifiableCollection(new ArrayList<>());

Singleton, Empty, and Synchronised Collections

Collections provides three categories of factory methods for special-purpose collections. Singleton collections (singletonList, singletonSet, singletonMap) create immutable collections containing exactly one element. Empty collections (emptyList, emptySet, emptyMap) create immutable empty collections. Synchronised wrappers (synchronizedList, synchronizedSet, synchronizedMap) wrap any collection with per-method synchronisation. Singleton and empty collections are lightweight: they do not back an array or hash table. singletonList returns an object that stores a single element reference; all List methods that require exactly one element work, and all modification methods throw. emptyList() returns a canonical empty list — the same instance is returned every time (it is a singleton itself). These are useful as return values when a method that returns a collection has nothing to return (emptyList() instead of null) or a single result (singletonList(element) instead of creating an ArrayList with one element). Synchronised wrappers wrap every method call in a synchronized block on the wrapper object. This ensures that individual method calls are atomic, but compound operations (check-then-act, iterate-then-modify) are not atomic and still require external synchronisation. The critical caveat: iteration requires the caller to synchronise on the collection object while iterating, because the Iterator is not covered by the per-method synchronisation. For concurrent code with significant contention, the java.util.concurrent classes (ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue) outperform synchronised wrappers because they use finer-grained locking, lock-free algorithms, or copy-on-write strategies that allow concurrent reads without contention.

Java

// ── Singleton collections — exactly one element ──────────────────────
List<String>          oneList = Collections.singletonList("only");
Set<String>           oneSet  = Collections.singleton("only");
Map<String, Integer>  oneMap  = Collections.singletonMap("key", 42);

System.out.println(oneList.get(0));    // "only"
System.out.println(oneSet.contains("only")); // true
System.out.println(oneMap.get("key")); // 42

// Modifications throw:
oneList.add("second");  // UnsupportedOperationException

// ── Empty collections — canonical empty, no allocation ───────────────
List<String>         empty  = Collections.emptyList();
Set<String>          emptyS = Collections.emptySet();
Map<String,Integer>  emptyM = Collections.emptyMap();

// emptyList() returns the SAME INSTANCE every call:
System.out.println(Collections.emptyList() == Collections.emptyList()); // true

// Use as null-safe return value instead of null:
public List<User> findByRole(String role) {
    List<User> result = userRepository.findByRole(role);
    return result != null ? result : Collections.emptyList();
    // Better: never return null from a method returning a collection
}

// ── Synchronised wrappers ──────────────────────────────────────────────
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// Individual operations are thread-safe:
syncList.add("A");         // synchronised
syncList.get(0);           // synchronised

// WRONG — iteration is NOT thread-safe without external synchronisation:
for (String s : syncList) {   // UNSAFE — another thread may modify during iteration
    System.out.println(s);
}

// CORRECT — synchronise on the list object during iteration:
synchronized (syncList) {
    for (String s : syncList) {   // safe — lock held for entire iteration
        System.out.println(s);
    }
}

// ── Synchronised variants ─────────────────────────────────────────────
Map<String, Integer>  syncMap  = Collections.synchronizedMap(new HashMap<>());
Set<String>           syncSet  = Collections.synchronizedSet(new HashSet<>());
SortedMap<String, Integer> syncSMap =
    Collections.synchronizedSortedMap(new TreeMap<>());

// ── Prefer concurrent collections for high contention ─────────────────
// Instead of:
Map<String, Integer> sync = Collections.synchronizedMap(new HashMap<>());
// Use:
Map<String, Integer> concurrent = new ConcurrentHashMap<>();
// ConcurrentHashMap: lock-free reads, segment-level write locks → much faster

Collections Class

Sorting and Reordering Algorithms

Search and Statistics Methods

Unmodifiable Wrappers — Not Immutable

Singleton, Empty, and Synchronised Collections

Related Topics in Collections Framework