skip to content

How does an ArrayList grow when it runs out of space, and what is the cost?

level: middleimportance: must knowfreq 80%

answer

  1. size vs capacity
  2. Full → allocate bigger array + copy (Arrays.copyOf)
  3. ~1.5x growth (oldCap + oldCap>>1)
  4. Single resize O(n), append O(1) amortized
  5. Geometric growth = constant amortized; pre-size to avoid churn

basics

~20 s

When the internal array is full and you add an item, ArrayList makes a bigger array (about 1.5x), copies everything over, then adds the new item. That copy is occasional, so adding is fast on average.

solid answer

~40 s

ArrayList keeps a backing array whose length is its capacity. When add() is called and size equals capacity, it grows: in the OpenJDK implementation the new capacity is roughly oldCapacity + (oldCapacity >> 1), i.e. about 1.5x, then Arrays.copyOf copies the existing elements into the new array. A single resize is O(n) because of the copy, but resizes happen geometrically rarely, so appending is O(1) amortized — averaged over many adds, each add costs constant time. The geometric (multiplicative) growth is what makes it amortized constant; growing by a fixed amount would make appends O(n) amortized. If you know the final size, call new ArrayList<>(capacity) or ensureCapacity() to pre-size and avoid repeated copies and garbage.

code

java · 8 lines
java
// Pre-size to avoid repeated grow-and-copy
List<Integer> nums = new ArrayList<>(100_000);
for (int i = 0; i < 100_000; i++) {
    nums.add(i); // no resize: capacity allocated once
}

// Without pre-sizing, the backing array would be copied
// ~30 times (10 -> 15 -> 22 -> ... ) as it grows ~1.5x each time.

go deeper

for a junior

Knows the array gets bigger and elements are copied when it fills up, and that adding is usually fast.

for a middle

States ~1.5x growth, the copy cost, and that append is O(1) amortized; knows about initial capacity.

for a senior

Explains amortized analysis via the geometric series, contrasts with fixed-increment growth, and knows trimToSize/ensureCapacity trade-offs.

for a principal

Reasons about allocation/GC pressure of resizing in hot paths, capacity tuning under load, and when growth-factor choice (1.5x vs 2x) affects memory headroom vs copy frequency.

## The problem: a fixed array, an unknown count ArrayList is built on a plain array, and Java arrays cannot grow. So ArrayList separates two numbers: - **size** — how many elements you have stored. - **capacity** — how many the current backing array can hold (its length). When `size < capacity`, an `add()` just drops the element into the next free slot — O(1). ## What happens when it is full When `size == capacity` and you call `add()`, there is no free slot, so ArrayList must **grow**: 1. Compute a new, larger capacity. 2. Allocate a brand-new array of that size. 3. **Copy** all existing elements from the old array into the new one (`Arrays.copyOf`, internally `System.arraycopy`). 4. Replace the reference; the old array becomes garbage. 5. Store the new element. Step 3 touches every element, so a single grow is **O(n)**. ## The growth factor (~1.5x) In OpenJDK the new capacity is `oldCapacity + (oldCapacity >> 1)`. `>> 1` is an integer right-shift = divide by 2, so this is roughly **1.5 times** the old capacity. (Exact constant is an implementation detail — do not quote it as guaranteed; "about 1.5x" is the safe answer. Other languages/libraries use 2x.) From an empty default ArrayList the array is lazily allocated at length 10 on first add. ## Why appends are O(1) *amortized* **Amortized** means averaged over a long sequence of operations. Most adds are cheap O(1); the expensive O(n) copies happen only when crossing a capacity boundary, and because capacity **multiplies** (geometric growth), those boundaries get exponentially farther apart. Total copy work to reach n elements is n + n/1.5 + n/1.5^2 + ... which is a geometric series summing to a constant multiple of n — so total work is O(n) for n adds, i.e. **O(1) per add on average**. If instead the array grew by a fixed +k each time, you would copy on roughly every k adds, giving total work proportional to n^2 — **O(n) amortized per add**. Geometric growth is the whole trick. ## Practical control: pre-sizing If you know (even roughly) how many elements you'll store: ```java List<Integer> nums = new ArrayList<>(10_000); // pre-size capacity // or, on an existing list: ((ArrayList<Integer>) nums).ensureCapacity(10_000); ``` This allocates once, avoids the repeated grow-and-copy churn, and reduces garbage and CPU. It does **not** change `size` — the list is still empty until you add. ## Note on shrinking ArrayList does **not** shrink automatically when you remove elements; capacity stays. Call `trimToSize()` to release unused capacity if memory matters.

  • Why is append amortized O(1) rather than O(n)?
    Because capacity grows geometrically (~1.5x), the rare O(n) copies are exponentially spaced; the total copy work for n adds sums (geometric series) to O(n), so each add averages constant time.
  • How do you avoid repeated resizing when you know the size?
    Construct with an initial capacity (new ArrayList<>(n)) or call ensureCapacity(n) before bulk-adding, so the array is allocated once.

saying these in an interview costs you the question

  • Saying every add() is O(n)
  • Claiming growth is exactly 2x in Java (that's other languages; OpenJDK is ~1.5x)
  • Saying ArrayList shrinks automatically on remove
  • Confusing capacity with size
  • Forgetting that amortized analysis is why appends are 'constant'

context

resolving links…