AlgoScope

Dynamic Array

structurebeginnerTime O(1) amortizedSpace O(n)

When the array fills up it allocates one twice as big and copies everything over. Most appends cost nothing, the occasional one is expensive, and the average works out constant.

01

Start with capacity 2. Append 5 values; when the array is full, double it.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.

  1. Size 0, capacity 2. Appending 3: what happens?

    • Fits, append
    • Full, grow first

    Answer: Fits, append. There is room, so 3 is written straight into slot 0.

  2. Size 1, capacity 2. Appending 8: what happens?

    • Fits, append
    • Full, grow first

    Answer: Fits, append. There is room, so 8 is written straight into slot 1.

  3. Size 2, capacity 2. Appending 1: what happens?

    • Fits, append
    • Full, grow first

    Answer: Full, grow first. The array is full, so it grows to 4 first.

  4. Size 3, capacity 4. Appending 6: what happens?

    • Fits, append
    • Full, grow first

    Answer: Fits, append. There is room, so 6 is written straight into slot 3.

  5. Size 4, capacity 4. Appending 9: what happens?

    • Fits, append
    • Full, grow first

    Answer: Full, grow first. The array is full, so it grows to 8 first.

How it runs, step by step

  1. Start with capacity 2. Append 5 values; when the array is full, double it.

    Empty dynamic array with capacity 2. Appending 5 values one at a time.

  2. Append 3 at index 0. Size 1 of 2.

    3 appended at index 0. Size is now 1 of capacity 2.

  3. Append 8 at index 1. Size 2 of 2.

    8 appended at index 1. Size is now 2 of capacity 2.

  4. Full (2 of 2). Allocate 4 slots and copy the 2 existing values across.

    The array is full at 2 of 2. Capacity doubles to 4; 2 values are copied.

  5. Append 1 at index 2. Size 3 of 4.

    1 appended at index 2. Size is now 3 of capacity 4.

  6. Append 6 at index 3. Size 4 of 4.

    6 appended at index 3. Size is now 4 of capacity 4.

  7. Full (4 of 4). Allocate 8 slots and copy the 4 existing values across.

    The array is full at 4 of 4. Capacity doubles to 8; 4 values are copied.

  8. Append 9 at index 4. Size 5 of 8.

    9 appended at index 4. Size is now 5 of capacity 8.

  9. 5 appends cost 6 copies over 2 resizes. Total work stays under 3n: amortized O(1) per append.

    Result: 5 values appended with 6 copies during 2 resizes. Amortized cost per append is constant.

Remember

  • Doubling means the total copies never exceed 2n, so n appends cost under 3n work.
  • A single append can cost O(n). Averaged over many appends it is O(1).
  • This is what ArrayList, Vector and Python lists do underneath.

Topics covered

Related

Where this is used

Language runtimesGo slices

A slice is a three-word header holding a pointer, a length and a capacity, and append writes straight into the spare capacity whenever there is room. When there is none the runtime's growslice allocates a larger backing array and copies into it, which is why append returns a new slice header instead of mutating the old one in place, and why discarding that return value loses the write. The size growslice asks for is then rounded up to one of the allocator's size classes, so the capacity you read back after an append is often a little larger than the growth rule alone would give.

Systems programmingstd::vector in C++

vector is the default sequence container because its elements stay in one contiguous block, so it can be passed to a C API or streamed through cache exactly like a fixed array. Keeping spare capacity is what makes that affordable: most push_back calls are a single write, and a new block is allocated only when the spare runs out. reserve(n) exists for the case where the final size is already known, so the program buys the whole block once and skips every reallocation and copy on the way up.

DatabasesRedis strings

Redis strings are SDS buffers, and sdsMakeRoomFor deliberately over-allocates rather than sizing to the exact length, so an APPEND command or a reply buffer being filled byte by byte does not call realloc on every write. The policy is geometric only while that is cheap: under 1 MB it doubles the requested length, and above 1 MB it adds a flat megabyte instead. Doubling a 500 MB value to save a handful of copies would cost half a gigabyte of slack, so the growth changes shape once the wasted memory outweighs the copying it avoids.

Text processingStringBuilder in Java

A StringBuilder is a dynamic array of characters that grows to about twice its capacity plus two when it fills, and append writes into spare room it already owns. That is the whole reason building a string in a loop with a builder costs O(n) while repeated s = s + x costs O(n^2): Java strings are immutable, so every + allocates a fresh array and copies the entire prefix again. The builder is not faster per character, it simply stops paying for a full copy at every step.

Why it works this way

Why double instead of growing by a fixed number of slots?

Growing by a constant 100 slots means reallocating n/100 times and copying 100, then 200, then 300 values, and that arithmetic series sums to O(n^2) total work. Multiplying the capacity instead makes the copy sizes a geometric series, which sums to a constant multiple of n whatever the factor is, so the cost per append stays flat. The factor only moves that constant: Go doubles while capacity is under 256 elements and then tapers toward 1.25x, and CPython grows by roughly 1.125, both buying less slack memory at the price of a few more copies.

Why some libraries grow by 1.5 and not 2

With a factor of 2 the block you need is always bigger than every block you have already freed added together, so the allocator can never lay the new one back down in the space the old ones left and the array keeps crawling forward through memory. Any factor below the golden ratio, about 1.618, eventually lets a new block fit in the coalesced remains of the old ones: at 1.5 that reuse becomes possible after four reallocations. This is the argument Facebook's fbvector makes for choosing 1.5, while libstdc++ still doubles.

Growth invalidates every pointer into the array

A resize allocates a new block and copies, so anything holding an address inside the old block is left pointing at freed memory. In C++ a push_back that reallocates invalidates every iterator, pointer and reference into the vector, which is the classic crash where a reference taken before a loop is used after it. Go has a quieter version of the same bug: two slices sharing one backing array stop sharing the moment append grows one of them, and writes through the grown slice silently stop being visible to the other. Indices survive a resize, addresses do not.

Shrinking needs a gap, or it thrashes

Halving the capacity as soon as the array is half full puts the grow point and the shrink point in the same place: one append and one removal at that boundary then copy everything, over and over, and the amortized argument collapses back to O(n) per operation. Shrinking only at a quarter full leaves room between the two thresholds, so the array has to gain or lose a constant fraction of its size before it pays for another copy. Many libraries sidestep the question by never shrinking on their own, which is why std::vector gives memory back only when you ask with shrink_to_fit, and even that is a request the implementation may ignore, while ArrayList waits for trimToSize.

Read more

Next up