Arrays and dynamic arrays

What this chapter covers

The array is the structure everything else is built on. It's a block of memory with elements laid end to end, and that simple layout buys the one superpower the rest of the book keeps trying to recover: reach any element by index in constant time. The catch is that a raw array has a fixed size, and real programs don't know their size in advance. This chapter builds the fix — a dynamic array that grows on demand — and shows why growing it by doubling makes appending cheap even though the growing itself is expensive. It's also your first encounter with amortized analysis, the accounting trick that lets an occasional costly operation still count as cheap.

A bit of history

The array is as old as stored-program computers. Once memory was addressable, the natural thing to do was lay values out contiguously and compute the address of element i by arithmetic — base plus i times element size. That formula is the whole reason random access is O(1), and it hasn't changed since the 1940s.

The dynamic, growable array is younger, and so is the analysis that justifies it. The doubling-on-full strategy became the standard implementation behind the resizable arrays in every major language — C++'s vector, Java's ArrayList, Python's list, Go's slices. What made it respectable rather than just a hack was Robert Tarjan's 1985 paper introducing amortized computational complexity, which gave us the vocabulary to say that an operation costing O(n) once in a while can still be O(1) on average, and to prove it rather than hand-wave. That proof is this chapter's math section.

The intuition

Picture a fixed block of slots — the backing store — with a count of how many are filled. Appending is easy while there's room: write into the next slot, bump the count. The problem is the moment the block is full. A fixed array can't grow in place; the memory right after it belongs to something else. So you allocate a new, bigger block, copy every existing element across, and switch to the new one. That copy is O(n), and it's unavoidable.

The question is how much bigger to make the new block. Add a constant amount — say one slot — and you'll resize on every single append, copying everything each time; that's O(n) per append, a disaster. Double the size instead, and resizes become rare: after doubling at size n, you get n more appends for free before the next one. The expensive copies get further and further apart, fast enough that their total cost, spread across all the cheap appends, comes out to a constant per append. Doubling turns an O(n) operation you do occasionally into an O(1) operation you can count on.

Complexity: how it scales

Random access is the easy part. Element i lives at a known offset, so reading or writing it is $O(1)$ regardless of size — this is what __getitem__ does.

Append is the interesting one. Most appends are a single write, $O(1)$. The ones that trigger a resize cost $O(n)$. To find the average, add up all the copying done over n appends. Starting from capacity 1 and doubling, resizes happen at sizes 1, 2, 4, 8, and so on, and each copies that many elements:

That's the total copying for all n appends combined. Divide by the n appends and the amortized cost per append is:

The trace bears the arithmetic out exactly: 64 appends into a fresh array did 63 element-copies in total, which is 0.984 copies per append — essentially one. The chart below shows where that copying happens. Each bar is the number of elements copied on that particular append; the spikes are the resizes, at 1, 2, 4, 8, 16, 32, and they get twice as far apart each time even as they get taller. That widening gap is the doubling paying for itself:

Inserting at the front is the operation to avoid. There's no room at index 0, so every existing element shifts one slot to the right first — $O(n)$ every time, and no amount of clever growth fixes it, because the cost is the shifting, not the allocating. When you need cheap insertion at both ends, that's a different structure, and it's the next two chapters.

What it's good at, what it isn't

Dynamic arrays are the right default for a sequence you mostly append to and index into. Contiguous memory isn't just about the O(1) index formula; it's also the friendliest possible layout for the hardware. The CPU pulls memory in cache lines, so walking an array in order means the next elements are almost always already in cache. This is why an array often beats a "faster" structure with better Big-O on real data — the constant hidden in a cache miss is enormous, and arrays dodge it.

Where they hurt is any edit that isn't at the end. Insert or delete in the middle or at the front and everything after the cut has to move, which is O(n). A resize also briefly needs both the old and new blocks in memory at once, so peak usage is larger than the data, and the extra capacity from over-allocation is real memory sitting empty. None of that outweighs the access speed for most workloads, which is exactly why the resizable array is the built-in list type in almost every language. Reach for something else only when your access pattern is genuinely about the front or the middle.

