Java Collection Algorithms
Java collection algorithms refer tojava.util.Collectionsa set of static methods provided in the Collections class, used to perform common operations such as sorting, searching, shuffling, filling, etc. on collections (List, Set, Map, etc.).
These algorithms are built into the JDK and are highly optimized. Developers do not need to write them from scratch; they can simply call them directly.
Collections Algorithms Overview
java.util.CollectionsCollections is a utility class; all of its methods are static, similar to the Arrays utility class for arrays.
The following table lists the most commonly used collection algorithms and their purposes:
| Algorithm Category | Method Name | Description |
|---|---|---|
| Sorting | sort() | Sorts a List in ascending order |
| Shuffling | shuffle() | Randomly shuffles the order of elements in a List |
| Reversal | reverse() | Reverses the order of elements in a List |
| Binary Search | binarySearch() | Performs a binary search for a specified element in a sorted List |
| Fill | fill() | Replaces all elements in a List with a specified element |
| Copy | copy() | Copies elements from one List to another List |
| Maximum/Minimum | max() / min() | Returns the maximum or minimum element in a collection |
| Frequency Count | frequency() | Returns the number of occurrences of a specified element in a collection |
| Disjoint Check | disjoint() | Determines whether two collections have any common elements |
| Immutable Collection | unmodifiableXxx() | Returns a read-only view of a collection |
| Thread Safety | synchronizedXxx() | Returns a thread-safe wrapper for a collection |
Sorting
Collections.sort()It is the most commonly used collection algorithm, arranging the elements in a List in ascending order.
Under the hood, it uses an optimized merge sort (TimSort), with a time complexity of O(n log n) and stable performance.
The sorting process is shown in the following figure:
Natural Order Sorting
When the element class implementsComparablethe interface, you can directly call sort() to sort by natural order.
Example
import java.util.Collections;
import java.util.List;
public class SortExample {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("example");
names.add("EXAMPLE");
names.add("apple");
names.add("banana");
System.out.println("Before sorting: " + names);
// Sort by natural order (by Unicode code point)
Collections.sort(names);
System.out.println("After sorting: " + names);
}
}
Output result:
排序前: [example, EXAMPLE, apple, banana] 排序后: [EXAMPLE, apple, banana, example]
Custom Comparator Sorting
UsingComparatoryou can sort by any custom rule without modifying the element class itself.
Example: Sort by String Length
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class CustomSortExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("example");
words.add("java");
words.add("algorithm");
words.add("C");
System.out.println("Before sorting: " + words);
// Sort by string length in ascending order
Collections.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
System.out.println("After sorting by length: " + words);
}
}
Output result:
排序前: [example, java, algorithm, C] 按长度排序后: [C, java, example, algorithm]
Java 8+ can use Lambda expressions to simplify the code:
Example: Lambda Syntax
Collections.sort(words, (s1, s2) -> s1.length() - s2.length());
// Or use Comparator.comparingInt
Collections.sort(words, Comparator.comparingInt(String::length));
// Reverse sort
Collections.sort(words, Comparator.reverseOrder());
// Sort by length in reverse order
Collections.sort(words, Comparator.comparingInt(String::length).reversed());
Shuffling
Collections.shuffle()Uses the Fisher-Yates algorithm to randomly shuffle the order of elements in a List.
Example
import java.util.Collections;
import java.util.List;
public class ShuffleExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
numbers.add(i);
}
System.out.println("Original list: " + numbers);
// Randomly shuffle the order
Collections.shuffle(numbers);
System.out.println("First shuffle: " + numbers);
Collections.shuffle(numbers);
System.out.println("Second shuffle: " + numbers);
}
}
Output result:
原始列表: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第一次混排: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6] 第二次混排: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]
Binary Search
Collections.binarySearch()Uses the binary search algorithm to locate a target element in a sorted List.
The time complexity is O(log n), much better than the O(n) of linear traversal.
Important prerequisite: The List must already be sorted in ascending order; otherwise, the result is undefined.
Example
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(30);
numbers.add(20);
numbers.add(50);
numbers.add(40);
// Must sort first
Collections.sort(numbers);
System.out.println("Sorted list: " + numbers);
// Binary search: the return value is the index (>= 0 means found)
int index = Collections.binarySearch(numbers, 30);
System.out.println("Index position of 30: " + index);
// Search for a non-existent element: returns a negative value = -(insertion point) - 1
int notFound = Collections.binarySearch(numbers, 25);
System.out.println("Return value for 25 (not found): " + notFound);
// Insertion point = -(notFound + 1) = 2, so it should be inserted at index 2
}
}
Output result:
排序后列表: [10, 20, 30, 40, 50] 30 的索引位置: 2 25 的返回值（不存在）: -3
When binarySearch() cannot find an element, it returns a negative value, the formula is-(insertion point) - 1The insertion point is the index where the element would be located if it existed. The cleverness of this design is that if the element exists, a non-negative index is returned; if it does not exist, a negative value is inevitably returned, so there is no ambiguity.
Maximum and Minimum
Collections.max()andCollections.min()Returns the maximum/minimum element in a collection according to natural order or a specified comparator.
Example
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class MaxMinExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("example");
words.add("algorithm");
words.add("java");
words.add("code");
// Get maximum and minimum by natural order (lexicographical order)
String maxWord = Collections.max(words);
String minWord = Collections.min(words);
System.out.println("Lexicographically maximum: " + maxWord);
System.out.println("Lexicographically minimum: " + minWord);
// Get maximum and minimum by string length
String longest = Collections.max(words,
Comparator.comparingInt(String::length));
String shortest = Collections.min(words,
Comparator.comparingInt(String::length));
System.out.println("Longest length: " + longest);
System.out.println("Shortest length: " + shortest);
}
}
Output result:
字典序最大: example 字典序最小: algorithm 长度最长: algorithm 长度最短: code
Counting Frequency and Disjoint Check
Collections.frequency()Counts the number of occurrences of a specified element in a collection.
Collections.disjoint()Determines whether two collections have no common elements at all.
Example
import java.util.Collections;
import java.util.List;
public class FrequencyDisjointExample {
public static void main(String[] args) {
List<String> items = new ArrayList<>();
items.add("example");
items.add("java");
items.add("example");
items.add("python");
items.add("example");
// Count the occurrences of "example"
int count = Collections.frequency(items, "example");
System.out.println("\"example\""Occurrences: " + count);
// Check whether the two collections are disjoint
List<String> groupA = new ArrayList<>();
groupA.add("java");
groupA.add("python");
List<String> groupB = new ArrayList<>();
groupB.add("C++");
groupB.add("go");
boolean noCommon = Collections.disjoint(groupA, groupB);
System.out.println("groupA and groupB are disjoint: " + noCommon);
}
}
Output result:
"example" 出现次数: 3 groupA 与 groupB 不相交: true
Immutable Collections and Thread-Safe Wrappers
Collections provides methods to wrap ordinary collections as immutable collections or thread-safe collections.
Immutable Collections (Unmodifiable)
CallingCollections.unmodifiableList()and other methods can create a read-only view.
Any modification operation will throw UnsupportedOperationException.
Thread-Safe Collections (Synchronized)
CallingCollections.synchronizedList()and other methods can create a thread-safe wrapper.
In a multithreaded environment, individual method calls on these collections are safe, but compound operations still require external synchronization.
Example
import java.util.Collections;
import java.util.List;
public class WrapperExample {
public static void main(String[] args) {
List<String> original = new ArrayList<>();
original.add("example");
original.add("java");
// Create an immutable view
List<String> readOnly = Collections.unmodifiableList(original);
System.out.println("Immutable view: " + readOnly);
// readOnly.add("error"); // Executing this will throw an exception
// After the original list is modified, the immutable view also reflects the changes
original.add("python");
System.out.println("After modifying the original: " + readOnly);
// Create a thread-safe wrapper
List<String> syncList = Collections.synchronizedList(
new ArrayList<>());
syncList.add("thread-safe");
// Manual synchronization is required when iterating
synchronized (syncList) {
for (String item : syncList) {
System.out.println(item);
}
}
}
}
Output result:
不可变视图: [example, java] 原始修改后: [example, java, python] thread-safe
An immutable view only prevents modifying the collection through that view; the underlying collection remains mutable. If you need a truly immutable collection, use Java 9+'sList.of()、Set.of()and other methods.
Common Algorithm Operations at a Glance
The following summarizes the calling methods and time complexities of common algorithms in Collections:
| Operation | Method Call | Time Complexity | Prerequisite |
|---|---|---|---|
| Sorting | Collections.sort(list) | O(n log n) | Elements implement Comparable |
| Custom sorting | Collections.sort(list, comp) | O(n log n) | Provide a Comparator |
| Reversing | Collections.reverse(list) | O(n) | None |
| Shuffling | Collections.shuffle(list) | O(n) | None |
| Binary search | Collections.binarySearch(list, key) | O(log n) | The list is sorted |
| Filling | Collections.fill(list, obj) | O(n) | None |
| Copying | Collections.copy(dest, src) | O(n) | dest.size() >= src.size() |
| Maximum | Collections.max(coll) | O(n) | Elements implement Comparable |
| Minimum | Collections.min(coll) | O(n) | Elements implement Comparable |
| Counting frequency | Collections.frequency(coll, obj) | O(n) | None |
| Swapping elements | Collections.swap(list, i, j) | O(1) | The indices are valid |
| Rotating | Collections.rotate(list, distance) | O(n) | None |
Notes
binarySearch() must be called on a sorted list; the result returned for an unsorted list is undefined. If the list contains duplicate elements, there is no guarantee which one will be found.
The wrapper returned by synchronizedXxx() only guarantees atomicity at the level of a single method call. Compound operations (such as if(!list.contains(x)) list.add(x)) still require an external synchronized block.
Difference between sort() and List.sort():
Since Java 8, the List interface has added the sort(Comparator) default method.
list.sort(null) sorts using natural ordering, equivalent to Collections.sort(list).
Both have the same underlying implementation, but list.sort() is more concise in syntax.
Performance comparison suggestions:
For small data volumes (fewer than 100 elements), the performance differences among various algorithms are negligible.
For large data volumes, binarySearch() is far superior to the linear search of indexOf().
When frequent lookups are needed, consider using HashSet instead of List, as the query complexity is O(1).
Other Extensions