Course contentsShow
← Java
Lesson 1040 of 2,87024. List ImplementationsFree lesson

Time Complexity: Insertion in Middle

ArrayList requires shifting elements O(n); LinkedList requires traversal O(n) but no shifting.

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.