Dynamic Arrays

A dynamic array grows automatically by reallocating to a larger block, giving amortized constant-time append on top of a fixed array.

Fixed arrays that grow

A plain array has a fixed capacity. A dynamic array (the Python list, the C++ vector, the Java ArrayList) wraps a fixed array plus a stored size and capacity. While size is below capacity, appending writes into the next free slot in O(1). When the array is full, it allocates a larger block, copies the existing elements, and continues.

Why doubling matters

The key design choice is the growth factor. If capacity is increased by a constant amount each time, n appends cost O(n^2) total because copies pile up. If capacity is doubled (or multiplied by a constant greater than one) each time it fills, the total copying work across n appends is bounded by 2n. Spread over n operations that is O(1) per append on average.

Amortized cost

Individual appends vary: most are O(1), but the one that triggers a resize is O(n). Amortized analysis charges each cheap append a small surplus that pays for the occasional expensive one. The result is an amortized O(1) append even though the worst single append is O(n).

class DynArray:
    def __init__(self):
        self.cap = 1
        self.n = 0
        self.data = [None]*self.cap
    def append(self, x):
        if self.n == self.cap:
            self.cap *= 2
            new = [None]*self.cap
            for i in range(self.n):
                new[i] = self.data[i]
            self.data = new
        self.data[self.n] = x
        self.n += 1

Trade-offs

Doubling can waste up to half the block in unused capacity, so some implementations grow by a factor closer to 1.5 to reduce slack. Shrinking is done lazily to avoid thrashing: a common rule is to halve capacity only when the array falls to one quarter full. Access by index stays O(1); insertion and deletion in the middle remain O(n) exactly as in a fixed array.