↩ back to Linear

Dynamic Array

A plain array is a fixed-size block of memory: you pick a capacity up front, and arr[i] is always one address computation away — no walking required. The catch is the "fixed" part. A dynamic array (what Array in JavaScript, list in Python, ArrayList in Java, and vector in C++ all actually are) keeps that O(1) indexing but lets you keep pushing past the current capacity: when it fills up, it allocates a bigger backing array and copies everything over. This is the array side of the trade-off Linked List describes from the other direction — get O(1) random access here, pay for it with occasional O(n) reallocations instead of a linked list's O(1) splice everywhere.

Try it

Push values on, pop the last one off, or get a value by index. Dashed cells are allocated capacity the array isn't using yet. Watch what happens the moment length catches up to capacity — and what doesn't happen to capacity when you pop.

Core operations

• get(i) / set(i, x) — jump straight to slot i. O(1), the same guarantee a fixed array gives, unaffected by how the resizing works underneath.
• push(x) — if there's spare capacity, place x in the next slot and increment length: O(1). If length has caught up to capacity, reallocate a bigger backing array first and copy every existing element into it: O(n) for that one call, but see below for why it's still O(1) amortized.
• pop() — decrement length and return what was there. O(1) — and, in every mainstream implementation, capacity is left exactly where it was. Nothing shrinks on its own.
• insert(i, x) / delete(i) — everything from i onward has to shift over by one to make or close a gap: O(n), unlike a linked list's O(1) splice once you're at the right node.

Reference implementation

class DynamicArray {
  #data;
  #length = 0;

  constructor(initialCapacity = 4) {
    this.#data = new Array(initialCapacity);
  }

  get length() { return this.#length; }
  get capacity() { return this.#data.length; }

  get(i) {
    if (i < 0 || i >= this.#length) {
      throw new RangeError(`index ${i} out of bounds (length ${this.#length})`);
    }
    return this.#data[i];
  }

  push(x) {
    if (this.#length === this.#data.length) this.#grow();
    this.#data[this.#length] = x;
    this.#length++;
  }

  pop() {
    if (this.#length === 0) throw new Error('pop on empty array (underflow)');
    this.#length--;
    const x = this.#data[this.#length];
    this.#data[this.#length] = undefined; // drop the reference; the slot stays allocated
    return x;
  }

  #grow() {
    const newCapacity = this.#data.length === 0 ? 1 : this.#data.length * 2;
    const next = new Array(newCapacity);
    for (let i = 0; i < this.#length; i++) next[i] = this.#data[i];
    this.#data = next;
  }
}

The whole design hinges on #grow()'s growth rule: multiply capacity by a constant factor (here, double it), never add a constant. The next section is about exactly why that one word — multiply, not add — is load-bearing.

Why push is O(1) amortized, not O(n)

Any single push that triggers a reallocation is genuinely O(n) — every existing element gets copied. So why do we call the operation "O(1)"? Because reallocations get rarer exactly as fast as they get more expensive, and the two cancel out over a long run.

With doubling, reallocations happen at capacities 1, 2, 4, 8, 16, ... — a geometric sequence. The copy cost at each one equals that capacity, so the total copying work across n pushes is 1 + 2 + 4 + ... up to roughly n — and a geometric series is bounded by about twice its largest term, so the total is O(n), not O(n²). Spread that O(n) total over n pushes and each one is O(1) on average — "amortized" — even though a few individual pushes are the expensive O(n) ones that pay for all the cheap ones around them.

Pitfalls

Growing by a fixed amount instead of a fixed factor. This is the one mistake that quietly destroys the whole amortized guarantee, and it looks reasonable at a glance — "grow the array by 8 slots whenever it's full" sounds like a sensible, memory-frugal policy. It isn't. Run the numbers instead of trusting intuition:

Doubling keeps total copying work (and so amortized cost per push) at O(n) (O(1) each). Growing by a fixed amount makes reallocations just as frequent as the naive "grow by exactly 1" version — both hit O(n) reallocations for n pushes instead of O(log n) — so total copying work becomes O(n²), meaning each push is O(n) amortized, not O(1). The constant (8 instead of 1) only changes where the quadratic curve starts, not that it's quadratic. This is exactly the kind of bug that's invisible on a small test array and only shows up as your program mysteriously slowing down once real data arrives.

Assuming pop() reclaims memory. The demo above never shrinks capacity on pop, and neither does JavaScript's Array, Python's list, Java's ArrayList, or C++'s vector by default. An array that briefly grows huge and then shrinks back down keeps holding that peak-sized backing buffer until something explicitly asks it to shrink (C++'s shrink_to_fit, or just building a fresh array from the surviving elements). If you're holding onto a large array "just in case" and expecting memory to shrink back after popping most of it, it won't, on its own.

Stale references across a reallocation. #grow() above doesn't resize #data in place — it builds an entirely new array and copies into it. Anything that captured a reference to the old backing array before a reallocation (a raw pointer in C++, a manually-cached buffer reference in lower-level code) is now looking at a stale copy that stops receiving future writes. JavaScript hides this by only ever letting you touch the array through its own object, but it's a routine source of bugs in languages that expose the backing buffer directly — the same shape as an invalidated iterator.

Where dynamic arrays show up

• The default "array" in most languages. JavaScript's Array, Python's list, Java's ArrayList, C++'s vector — none of these are fixed-size. When people say "just use an array" day to day, this is almost always the structure they mean.
• Binary Heap. A heap's complete-tree shape is stored in exactly this structure — pushing a new element onto the end and letting it sift up is only O(log n) overall because the underlying array push is amortized O(1), not O(n).
• String builders and byte buffers. Appending to a growing string or binary buffer without knowing the final size up front uses the identical doubling trick.
• Accumulating results with an unknown final count. Any algorithm that builds up an output list one item at a time — collecting matches, building a sorted run, BFS visit order — relies on push being cheap without needing to pre-size anything.

Complexity

Time: get/set are O(1). push/pop are O(1) amortized (a single push can be O(n) worst case). insert/delete at an arbitrary index and search by value are all O(n) — the array has to shift or be scanned. Space: O(n), but with real slack — right after a doubling reallocation, roughly half the newly allocated capacity sits empty, the price paid for keeping reallocations geometrically rare instead of linearly frequent.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.