Dynamic Arrays and Amortised Growth

When the array is full, it moves into one twice the size, so appends stay cheap on average.

A dynamic array is an array that grows: when it runs out of room, it moves its elements into a larger block of memory. This card covers the difference between its size and its capacity, why doubling the capacity keeps appends cheap on average, and the name for that kind of cost, amortised.

A chat app keeps every message of a conversation in order, and nobody knows how many there will be. A fixed array cannot grow where it is, because the memory after its last cell may already belong to something else. A dynamic array keeps two numbers: its size, the elements it holds, and its capacity, the cells it has reserved. While size is below capacity, an append writes into the next free cell. When size reaches capacity, the array reserves a block twice as large, copies every element across, and then appends.

It is like a family moving house when it outgrows the old one: the move is costly, but it happens rarely, and each move buys room for as many again. The analogy breaks on the schedule, because a family does not double at predictable moments and a dynamic array does exactly that.

Before the trace: appending 1 to 9 to an empty array of capacity 1, how many element copies happen in total?

15, which is 1 + 2 + 4 + 8: one batch each time the array fills.

In the trace, size-1 marks the last element, capacity-1 the last reserved cell, and _ a reserved cell that is still empty.

Appending 1 to 9 from capacity 1

Inputan empty dynamic array with capacity 1 that doubles when it is full

Append 1: a free cell
1. 1size-1capacity-1
Capacity 1 holds the first item with no copy.
Append 2: full, move to capacity 2
1. 1
2. 2size-1capacity-1
Full: copy 1 item into a block of 2. Copies in total: 1.
Append 3: full, move to capacity 4
1. 1
2. 2
3. 3size-1
4. _capacity-1
Full: copy 2 items into a block of 4. Copies in total: 3.
Append 4: a free cell
1. 1
2. 2
3. 3
4. 4size-1capacity-1
A free cell, so no copy. Copies in total: 3.
Append 5: full, move to capacity 8
1. 1
2. 2
3. 3
4. 4
5. 5size-1
6. _
7. _
8. _capacity-1
Full: copy 4 items into a block of 8. Copies in total: 7.
Append 9: full, move to capacity 16
1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9size-1
10. _
11. _
12. _
13. _
14. _
15. _
16. _capacity-1
Full: copy 8 items into a block of 16. Copies in total: 15.

ResultNine appends cost 15 copies in total, fewer than two per append.

Each batch copies everything appended before it, but each doubling also puts the next batch twice as far away. Over n appends the batches are 1 + 2 + 4 + … up to less than n, which adds up to less than 2n. The total work for n appends is therefore O(n), and append costs O(1) amortised: the total over a whole sequence of calls divided by its length. The one append that triggers a move is still O(n) on its own.

Any constant growth factor above 1 keeps that argument; a smaller factor moves more often and leaves fewer cells empty. CPython's list grows by about an eighth (list_resize in listobject.c; a run of Python 3.14.8 measured a ratio of 1.125 between capacities near a million), and Java's ArrayList by half (ArrayList.grow in OpenJDK).

Growing by a fixed number of cells instead is not enough. Adding ten cells at a time makes batches of 10, 20, 30 and so on, about n²/20 copies over n appends, so each append is O(n) amortised.

Doubling is why appending to a Python list or a Java ArrayList is the cheap way to build a sequence whose length nobody knows in advance.

On the Data Structures cheatsheet

← → move through sections and cards