skip to content

Explain why ArrayList's add() at the end is described as 'amortized O(1)' and what happens when the backing array fills up.

level: middleimportance: should knowfreq 50%

answer

  1. Capacity (slots) vs size (elements)
  2. Full → allocate ~1.5x array + System.arraycopy (O(n))
  3. Geometric growth → total copy work O(n) over n adds → O(1) average
  4. Single add worst case O(n); amortized O(1)
  5. Pre-size with constructor/ensureCapacity to skip resizes

basics

~20 s

ArrayList keeps a fixed-size array inside. Adding is instant until it's full; then it makes a bigger array (about 1.5x) and copies everything over. That copy is occasional and spread across many cheap adds, so on average each add is constant time.

solid answer

~50 s

ArrayList is backed by an array of fixed capacity. Appending is O(1) while there's room — it just writes to the next slot. When the array is full, ArrayList grows it: it allocates a new, larger array (roughly 1.5x the old size) and copies all existing elements over, which is an O(n) operation for that one add. But because capacity grows geometrically, these resize-and-copy events become exponentially rarer as the list grows. Summed over n appends, the total copying work is proportional to n, so the average cost per append is constant — that's the meaning of 'amortized O(1).' Any single add can be O(n) (the one that triggers a resize), but the average over a sequence is O(1). If you know the final size, calling the capacity constructor or ensureCapacity avoids the intermediate resizes entirely.

go deeper

for a junior

Knows ArrayList grows by making a bigger array and copying when full, and that adding is usually fast.

for a middle

Explains amortized O(1) via geometric growth, distinguishes capacity from size, and knows to pre-size for bulk loads.

for a senior

Derives the geometric-series argument, contrasts with linear growth's O(n^2), distinguishes single-op worst case from amortized, and reasons about latency jitter from a large resize.

for a principal

Considers amortized cost in latency budgets and GC/allocation impact at scale, sets guidance on pre-sizing hot paths, and can compare growth strategies and their memory-vs-copy tradeoffs.

## What 'capacity' means `ArrayList` is backed by a plain Java array, which has a **fixed length** once created. The number of slots is the **capacity**; the number of elements actually stored is the **size**. Capacity is always >= size, with the difference being unused growth headroom. ## The fast path When you call `add(x)` and `size < capacity`, ArrayList simply writes `x` into the next free slot and increments size. That's a constant-time, O(1) operation — no matter how many elements already exist. ## What happens when it's full (size == capacity) A Java array can't be resized in place, so ArrayList must: 1. Allocate a **new, larger array** — Java's implementation grows by about **1.5x** (`oldCapacity + (oldCapacity >> 1)`). 2. **Copy** all existing elements from the old array into the new one (a fast `System.arraycopy`, but still O(n) work). 3. Drop the old array and write the new element. That particular `add` therefore costs O(n). The old array becomes garbage for the GC to reclaim. ## Why the average is still O(1): amortized analysis **Amortized analysis** averages the cost of an operation over a whole sequence, so that occasional expensive operations are 'paid for' by many cheap ones. The key is **geometric (multiplicative) growth**. Because capacity multiplies by ~1.5 each time, resizes happen at sizes like 10, 15, 22, 33, 49... — exponentially farther apart. To reach n elements you copy roughly n + n/1.5 + n/1.5^2 + ... elements total, a **geometric series** that sums to a constant multiple of n (about 3n). So n appends do O(n) total work, meaning **O(1) per append on average**. Contrast with a naive 'grow by +1 each time' strategy: every add would copy everything, giving 1 + 2 + ... + n = O(n^2) total — O(n) per add. Geometric growth is what rescues the amortized bound. ## Worst-case vs amortized It's important to distinguish: - **Single-operation worst case:** O(n) (the add that triggers a resize). - **Amortized (average over a sequence):** O(1). This matters for latency-sensitive code: a particular append can stall while copying a huge array, even though the average is great. If you can't tolerate that jitter, pre-size. ## Pre-sizing to avoid resizes If you know roughly how many elements you'll add, create the list with that capacity (`new ArrayList<>(expectedSize)`) or call `ensureCapacity(n)`. This allocates the array once up front, eliminating intermediate resize-and-copy cycles and the resulting garbage — a cheap, common optimization for large bulk loads. ## Relation to the LinkedList comparison LinkedList never resizes a backing array (it has none) — each `add` allocates one node, which is O(1) but allocates more and scatters memory. ArrayList trades occasional bulk copies for compact, contiguous storage and far better iteration speed, which is why it's still the default despite the resize cost.

  • Why does geometric growth (x1.5) give amortized O(1) but linear growth (+1) does not?
    With geometric growth the total elements copied across all resizes form a converging geometric series summing to O(n), so per-add it's O(1). Linear growth copies the whole array on nearly every add, totaling 1+2+...+n = O(n^2), i.e. O(n) per add.
  • How would you avoid resize overhead when loading a million known elements?
    Construct with the expected capacity (new ArrayList<>(1_000_000)) or call ensureCapacity before the loop, so the array is allocated once and no intermediate resize-and-copy or garbage occurs.

saying these in an interview costs you the question

  • Saying every add is O(1) worst-case (the resizing add is O(n))
  • Saying add is O(n) in general (it's amortized O(1))
  • Thinking the array is resized in place
  • Claiming growth is +1 each time (that would be O(n^2) total)
  • Not knowing you can pre-size to avoid resizes

context

resolving links…