WalkthroughDifficulty: Intermediate2 min

How an ArrayList Grows When Its Array Is Full

Zero slots, then ten, then fifteen: growth is a copy, spread so thinly that appending stays cheap.

An ArrayList is backed by an array, and an array cannot change length. When the array is full, the list allocates a larger one, copies every element across, and carries on. Following it step by step explains why appending is cheap on average and why sizing a list ahead helps.

You start with an empty ArrayList and add elements one at a time.

From an empty list to one that has outgrown its array

new ArrayList<>() allocates nothing

java

List<String> refs = new ArrayList<>();

The backing array is a shared, empty one. Capacity is zero, and a list nobody ever adds to costs almost nothing, which matters when a program holds thousands of them.

The first add allocates ten slots

java

refs.add("A");

Ten is the default initial capacity. Size is now one and capacity is ten, so the next nine adds cost nothing but a write.

The eleventh add finds the array full

There is no eleventh slot and no way to lengthen the array. The list allocates a new array about half as long again, which is fifteen slots.

Every element is copied across

Ten elements are copied from the old array into the new one, the list points at the new array, and the old one becomes garbage. Only then does the eleventh element go in.

Growth happens less and less often

Capacity after each growth, from the default start
Growth	Capacity
Initial	10
First	15
Second	22
Third	33

Because capacity grows by a proportion rather than a fixed amount, the copies get further apart as the list grows. Averaged over many adds, appending costs a constant amount, which is why add is cheap despite occasionally copying everything.

Growth is a copy, and its cost is spread thinly. When you know the final size, new ArrayList<>(50_000) allocates it once and skips every copy in the table. You know the steps are right when size() and the capacity differ: size is how many elements you added, and capacity is how many fit before the next copy.

← → move through sections and cards