JAVA / COLLECTIONS
Collections utilities for sorting, searching and views
Use java.util.Collections to sort, binary-search and wrap lists correctly, decode negative search results, and tell a live view from a real copy.
What you will learn
- Sort and reverse in place with Collections; those methods return void, not a new list.
- Search with the same comparator you sorted by, or binarySearch quietly returns nonsense.
- Turn a negative binarySearch result into an insertion index with -result - 1.
- Spot when a wrapper is a live view over a still-mutable source, not a copy.
Understanding Collections utilities for sorting, searching and views
The Collections class is a box of static methods that fall into three groups, and telling them apart removes most of the confusion. Destructive algorithms such as sort, reverse, shuffle, swap, rotate and fill rearrange the list you hand them and return void. Queries such as binarySearch, min, max, frequency and disjoint read the collection and hand back a value. Factories such as unmodifiableList, synchronizedMap, singletonList and nCopies return a new object that usually wraps the argument instead of copying it.
binarySearch trusts you completely. It halves the candidate range using comparisons, so it is only correct when the list is already sorted by exactly the ordering the search uses; a list sorted with Collections.reverseOrder() and then searched by natural order yields a wrong index or a false miss, with no exception to warn you. When the key is genuinely absent the return value is -(insertion point) - 1, which can never be a valid index, so one call tells you both "not here" and "it belongs at position n" via -result - 1.
A view is a window, not a photograph. Collections.unmodifiableList(list) refuses add, set and remove made through the wrapper, but the underlying list stays writable and every change to it appears the next time you read the view, so the wrapper is read-only rather than immutable. The same holds for a map's keySet and values and for list.subList(from, to): writing through them writes into the backing collection. When a caller needs something that cannot shift under it, hand over new ArrayList<>(list) or List.copyOf(list) instead.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionsUtilities {
public static void main(String[] args) {
List<String> names = new ArrayList<>(List.of("Ravi", "Ana", "Tomas", "Bo"));
Collections.sort(names);
System.out.println("sorted: " + names);
System.out.println("index of Bo: " + Collections.binarySearch(names, "Bo"));
System.out.println("miss for Zoe: " + Collections.binarySearch(names, "Zoe"));
Collections.sort(names, Collections.reverseOrder());
System.out.println("reversed: " + names);
System.out.println("stale search: " + Collections.binarySearch(names, "Bo"));
System.out.println("matched search: "
+ Collections.binarySearch(names, "Bo", Collections.reverseOrder()));
List<String> view = Collections.unmodifiableList(names);
names.add("Ines");
System.out.println("view sees the add: " + view);
}
}Collections methods either mutate the collection you pass in or return a thin view of it, so almost nothing you get back is an independent copy.
Worked examples
Read-only is not immutable
Shows that an unmodifiable wrapper blocks writes through itself while the original list keeps changing behind it.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class UnmodifiableView {
public static void main(String[] args) {
List<Integer> scores = new ArrayList<>();
scores.add(70);
scores.add(90);
List<Integer> readOnly = Collections.unmodifiableList(scores);
try {
readOnly.add(100);
} catch (UnsupportedOperationException e) {
System.out.println("view refused the write");
}
scores.add(100);
System.out.println("through the view: " + readOnly);
System.out.println("same size? " + (readOnly.size() == scores.size()));
List<Integer> snapshot = new ArrayList<>(scores);
scores.set(0, 0);
System.out.println("view: " + readOnly);
System.out.println("copy: " + snapshot);
}
}Example explained
Line 1readOnly.add(100) throws UnsupportedOperationException because the wrapper implements every mutator as an immediate throw.
Line 2scores.add(100) still succeeds: the wrapper never took ownership of the list, it only filters calls that go through itself.
Line 3readOnly.size() == scores.size() is true because the view holds a reference to the same ArrayList rather than its own elements.
Line 4new ArrayList<>(scores) copies the references once, so the later set(0, 0) shows up in readOnly but not in snapshot.
In-place algorithms and plain queries
Contrasts the void-returning rearranging methods with the query methods that only read a collection.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class InPlaceAlgorithms {
public static void main(String[] args) {
List<String> deck = new ArrayList<>(List.of("a", "b", "c", "d", "e"));
Collections.reverse(deck);
System.out.println("reverse: " + deck);
Collections.swap(deck, 0, 4);
System.out.println("swap: " + deck);
Collections.rotate(deck, 2);
System.out.println("rotate: " + deck);
List<String> votes = new ArrayList<>(List.of("x", "y", "x", "x"));
System.out.println("frequency of x: " + Collections.frequency(votes, "x"));
System.out.println("max: " + Collections.max(votes));
System.out.println("disjoint: " + Collections.disjoint(deck, votes));
}
}Example explained
Line 1Collections.reverse(deck) mutates deck and returns void, so the printed list is deck itself, not a reversed copy.
Line 2rotate(deck, 2) shifts every element two slots right with wraparound: index i ends up holding what was at (i - 2) mod 5.
Line 3frequency counts equals matches by walking the collection, so it needs no ordering and accepts any Collection.
Line 4disjoint is true because deck and votes share no element; it returns as soon as it finds one in common.
subList as a writable window
Demonstrates sorting and filling only part of a list through a subList view, and how a structural change invalidates it.
import java.util.ArrayList;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.List;
public class SubListView {
public static void main(String[] args) {
List<Integer> data = new ArrayList<>(List.of(9, 4, 7, 1, 8, 3));
List<Integer> middle = data.subList(1, 5);
Collections.sort(middle);
System.out.println("backing list: " + data);
System.out.println("window: " + middle);
Collections.fill(middle, 0);
System.out.println("after fill: " + data);
data.add(5);
try {
middle.get(0);
} catch (ConcurrentModificationException e) {
System.out.println("window invalid after structural change");
}
}
}Example explained
Line 1subList(1, 5) is a view over positions 1 to 4, so Collections.sort(middle) sorts exactly that slice of data and leaves 9 and 3 in place.
Line 2Collections.fill(middle, 0) writes through the window, replacing four elements of the backing list with 0.
Line 3data.add(5) changes the structure of the backing list, so reading through middle now throws ConcurrentModificationException.
Important notes
Collections.emptyList(), singletonList(x) and nCopies(n, x) are fixed structures that reject add and set; nCopies also stores one element reference n times, so every position is the same object.
Collections.synchronizedList only locks individual method calls, so iterating it still requires your own synchronized block on the wrapper object.
Common mistakes
Writing List<String> sorted = Collections.sort(names); this does not compile, because sort reorders names itself and its return type is void.
Calling binarySearch on a list that was never sorted, or sorted with a different comparator: as in the main example, "Bo" is in the list yet the search returns -1, and nothing signals the error.
Publishing Collections.unmodifiableList(internal) as if it were a defensive copy while still mutating internal: callers watch the contents change under them and their iteration can fail with ConcurrentModificationException.
Try it yourself
Change, predict, then run
Build new ArrayList<>(List.of(42, 8, 15, 4, 23)), sort it with Collections.sort, then print Collections.binarySearch(list, 16), insert 16 at the index you compute from that negative value, and print the list plus the new search result to confirm it is now a valid index.
Open the Java workspaceCheck your understanding
A list is sorted with Collections.sort(list, Collections.reverseOrder()) so it reads [Tomas, Ravi, Bo, Ana]. What happens when you then call Collections.binarySearch(list, "Bo") with no comparator?
- It returns -1: the search assumes ascending natural order, so the first comparisons push it to the wrong end and it reports a miss.
- It returns 2, because binarySearch falls back to a linear scan when the halving fails to land on the key.
- It throws IllegalArgumentException, because the list is not in natural order.
- It returns -3, the encoded position where Bo would belong in natural order.
Show answer
binarySearch cannot inspect how the list is ordered; it only compares and throws away half the range, so on descending data the comparison against Ravi sends it left of Bo and it finishes with the miss encoding -(0 + 1) = -1. Option 1 is tempting because Bo really is present, but there is no linear fallback: an element that exists can be reported absent, and the contract says the result is simply undefined when the list is not sorted for the ordering in use, which is also why no exception is thrown.