skip to content

Why are insertion and removal in the middle of an ArrayList O(n), and when does that matter?

level: middleimportance: should knowfreq 70%

answer

  1. Contiguous, no gaps -> must shift to edit middle
  2. Insert i: shift right; remove i: shift left (System.arraycopy)
  3. Cost = size - i elements moved -> O(n)
  4. End is the fast case (O(1) amortized)
  5. Prefer ArrayDeque for ends; removeIf for bulk delete

basics

~20 s

To insert or remove in the middle, ArrayList has to shift every element after that spot by one position so there are no gaps. The more elements after the spot, the more shifting, so it costs O(n).

solid answer

~50 s

ArrayList stores elements contiguously in an array with no gaps. Inserting at index i means making room: every element from i to the end is shifted one slot to the right (via System.arraycopy), then the new value is placed at i. Removing at index i shifts everything after i one slot left to close the gap. Both touch up to n elements, so they are O(n); near the front the cost is highest, near the end it is cheap. Appending at the end is the special fast case (O(1) amortized). If your workload does many middle or front insertions/removals, ArrayList is a poor fit; consider an ArrayDeque for ends, or restructure to append-and-sort, or batch with removeIf which compacts in a single pass. LinkedList has O(1) splicing only once you already hold the node, but finding the position is O(n), so it rarely wins in practice.

go deeper

for a junior

Knows that adding/removing in the middle is slower than at the end because items have to move.

for a middle

Explains shifting via System.arraycopy, the size - i cost, O(n) complexity, and that the end is the O(1) exception.

for a senior

Quantifies when it matters (large lists, front/middle churn), recommends ArrayDeque/removeIf/build-then-sort, and debunks the LinkedList myth with cache reasoning.

for a principal

Chooses data structures by access pattern at scale, reasons about quadratic blow-ups in hot paths, and weighs cache locality vs theoretical complexity in real benchmarks.

## The core constraint: no gaps ArrayList keeps its `size` elements packed into the first `size` slots of its backing array, **contiguously and with no holes**. Index `i` must always be the i-th element. This packing is what makes `get(i)` O(1) — but it is also why middle edits are expensive. ## Inserting at index i `add(i, value)` must place `value` at slot `i` while preserving every existing element. But slot `i` is occupied. So ArrayList: 1. Ensures capacity (may trigger a resize, see the growth question). 2. **Shifts** elements `i, i+1, ..., size-1` each one position to the **right**, using `System.arraycopy` (a fast bulk memory move, but still proportional to how many elements moved). 3. Writes `value` into slot `i` and increments `size`. The number of elements shifted is `size - i`. Insert at the **front** (`i = 0`) shifts everything → O(n). Insert at the **end** shifts nothing → O(1). ## Removing at index i `remove(i)` leaves a hole at `i`. To keep things contiguous it **shifts** elements `i+1, ..., size-1` one position **left**, overwriting the hole, then nulls the now-unused last slot (to let GC reclaim it) and decrements `size`. Again it moves `size - i - 1` elements → O(n), cheapest at the end. ```java List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40)); list.add(1, 99); // shifts 20,30,40 right -> [10,99,20,30,40] list.remove(0); // shifts 99,20,30,40 left -> [99,20,30,40] ``` ## Why 'O(n)' and when it matters **O(n)** means the work grows linearly with list size. For a 10-element list nobody cares. For a 1,000,000-element list, repeated front insertions become quadratic overall (O(n) each x n operations = O(n^2)) and can dominate runtime. It matters when your access pattern is **insert/remove in the middle or front, frequently, on a large list**. It does NOT matter for the common pattern of *append to the end and read by index*. ## Better options for those patterns - **Ends only**: `ArrayDeque` gives O(1) add/remove at both head and tail. - **Bulk removal by predicate**: `list.removeIf(pred)` compacts in a **single O(n) pass** instead of O(n) per removed element — far better than removing one-by-one in a loop. - **Build-then-sort**: if order is derivable, append (O(1)) then sort once (O(n log n)) instead of inserting in sorted position repeatedly. - **LinkedList caveat**: a linked list can splice in O(1) *given the node*, but you must first **walk** to the position (O(n)), and its poor cache locality usually makes it slower than ArrayList in real benchmarks. It is rarely the right answer. ## Gotcha: removing in a for-loop Removing while iterating by index causes you to skip elements (indices shift under you) and is O(n^2). Use an `Iterator.remove()` or `removeIf` instead.

  • Is removing from the end of an ArrayList also O(n)?
    No. Removing the last element shifts nothing — it just nulls the last slot and decrements size, so it is O(1).
  • How should you delete many elements matching a condition?
    Use removeIf(predicate), which compacts the array in a single O(n) pass, instead of remove() in a loop which is O(n) per removal and risks index-skipping.

saying these in an interview costs you the question

  • Saying middle insert/remove is O(1)
  • Claiming LinkedList is always faster for inserts (position lookup is O(n), cache-hostile)
  • Removing elements in an index for-loop (skips items, O(n^2))
  • Forgetting that end operations are the cheap exception
  • Confusing the resize cost with the shift cost — they are separate

context

resolving links…