Array Copying During Resize: System.arraycopy
What you'll learn: You'll understand the O(n) performance cost incurred when ArrayList resizes and must copy all existing elements to a new, larger array.
The Core Problem
When an ArrayList exhausts its capacity and needs to grow, Java can't simply "expand" the existing array—arrays have fixed sizes. Instead, ArrayList must:
- Allocate a completely new, larger array (typically 1.5x the old capacity)
- Copy every single element from the old array to the new one
- Replace the internal reference to point to the new array
This copying step is performed by System.arraycopy(), a native method optimized for speed but still fundamentally limited by the number of elements that must be moved.
Why This Matters: O(n) Cost
Copying all existing elements takes time proportional to the number of elements—that's O(n) complexity. If your ArrayList has 10,000 elements when it needs to resize, all 10,000 references must be copied to the new array. That's not free.
Analogy: Imagine moving to a bigger apartment. No matter how well-organized you are, you still need to physically move every single box from the old place to the new one. More boxes = more trips = more time.
The Impact
While a single add() operation usually runs in O(1) time (just placing an element), the occasional resize operation costs O(n). Over many operations, this "amortizes" to O(1) average, but individual resize operations can cause noticeable performance hiccups in time-sensitive code.
Understanding this cost explains why specifying an appropriate initial capacity (when you know roughly how many elements you'll need) can significantly improve performance by avoiding multiple expensive resize operations.
Key Takeaway: Resizing an ArrayList requires copying all n existing elements via System.arraycopy(), an O(n) operation that makes resize steps temporarily expensive despite add()'s usual O(1) performance.