Rotate Internals: Reversal Algorithm
What you'll learn: How Collections.rotate achieves efficient circular shifting using a clever three-reversal technique instead of expensive element-by-element moves.
When you call Collections.rotate(list, distance), you might expect it to move each element one-by-one in a loop, requiring temporary storage. But Java uses a brilliant algorithm that needs no extra space and runs in O(n) time through three reversals.
The Three-Reversal Trick
The algorithm works like this:
- Reverse the entire list
- Reverse the first k elements (where k is the effective rotation distance)
- Reverse the remaining elements
Think of it like rearranging a deck of cards: instead of dealing them out and picking them back up in order, you flip the whole deck, then flip the top portion, then flip the bottom portion—and magically they're rotated!
Example Walkthrough
Rotating [1, 2, 3, 4, 5] by distance 2 (shift right by 2):
Step 1: Reverse entire list → [5, 4, 3, 2, 1]
Step 2: Reverse first 2 elements → [4, 5, 3, 2, 1]
Step 3: Reverse last 3 elements → [4, 5, 1, 2, 3]
Result: [4, 5, 1, 2, 3] ✓ (elements rotated right by 2)
Why This Matters
- O(1) space: Only swaps elements in-place, no temporary arrays
- O(n) time: Each element touched exactly three times
- Elegant: Works for any distance (positive or negative) after normalizing
The reversal algorithm is a classic computer science technique that transforms what seems like a complex shifting problem into three simple flip operations.
Key Takeaway: Collections.rotate uses three list reversals to achieve circular shifting in linear time with constant space—a clever alternative to moving elements one position at a time.