YouTipJava Collection Algorithms
Java Collection Algorithms | Rookie Tutorial
Java collection algorithms refer to a set of static methods provided in the java.util.Collections class, used to perform common operations such as sorting, searching, shuffling, and filling on collections (List, Set, Map, etc.).
These algorithms are built into the JDK, highly optimized, and developers can call them directly without writing from scratch.
* * *
## Collections Algorithm Overview
java.util.Collections is a utility class where all methods are static, similar to the Arrays utility class for operating on arrays.
The following table lists the most commonly used collection algorithms and their purposes:
| Algorithm Category | Method Name | Function Description |
| --- | --- | --- |
| Sorting | sort() | Sort List in ascending order |
| Shuffling | shuffle() | Randomly shuffle the order of elements in List |
| Reversing | reverse() | Reverse the order of elements in List |
| Binary Search | binarySearch() | Binary search for specified element in sorted List |
| Filling | fill() | Replace all elements in List with specified element |
| Copying | copy() | Copy elements from one List to another List |
| Max/Min Value | max() / min() | Return the maximum or minimum element in collection |
| Frequency Count | frequency() | Return the number of times specified element appears in collection |
| Disjoint Check | disjoint() | Check if two collections have no common elements |
| Immutable Collection | unmodifiableXxx() | Return read-only view of collection |
| Thread Safety | synchronizedXxx() | Return thread-safe collection wrapper |
* * *
## Sorting
Collections.sort() is the most commonly used collection algorithm, arranging elements in List in ascending order.
The underlying implementation uses an optimized merge sort (TimSort) with time complexity of O(n log n), providing stable performance.
The sorting process is shown in the figure below:
### Natural Order Sorting
After the element class implements the Comparable interface, sort() can be called directly to arrange in natural order.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortExample {
public static void main(String[] args){
List names =new ArrayList<>();
names.add("tutorial");
names.add("TUTORIAL");
names.add("apple");
names.add("banana");
System.out.println("Before sorting: "+ names);
// Natural order sorting (by Unicode code point)
Collections.sort(names);
System.out.println("After sorting: "+ names);
}
}
Output:
Before sorting: [tutorial, TUTORIAL, apple, banana]After sorting: [TUTORIAL, apple, banana, tutorial]
### Custom Comparator Sorting
Using Comparator allows sorting by any custom rule without modifying the element class itself.
## Example: Sort by String Length
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class CustomSortExample {
public static void main(String[] args){
List words =new ArrayList<>();
words.add("tutorial");
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(){
@Override
public int compare(String s1, String s2){
return s1.length()- s2.length();
}
});
System.out.println("After sorting by length: "+ words);
}
}
Output:
Before sorting: [tutorial, java, algorithm, C]After sorting by length: [C, java, tutorial, algorithm]
Java 8+ can use Lambda expressions for simplified syntax:
## Example: Lambda Syntax
// Lambda expression sorting by length
Collections.sort(words, (s1, s2)-> s1.length()- s2.length());
// Or use Comparator.comparingInt
Collections.sort(words, Comparator.comparingInt(String::length));
// Reverse order
Collections.sort(words, Comparator.reverseOrder());
// Reverse order by length
Collections.sort(words, Comparator.comparingInt(String::length).reversed());
* * *
## Shuffling
Collections.shuffle() uses the Fisher-Yates algorithm to randomly shuffle the order of elements in List.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ShuffleExample {
public static void main(String[] args){
List numbers =new ArrayList<>();
for(int i =1; i <=10; i++){
numbers.add(i);
}
System.out.println("Original list: "+ numbers);
// Randomly shuffle order
Collections.shuffle(numbers);
System.out.println("First shuffle: "+ numbers);
Collections.shuffle(numbers);
System.out.println("Second shuffle: "+ numbers);
}
}
Output:
Original list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]First shuffle: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6]Second shuffle: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]
* * *
## Binary Search
Collections.binarySearch() locates target elements in sorted List using binary search algorithm.
Time complexity is O(log n), far superior to linear traversal's O(n).
Important prerequisite: List must be sorted in ascending order, otherwise results are undefined.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args){
List 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: return value is index (>= 0 means found)
int index =Collections.binarySearch(numbers, 30);
System.out.println("Index of 30: "+ index);
// Search for non-existent element: returns negative value = -(insertion point) - 1
int notFound =Collections.binarySearch(numbers, 25);
System.out.println("Return value for 25 (not exists): "+ notFound);
// Insertion point = -(notFound + 1) = 2, should be inserted at index 2
}
}
Output:
Sorted list: [10, 20, 30, 40, 50]Index of 30: 2Return value for 25 (not exists): -3
> When binarySearch() cannot find the element, it returns a negative value calculated as -(insertion point) - 1. The insertion point is the index where the element would be if it existed. The cleverness of this design is: if element exists, non-negative index is returned; if not, negative value is guaranteed, eliminating ambiguity.
* * *
## Maximum and Minimum Values
Collections.max() and Collections.min() return the maximum/minimum element in collection by natural order or specified comparator.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class MaxMinExample {
public static void main(String[] args){
List words =new ArrayList<>();
words.add("tutorial");
words.add("algorithm");
words.add("java");
words.add("code");
// Get maximum and minimum by natural order (lexicographical)
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:
Lexicographically maximum: tutorial Lexicographically minimum: algorithm Longest length: algorithm Shortest length: code
* * *
## Frequency Count and Disjoint Check
Collections.frequency() counts the number of times a specified element appears in collection.
Collections.disjoint() checks if two collections have no common elements at all.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class FrequencyDisjointExample {
public static void main(String[] args){
List items =new ArrayList<>();
items.add("tutorial");
items.add("java");
items.add("tutorial");
items.add("python");
items.add("tutorial");
// Count occurrences of "tutorial"
int count =Collections.frequency(items, "tutorial");
System.out.println("\"tutorial\" occurrences: "+ count);
// Check if two collections are disjoint
List groupA =new ArrayList<>();
groupA.add("java");
groupA.add("python");
List 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:
"tutorial" occurrences: 3 groupA and groupB are disjoint: true
* * *
## Immutable Collections and Thread-Safe Wrappers
Collections provides methods to wrap ordinary collections into immutable or thread-safe collections.
### Immutable Collections (Unmodifiable)
Calling Collections.unmodifiableList() and similar methods creates a read-only view.
Any modification operation will throw UnsupportedOperationException.
### Thread-Safe Collections (Synchronized)
Calling Collections.synchronizedList() and similar methods creates a thread-safe wrapper.
Individual method calls on these collections in multi-threaded environments are safe, but compound operations still require external synchronization.
## Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class WrapperExample {
public static void main(String[] args){
List original =new ArrayList<>();
original.add("tutorial");
original.add("java");
// Create immutable view
List readOnly =Collections.unmodifiableList(original);
System.out.println("Immutable view: "+ readOnly);
// readOnly.add("error"); // Execution would throw exception
// After original list is modified, immutable view also reflects changes
original.add("python");
System.out.println("After original modification: "+ readOnly);
// Create thread-safe wrapper
List syncList =Collections.synchronizedList(
new ArrayList<>());
syncList.add("thread-safe");
// Iteration requires manual synchronization
synchronized(syncList){
for(String item : syncList){
System.out.println(item);
}
}
}
}
Output:
Immutable view: [tutorial, java]After original modification: [tutorial, java, python] thread-safe
> Immutable views only prevent modification through that view; the underlying collection remains mutable. For truly immutable collections, use Java 9+ methods like List.of(), Set.of(), etc.
* * *
## Common Algorithm Operations Overview
The following summarizes the calling methods and time complexity of commonly used algorithms in Collections:
| Operation | Method Call | Time Complexity | Prerequisites |
| --- | --- | --- | --- |
| Sorting | Collections.sort(list) | O(n log n) | Elements implement Comparable |
| Custom Sorting | Collections.sort(list, comp) | O(n log n) | Provide Comparator |
| Reversing | Collections.reverse(list) | O(n) | None |
| Shuffling | Collections.shuffle(list) | O(n) | None |
| Binary Search | Collections.binarySearch(list, key) | O(log n) | 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 |
| Frequency Count | Collections.frequency(