The data, or the inputs

The input is just a stream of values to append — the content is irrelevant, the count is everything, because this chapter is about how cost behaves as the array grows. The one thing worth watching directly is the backing store itself: how it fills up, and what happens at the instant it's full.

Build it, one function at a time

Append is the heart of it. Check whether the store is full; if so, grow it; then write and bump the count:

def append(self, value):
    """Amortized O(1): usually a single write; occasionally a resize.

    When the store is full we grow it before writing. Because we DOUBLE the
    capacity, resizes get rarer as the array grows — a resize at size n buys
    room for another n appends before the next one.
    """
    if self._n == self._cap:
        self._resize(2 * self._cap)
    self._store[self._n] = value
    self._n += 1

The grow step is the expensive one we're trying to make rare — allocate a bigger store and copy every live element across exactly once. The self.copies counter is only there so the chapter can prove the amortized bound:

def _resize(self, new_cap):
    """O(n): the expensive step. Allocate a bigger store and copy every
    existing element across exactly once."""
    bigger = [None] * new_cap
    for i in range(self._n):
        bigger[i] = self._store[i]
        self.copies += 1
    self._store = bigger
    self._cap = new_cap

Random access is the payoff and the reason to use an array at all — a direct index into the backing store, in constant time:

def __getitem__(self, i):
    """O(1): a direct index into the backing store. This — random access in
    constant time — is the reason arrays exist."""
    if not 0 <= i < self._n:
        raise IndexError(i)
    return self._store[i]

def __setitem__(self, i, value):
    if not 0 <= i < self._n:
        raise IndexError(i)
    self._store[i] = value

And front insertion is the anti-pattern, included so you can feel the O(n) in your hands: to make room at index 0, everything shifts right:

def insert_front(self, value):
    """O(n): the array's weak spot. To open a slot at index 0 every existing
    element must shift one place to the right."""
    if self._n == self._cap:
        self._resize(2 * self._cap)
    for i in range(self._n, 0, -1):
        self._store[i] = self._store[i - 1]
    self._store[0] = value
    self._n += 1

Watch it work

Here's the backing store as sixteen values get appended one at a time. Slate cells are filled, dark cells are empty capacity, orange is the value just written. When the store fills, watch it double in width and flash the copied elements in blue — that blue burst is the O(n) resize. Step through and count the appends between resizes: they double each time, 1, 2, 4, 8, which is precisely why the average cost stays flat. Sixteen appends fit into a store that doubled 1 → 2 → 4 → 8 → 16 and copied 15 elements total along the way.

The complete code

The whole dynamic array against the one it reimplements — flip between them. The from-scratch tab is our backing store, doubling append, O(1) access, and O(n) front insert. The library tab is Python's list: same structure, but it grows on a gentler curve than our strict doubling (its factor is about 1.125) and runs the append-and-copy loop in C. Same shape — amortized O(1) append, O(n) front insert.

"""A dynamic array built from scratch on top of a fixed-size backing store.

The backing store is a Python list used the way a real language uses a raw
array: allocated at a fixed capacity, never grown in place. When it fills, we
allocate a bigger one and copy everything across. Doubling the capacity on each
resize is what makes append cheap on average — that's the whole idea of the
chapter, and `self.copies` counts the copying so we can prove it.
"""


