Course contentsShow
← Java
Lesson 1236 of 2,87028. Collections Utility ClassFree lesson

Rotate Internals: Reversal Algorithm

See how rotate uses three reversals to achieve O(n) time and O(1) space circular shifting.

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:

  1. Reverse the entire list
  2. Reverse the first k elements (where k is the effective rotation distance)
  3. 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.