A list that grows
In Python you write items.append(x) as often as you like. You never say how big the list should be. The same is true of push on a JavaScript array and add on a Java ArrayList.
Underneath, though, they all sit on a plain array, and a plain array has a fixed size. It is one block of memory, and the memory just after it usually belongs to something else. It cannot simply be made longer.
So how does a fixed block behave like something that grows without limit?
Grow by copying
Keep some spare room
The array is created larger than it needs to be. Appending means writing into the next free slot, which is instant.
When it is full, make a bigger one
Ask for a new, larger block of memory.
Copy every item across
This is the slow part: one copy per item already stored.
Throw the old block away and carry on
The new array has spare room again.
Such a list is called a dynamic array. The only real decision is: how much bigger?
Why doubling
Suppose the new array had room for just one more item. Then every append would copy everything. A thousand appends would make about half a million copies.
Now double the size each time instead.
0 items in 1 slots
Pink: just copied into a new array. Violet: just appended.
Start. An array with room for 1 item. An array's size is fixed when it is created, so growing means making a new one.
- Appends
- 0
- Resizes
- 0
- Items copied
- 0
- Copies per append
- 0
Most appends cost nothing extra. Now and then one is slow. And the slow ones get rarer exactly as fast as they get bigger: after copying 8 items you get 8 free appends, after copying 16 you get 16.
Example
A million appends
Starting from 1 slot, the sizes go 1, 2, 4, 8, and so on. After 20 doublings the array has 1,048,576 slots, enough for a million items.
The copies add up to 1 + 2 + 4 + ... + 524,288 = 1,048,575.
A million appends, about a million copies: roughly one copy per item, and never more than two. Not a thousand, not half a million.
This is what people mean when they say append is O(1) amortized. Any single append might be slow, but averaged over all of them the cost per append is a small constant.
What each operation costs
| Operation | Cost | Why |
|---|---|---|
Read or write position i | One step | Positions are side by side, so the address is simple arithmetic |
| Append at the end | One step on average | Free slot most of the time, an occasional copy |
| Insert or remove at the front or middle | Up to one step per item | Everything after it has to shift |
| Search for a value | Up to one step per item | No shortcut unless it is sorted |
items = []
for i in range(1_000_000):
items.append(i) # about 1 copy each, on average
items.insert(0, "x") # slow: shifts a million itemsKey takeaways
- A dynamic array is a fixed array with spare room, replaced by a bigger one when it fills.
- Growing means copying every item, which is slow.
- Doubling the size makes resizes rare enough that the average cost per append is under two copies.
- Reading by position and appending are fast. Inserting at the front or middle is slow.