Pointer Walk

Dynamic Arrays

A million appends need only twenty resizes. Why doubling keeps the copying under two copies per item.

Data StructuresBeginner7 min read

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

  1. 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.

  2. When it is full, make a bigger one

    Ask for a new, larger block of memory.

  3. Copy every item across

    This is the slow part: one copy per item already stored.

  4. 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.

A dynamic array that doubles when fullInteractive

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

OperationCostWhy
Read or write position iOne stepPositions are side by side, so the address is simple arithmetic
Append at the endOne step on averageFree slot most of the time, an occasional copy
Insert or remove at the front or middleUp to one step per itemEverything after it has to shift
Search for a valueUp to one step per itemNo shortcut unless it is sorted
python
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 items

Key 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress