Dynamic Arrays

The append you never paid for

You have called list.append() thousands of times this year. Every single time, the answer came back instantly — fast enough that you never thought about it. But the list does not know in advance how big it will get. Somewhere in there, on a small fraction of those calls, it had to allocate a brand new block of memory and copy every existing element across before the append could complete. You never noticed. The way it hides those expensive moments is the topic of this lesson.

Two numbers, not one

A static array has one number you care about: how many slots it holds. A dynamic array has two.

length    — how many slots are in use
capacity  — how many slots are allocated

The buffer underneath is a static array. The dynamic array is the buffer plus the extra slack at the right end and the bookkeeping that turns "the buffer is full" from an error into a routine event.

function construct(initialCap, growthFactor) {
  return { buffer: new Array(initialCap), length: 0,
           capacity: initialCap, growthFactor };
}

The visualiser starts with a capacity of 2 and a length of 0. The two numbers sit beside the buffer. Push values one at a time and watch which pushes are cheap and which are expensive — the cost badge will tell you when something more than a single write happened.

The first two pushes are free. The buffer has slack; the value lands in the next empty slot; length advances. Three writes spent so far — counting the construction's zero — and the work for each push was exactly one memory write.

Then the buffer fills.

What happens when there is no room

Pushing into a full buffer cannot just write past the end. The allocation has a fixed size. So the dynamic array does the only thing it can: it asks the allocator for a new buffer, twice the size, copies every existing element across, frees the old one, and only then writes the new value into the next free slot.

function push(arr, value) {
  if (arr.length === arr.capacity) {
    const next = new Array(arr.capacity * 2);     // allocate
    for (let i = 0; i < arr.length; i++) {
      next[i] = arr.buffer[i];                    // copy
    }
    arr.buffer = next;                            // free old, point at new
    arr.capacity = next.length;
  }
  arr.buffer[arr.length] = value;                 // write
  arr.length += 1;
}

Step the visualiser through the third push. The two old values fly across into a fresh four-slot buffer; the old buffer fades out; only then does the new value land in slot 2.

The push did not fail. It did not silently grow the buffer in place. It paid for the move, in copies, and got on with the write.

That one push, on a million-element buffer, would cost roughly a million writes. Not "amortised". Not "on average". That single call would copy a million values across before its own value lands. It is the most expensive thing a dynamic array ever does.

Why the textbook says O(1)

Here is the move that makes the textbook honest. Every time the buffer fills and we double, the next resize is twice as far away. The first resize copied 2 elements. The next copied 4. The next copies 8, then 16, then 32. The cost grows, but so does the slack we get for free in between.

Sum up the work and the geometric series collapses. For n total pushes from an empty buffer, the resize-copies sum to less than n — they are bounded by n × (factor / (factor − 1)), which is 2n for a growth factor of 2. Add the n push-writes themselves, and the total work for n pushes is less than 3n. Divide by n and the average is bounded by 3. A constant. That is the amortised O(1) the textbook means.

The visualiser keeps a running tally as you push. After 8 pushes from capacity 2, you should see 14 total writes — averaging 1.75 per push. Push more and the average drifts toward 3 but never crosses it.

The amortised argument is not "most pushes are cheap, ignore the resize". It is "the resize is exactly as cheap as the cheap pushes once you account for the slack the resize buys you". The trade is honest, but you have to count both halves of it.

Notice that the order matters. The copy needs the old buffer; the new value needs the new buffer in place; the length must not advance until the new value is actually written, or a concurrent reader could observe a slot beyond the end. The right sequence is fixed.

Why doubling, not adding

The amortised argument depends on the growth being geometric, not just "growth on demand". If we grew the buffer by a constant amount — say, one slot at a time — every push past the initial capacity would trigger a resize. Push number k would copy k − 1 elements. Total work for n pushes would be 1 + 2 + 3 + … + n, which is roughly n² / 2. Push would be O(n) per call, not amortised O(1).

This is the failure mode the doubling strategy exists to prevent. Any growth factor strictly greater than 1 makes the geometric-series argument work — but the constant matters. A factor of 2 wastes up to half the buffer to slack right after a resize; a factor of 1.5 wastes less but copies more often. C++'s libstdc++ uses 2; MSVC's std::vector uses 1.5; CPython's list uses about 1.125. Different trade-offs, same family of strategy.

