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

Reverse Internals: How Swapping Works

Understand the algorithm: two-pointer approach with O(n/2) swaps and O(1) space complexity.

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

  1. Initialize two pointers: one at index 0 (start), one at list.size() - 1 (end)
  2. Swap elements at these positions
  3. Move pointers inward: increment start, decrement end
  4. 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.