Dynamic Arrays & Amortized Growth

The 10-second versionCopy Anchor Link

A plain array is fixed-size; you must know the length up front. A dynamic array keeps the same contiguous block but adds two numbers: length (how many elements are in use) and capacity (how many fit). When you append and length == capacity, you allocate a bigger block, copy everything over, and keep going. If you grow by doubling, the copies are rare and cheap enough that the cost of one append, averaged over many of them, is O(1) amortized — even though the occasional append is O(n). This is the data structure behind std::vector, ArrayList, JavaScript's arrays, and Rust's Vec.

Why this existedCopy Anchor Link

The array from the last page is perfect until you need it to hold one more thing than you planned for. The number of rows in a query, the tokens in a document, the players in a match — none of that is known when you write the code. You had two ugly choices: over- allocate (guess, and waste memory or overflow anyway) or hand-roll a resizable buffer and get the copy logic right yourself.

The idea that saved everyone is a policy, not a data structure: grow geometrically. Instead of adding one slot when full, add a whole block more — ideally double. That single rule turns an O(n²) death spiral into amortized O(1) appends.

• 1994 — Alexander Stepanov brings his STL to C++, standardizing the growable array as std::vector. Its growth policy became the template everyone copied.
• 1998 — Java 1.2 ships java.util.ArrayList in the Collections Framework, hiding the same doubling behind add.
• 2015 — Rust 1.0 stabilizes Vec<T>, with the growth policy checked and documented as part of the standard library.
• Along the way, JavaScript arrays and Python lists quietly became dynamic arrays too — so most developers use one before they ever learn the word.

Why it mattered then: it let programmers stop guessing sizes. Write push and let the buffer deal with growth — trading a little sliding-scale waste for a lot of simplicity and speed.

Inside the inventor's headCopy Anchor Link

Start with the honest first attempt: "when it's full, make it one bigger." It's correct — just catastrophically slow. Every single append past the capacity reallocates the whole array and copies every element:

The trap is subtle: each individual resize looks fine — it's "just one element bigger." But it happens on every append once you're at capacity. Watch the mismatch between what you do and what it costs:

// Naive: a brand-new, one-slot-bigger array on every push — Θ(n) per pushlet naive = new Int32Array(0);let naiveLen = 0;const pushPlusOne = (x) => {  const bigger = new Int32Array(naiveLen + 1);  bigger.set(naive.subarray(0, naiveLen));   // copies all elements  bigger[naiveLen++] = x;  naive = bigger;};// Improved: grow only when full, and DOUBLE. Most pushes cost Θ(1).let buf = new Int32Array(0);let len = 0;const pushDouble = (x) => {  if (len === buf.length) {    const cap = buf.length ? buf.length * 2 : 1;   // the whole trick    const bigger = new Int32Array(cap);    bigger.set(buf.subarray(0, len));    buf = bigger;  }  buf[len++] = x;};

The pivot is dropping the requirement that the new array be as small as possible. Once you allow yourself to overshoot the capacity, the number of resizes collapses from n to log n — and the doubling is what makes each of those resizes "pay for" the many cheap appends around it.

The final approachCopy Anchor Link

The structureCopy Anchor Link

A dynamic array is just three fields: a pointer to the block, a len, and a cap, with the invariant 0 ≤ len ≤ cap.

The invariantCopy Anchor Link

0 ≤ len ≤ cap, and elements 0 … len − 1 are the live contents. Growth preserves contiguity — it moves the whole block, it never splits it — so random access stays O(1). The growth policy (double when full) is what keeps appends cheap on average.

Before / after a resizeCopy Anchor Link

Why doubling beats +1 (the derivation)Copy Anchor Link

Say you push n elements one at a time.

• Grow by +1. At sizes 1, 2, 3, …, n you copy 1 + 2 + 3 + … + n = n(n+1)/2 elements in total. That's Θ(n²) for n pushes — Θ(n) per push.
• Grow by ×2. At sizes 1, 2, 4, 8, …, n you copy 1 + 2 + 4 + … + n elements, which is less than 2n (a geometric series sums to twice its last term). That's Θ(n) for n pushes — Θ(1) per push, amortized.

The geometric series is the whole magic: doubling makes the sum of all copies a constant multiple of n, so each append "pre-pays" at most about 2 units of copy work.

A worked trace: pushing 0 … 9Copy Anchor Link

Total copies to push 10 elements: 0+1+2+4+8 = 15 — about 2n, exactly as predicted.

It in codeCopy Anchor Link

class Vec {  constructor() { this.data = new Int32Array(0); this.len = 0; }  push(x) {    if (this.len === this.data.length) {      const cap = this.data.length ? this.data.length * 2 : 1;      const bigger = new Int32Array(cap);      bigger.set(this.data);              // amortized: rare      this.data = bigger;    }    this.data[this.len++] = x;            // cheap common case  }  get(i) { return this.data[i]; }          // O(1)  size() { return this.len; }}

ComplexityCopy Anchor Link

Space is Θ(n), but the capacity sits between n and 2n — you pay up to 2× memory in exchange for amortized O(1) appends.

The one caveat: realloc can move the block, so any pointer into the old storage is now stale. That's why languages with references either hide the block behind an owner (Rust) or never hand out interior pointers as stable (JavaScript).

Where you meet it todayCopy Anchor Link

• Every language's "array" is one. JavaScript's Array, Python's list, Go's slice, Java's ArrayList, C++'s vector, Rust's Vec — all dynamic arrays with geometric growth.
• String builders. Java's StringBuilder and Rust's String are dynamic arrays of characters; that's how they turn O(n²) concatenation into O(n) building.
• Graph adjacency lists. Storing each vertex's neighbors in a growable array is the default graph representation — you never know a node's degree in advance.
• Accumulators. Histograms, log buffers, and "collect all matches" results are push-only dynamic arrays by another name.

const v = [];for (let i = 0; i < 1000; i++) v.push(i);         // built-in, amortized Θ(1)

RecapCopy Anchor Link

• A dynamic array = a contiguous block plus a length and a capacity.
• Grow by doubling, not +1: +1 gives Θ(n) per append (Θ(n²) total), doubling gives Θ(1) amortized (Θ(n) total) via a geometric series.
• Contiguity is moved, never broken, so random access stays O(1).
• realloc may relocate the block — pointers into the old storage go stale.
• It's the workhorse behind almost every "list" you've ever used.

Next up: Strings — a dynamic array of characters, with its own centuries-old question about how you know where it ends.