class DynamicArray:
    def __init__(self):
        self._cap = 1                 # capacity of the backing store
        self._n = 0                   # number of elements actually stored
        self._store = [None] * self._cap
        self.copies = 0               # total element copies caused by resizing

    # region: append
    def append(self, value):
        """Amortized O(1): usually a single write; occasionally a resize.

        When the store is full we grow it before writing. Because we DOUBLE the
        capacity, resizes get rarer as the array grows — a resize at size n buys
        room for another n appends before the next one.
        """
        if self._n == self._cap:
            self._resize(2 * self._cap)
        self._store[self._n] = value
        self._n += 1
    # endregion

    # region: resize
    def _resize(self, new_cap):
        """O(n): the expensive step. Allocate a bigger store and copy every
        existing element across exactly once."""
        bigger = [None] * new_cap
        for i in range(self._n):
            bigger[i] = self._store[i]
            self.copies += 1
        self._store = bigger
        self._cap = new_cap
    # endregion

    # region: access
    def __getitem__(self, i):
        """O(1): a direct index into the backing store. This — random access in
        constant time — is the reason arrays exist."""
        if not 0 <= i < self._n:
            raise IndexError(i)
        return self._store[i]

    def __setitem__(self, i, value):
        if not 0 <= i < self._n:
            raise IndexError(i)
        self._store[i] = value
    # endregion

    # region: insert_front
    def insert_front(self, value):
        """O(n): the array's weak spot. To open a slot at index 0 every existing
        element must shift one place to the right."""
        if self._n == self._cap:
            self._resize(2 * self._cap)
        for i in range(self._n, 0, -1):
            self._store[i] = self._store[i - 1]
        self._store[0] = value
        self._n += 1
    # endregion

    def __len__(self):
        return self._n

    @property
    def capacity(self):
        return self._cap

    def to_list(self):
        return [self._store[i] for i in range(self._n)]

"""Python's built-in list IS a dynamic array — the exact structure this chapter
builds. So the face-off is our DynamicArray against the list it reimplements.

CPython's list over-allocates on a gentler curve than our doubling (its growth
factor is roughly 1.125), and the append + copy loop runs in C. Same amortized
O(1) append, same O(n) resize cost spread thin — just a smaller constant.
"""


# region: python_list
def build_with_list(values):
    """Append every value into a built-in list. Amortized O(1) per append,
    because the list over-allocates and only copies on the occasional resize."""
    out = []
    for value in values:
        out.append(value)
    return out
# endregion


# region: list_insert_front
def insert_front_with_list(values):
    """The built-in's front insert is list.insert(0, x) — still O(n) per call,
    same as ours, because the underlying array still has to shift."""
    out = []
    for value in values:
        out.insert(0, value)
    return out
# endregion

Scratch vs library

Same structure, same Big-O, so the face-off is purely about the constant — and the constant is large, because ours is a Python loop and the list is C. Appending 160000 items took about 20.1 ms with our DynamicArray against 1.54 ms with the built-in, roughly thirteen times slower. The chart shows both operations; note that the append lines are both straight (linear total work, so amortized constant per item) while the front-insert lines curve upward — that's the $O(n^2)$ of doing an O(n) shift n times, and it bends the same way for our code and the library's, because the structure forces it:

Thirteen times is a real gap, and it's the price of writing your own container in a high-level language. It's also beside the point: you'd never ship this. The reason to build it is to know exactly what list.append is doing under you, so that when a profiler shows an append-heavy loop dominating, you know it's the rare resizes and not the writes, and when you see list.insert(0, x) in a hot path you recognize the O(n) trap instantly.

Where you'll actually meet it

You meet the dynamic array every time you write [] and start appending — it's the default list type in Python, JavaScript, Java, C++, Go, and Rust, under the names list, Array, ArrayList, vector, slice, and Vec. Its performance profile shapes everyday advice you've probably absorbed without knowing why: build a list by appending, not by inserting at the front; pre-size it when you know the length so you skip the resizes entirely; prefer it over a linked list for iteration because the cache loves contiguous memory. Every one of those tips is a direct consequence of the mechanics in this chapter.

Takeaways

A dynamic array is a fixed array plus a growth strategy, and the growth strategy is the whole trick: double the capacity when it fills, so the expensive O(n) copies get exponentially rarer and their cost amortizes to O(1) per append. You get constant-time random access and cache-friendly iteration for free, and you pay for it at the front and the middle, where every insert or delete is O(n).

That trade — cheap at the end and by index, expensive in the middle — is the array in one line, and it's the baseline the next structures are defined against. Linked lists give up the O(1) index to win O(1) insertion anywhere you already are. Stacks and queues are arrays with the operations deliberately restricted to the cheap ends. Keep this chapter's picture of the doubling backing store in mind; almost everything that follows is a reaction to it.