Dynamic Arrays, Built From Scratch

The problem a dynamic array solves

Back to the train: it was built with a fixed number of cars, and the track position right behind the caboose already belongs to something else — another train's siding, a switch, whatever. There's no room to just weld one more car onto the end forever. A raw array's size is fixed at allocation for the identical reason — the memory after it may belong to something else, so it cannot simply grow in place. But programs rarely know sizes up front. The dynamic array's answer:

1. keep a plain array (the backing store) with some capacity,
2. track how many slots are actually used (the length),
3. when an append finds length == capacity, allocate a bigger block, copy everything over, and retire the old one — build an entirely new, longer train on a fresh stretch of track, and move every existing car over to it, one by one, before retiring the old, too-short train.

The whole design question is step 3: how much bigger? Two policies, two outcomes — worth re-deriving here since the implementation below hinges on picking the right one:

• Multiplicative (double capacity). Copies happen at sizes 1, 2, 4, 8, …, n — a geometric series summing to under 2n total copies across n appends. Spread over n appends, that's O(1) amortized each (you proved this fully in the Big O module). Each new train is roughly twice as long as the last, so rebuilds become rare fast — most cars, once moved, sit through many future appends before ever needing to move again.
• Additive (capacity += c). Copies happen every c appends, at sizes c, 2c, 3c, …, n — an arithmetic series summing to Θ(n²/c). Spread over n appends, that's Θ(n/c) amortized each: still growing with n, not constant. A fixed increment never escapes O(n) amortized, no matter how large you pick c — you'd be building a new train every c cars forever, re-moving the same early cars again and again as the train grows.

Now we build the multiplicative version.

The implementation

Everything the standard list / Array does for appends, reads, and removal — from scratch. (Python note: we deliberately use a fixed-size allocation to simulate the raw array underneath.)

class DynamicArray:
    def __init__(self) -> None:
        self._capacity = 1
        self._length = 0
        self._store = [None] * self._capacity   # simulated raw array

    def __len__(self) -> int:
        return self._length

    def get(self, i: int):
        if not 0 <= i < self._length:
            raise IndexError(i)
        return self._store[i]                   # O(1): address arithmetic

    def set(self, i: int, value) -> None:
        if not 0 <= i < self._length:
            raise IndexError(i)
        self._store[i] = value                  # O(1)

    def append(self, value) -> None:
        if self._length == self._capacity:
            self._grow()                        # O(n), but rare
        self._store[self._length] = value       # O(1)
        self._length += 1

    def pop(self):
        if self._length == 0:
            raise IndexError("pop from empty array")
        self._length -= 1
        value = self._store[self._length]
        self._store[self._length] = None        # release the reference
        return value                            # O(1) — no shifting at the end

    def insert(self, i: int, value) -> None:
        if not 0 <= i <= self._length:
            raise IndexError(i)
        if self._length == self._capacity:
            self._grow()
        for j in range(self._length, i, -1):    # shift right: O(n - i)
            self._store[j] = self._store[j - 1]
        self._store[i] = value
        self._length += 1

    def _grow(self) -> None:
        self._capacity *= 2                     # multiplicative — load-bearing!
        new_store = [None] * self._capacity
        for j in range(self._length):           # copy: O(n)
            new_store[j] = self._store[j]
        self._store = new_store

Walk the code against the design: append is a single write except when _grow fires; _grow doubles (the amortization argument needs exactly this); pop at the end never shifts; insert pays the shifting cost that contiguity demands. Step through five appends and watch _grow earn its keep:

Design notes worth internalizing

• Length ≠ capacity. The store is usually bigger than the data. Space is O(n) still — doubling wastes at most half, a constant factor.
• Why not shrink eagerly? Popping just below a power of two and re-appending would then thrash grow/shrink at O(n) each. Real implementations shrink lazily (e.g. at ¼ occupancy) or never — keeping the amortized argument intact.
• Growth factors in the wild are 1.5×–2× (Python ~1.125×+ overallocation pattern, many ArrayLists 1.5×, JS engines vary). Any factor > 1 gives O(1) amortized; the choice trades memory waste against copy frequency.