Reverse Internals: How Swapping Works
You'll learn how Collections.reverse() efficiently reverses a list using an elegant two-pointer swapping algorithm.
The Core Algorithm
When you call Collections.reverse(list), Java doesn't create a new list or shift every element one by one. Instead, it uses a two-pointer approach that swaps elements from opposite ends, moving inward until the pointers meet in the middle.
Think of it like two people standing at opposite ends of a line of chairs, swapping the first chair with the last, then stepping inward to swap the second with the second-to-last, and continuing until they meet in the center.
How It Works Step-by-Step
- Initialize two pointers: one at index
0(start), one atlist.size() - 1(end) - Swap elements at these positions
- Move pointers inward: increment start, decrement end
- Repeat until start >= end (they cross or meet)
For a list of size n, this performs exactly n/2 swaps. A 10-element list? Just 5 swaps needed.
Complexity Analysis
- Time Complexity: O(n/2), which simplifies to O(n)—you visit roughly half the elements, but each swap touches two positions
- Space Complexity: O(1)—only two pointer variables needed, no matter how large the list
- In-place operation: The original list is modified directly; no extra memory for a copy
This is far more efficient than creating a new reversed list (which would need O(n) extra space) or repeatedly removing and reinserting elements.
Key Takeaway: Collections.reverse() uses a two-pointer swapping algorithm that achieves O(n) time with O(1) space, making it both fast and memory-efficient by working in-place.