Time Complexity: Insertion in Middle
What you'll learn: You'll understand why inserting an element in the middle of a list has O(n) complexity for both ArrayList and LinkedList, but for different reasons.
The Surprising Truth
Both ArrayList and LinkedList take linear time O(n) to insert an element in the middle, but their bottlenecks differ completely.
ArrayList: The Shifting Problem
When you insert an element at an arbitrary index in an ArrayList, you must shift all subsequent elements to make room. Since the backing array has contiguous memory, this requires moving approximately n/2 elements on average.
Example: Inserting at index 2 in a size-5 ArrayList:
// Before: [A, B, C, D, E]
list.add(2, "X");
// After: [A, B, X, C, D, E]
// Elements C, D, E had to shift right
The System.arraycopy operation moves all elements after the insertion point, giving us O(n) time complexity.
LinkedList: The Traversal Problem
LinkedList doesn't need to shift elements—it just rewires node references. But to insert at a specific index, you must traverse from head or tail to find that position. With n elements, reaching the middle requires visiting approximately n/2 nodes.
Analogy: Like finding the 50th person in a conga line—you must walk past everyone ahead of them, even though adding them only means linking hands.
The Verdict
Both implementations are O(n) for middle insertion:
- ArrayList: O(1) to find position + O(n) to shift elements
- LinkedList: O(n) to find position + O(1) to rewire references
Neither structure optimizes middle insertions—if this is your primary operation, consider specialized data structures.
Key Takeaway: Both ArrayList and LinkedList have O(n) time complexity for middle insertion—ArrayList due to element shifting, LinkedList due to traversal—making neither ideal for frequent insertions at arbitrary positions.