The capacities the buffer visits as you push are powers of the growth factor — 1, 2, 4, 8, 16, 32, … for factor 2. The buffer doubles only when you push into a full one; pushing into a buffer with slack leaves the capacity alone.

Pop is the easy direction

Removing the last element is the cheap mirror of pushing into a full buffer: decrement length, clear the slot, return the value.

function pop(arr) {
  arr.length -= 1;
  const v = arr.buffer[arr.length];
  arr.buffer[arr.length] = null;
  return v;
}

What pop deliberately does not do is shrink the buffer. The slack stays. If you push again immediately afterwards, the next push is free because the slot is still allocated. Implementations that do shrink — some C++ vectors, some Java lists — only do it with hysteresis: they wait until length drops well below capacity (typically length < capacity / 4) before halving. Without that hysteresis, alternating push-pop near the boundary would cause a resize on every other call.

CPython's list never shrinks on pop at all. The slack just sits there, and the only way to release it is to construct a new list. That choice is deliberate; the cost of the occasional held slack is well below the cost of resize-thrash in tight loops.

If the visualiser shows length dropping while capacity holds steady, the picture is correct. The two numbers diverge on pop and converge again on push.

When the amortised guarantee lies

The amortised argument is a statement about totals, not about individual operations. For most code, that's the right framing — the average cost is what dominates the runtime, and the occasional resize is invisible. But there are workloads where the worst push is what matters, not the average.

An audio processing loop running every ten milliseconds cannot afford a single push that copies a million elements. A physics step in a game frame budget cannot afford a stall. A trading system's hot path cannot afford an unpredictable spike. For these systems, "amortised O(1)" is the wrong tool, and the answer is to pre-size the buffer once at the start and never let it resize during the loop.

const events = new Array(1_000_000);  // capacity from the start
events.length = 0;                    // logically empty
// ...
events.push(event);                   // never resizes — slack is pre-allocated

Most languages have an explicit form of this — Vec::with_capacity(n) in Rust, make([]T, 0, n) in Go, std::vector::reserve(n) in C++, [None] * n in Python (with a separate length counter). It is the single most common dynamic-array optimisation in production code.

The lesson here is that "average is fine" is a workload statement, not a data structure statement. Tail latency and average latency answer different questions; pick the one your system actually cares about.

Where this shows up in real systems

Almost every "list" or "array" abstraction you reach for in a high-level language is a dynamic array, and almost all of them use the doubling family of strategies. A few worth knowing the specifics of:

• CPython's list: not a doubling-by-2 strategy — closer to 1.125x plus a small constant, defined in Objects/listobject.c's list_resize. Tuned to be more memory-conservative than the textbook 2x because Python programs hold a lot of small lists. Pop never shrinks.
• Java's ArrayList: 1.5x growth, computed as oldCapacity + (oldCapacity >> 1). The OpenJDK source spells it out plainly in ArrayList.grow().
• C++ std::vector: implementation-defined. libstdc++ (GCC) and libc++ (Clang) use 2x; MSVC uses 1.5x. The C++ standard mandates geometric growth so that push_back is amortised O(1), but does not pin the factor.
• Rust's Vec: 2x growth, in library/alloc/src/raw_vec.rs. The reallocation path returns an error rather than panicking on allocation failure, which is what makes Vec usable in no_std and embedded contexts.
• Go slices: 2x until length 1024, then 1.25x with rounding to allocator size classes. The size-class rounding is unique to Go — the runtime allocator has fixed bucket sizes, so the slice grows to the next bucket boundary.

Across all of them, the same two ideas hold: track length and capacity separately, and grow geometrically when you run out of room. Once you've held that picture, every "list" or "vector" in every language collapses into the same data structure with different tuning constants.

The append you have written ten thousand times this year was paid for by exactly this strategy, every time. You just never noticed the bill.

What to learn next

• Hash maps — the same "grow geometrically when you run out of room" idea, applied to bucket arrays. Same family, more bookkeeping.
• Linked lists (singly) — the alternative shape that gives up index-arithmetic in exchange for cheap insertion. Often the wrong choice in practice; understand why.
• Two pointers — the first pattern that exploits the dynamic array's cheap-push-cheap-index combination for problem solving.