49The array — the block everything is built on

In Chapter 48 we said a data structure is two things joined together: a way of arranging data in memory, and the operations that arrangement makes cheap. Now we spend that idea on the first arrangement there is, the one every other structure in this volume builds on: the array, a contiguous block of equal-size slots laid end to end in RAM with no gaps. Here's the plan. We'll set that block down in memory, watch the machine reach any element with a single multiply-add, then feel the price the same tight packing charges the moment you insert in the middle. All the way through, we keep asking the one question that decides everything: what does the layout make cheap, and what does it make expensive? By the end you'll see why indexing is O(1) and a middle insert is O(n) — not as rules to memorise, but as facts the layout leaves no choice about. You'll also see why Python's list grows in sudden jumps, why a list of a million integers costs 36 MB while the same numbers packed cost 8, and when the array is the container to reach for. Which is more often than you'd guess.

01One block, equal slots, no gaps

Let's start from the metal. Back in Volume 1 we drew RAM as one long row of numbered boxes: each box one byte, each with an address, its number in the row. An array is the simplest way to lay a sequence into that row. Pick a slot size, then set the elements down in consecutive slots starting at some address. That starting address is the array's base. The slot size — how many bytes each element takes — is the stride. Notice what's not there: nothing marks where one element ends and the next begins, except the fact that they're all the same width. So the machine can find element i by counting. Skip i strides from the base, and you're standing on it.

The word doing all the work is contiguous — "touching, in one unbroken run." The slots are neighbours in physical memory. There's no header between them, no pointer from one to the next, no bookkeeping of any kind. That absence is the whole trick, and everything good and bad about the array flows straight out of it.

If the position of element i is nowhere written down, how does the machine find it instantly? It doesn't look. It calculates →

02Why indexing is O(1): one multiply-add

Here is the array's superpower, and it's pure arithmetic. To find element i, the machine computes its address directly:

address(i) = base + i × stride

One multiply, one add. The CPU forms that address and reads the slot. There's no scanning, no comparing, no walking from the front. It doesn't matter whether i is 0 or 9,999,999: the same two operations land on the exact byte. That is what O(1) — constant time — means. The cost doesn't grow with the size of the collection. This is the payoff Volume 1 promised when it called a Python list "a contiguous array of references": indexing is a jump, not a search.

We can watch the formula on real memory. The array module hands us a block of packed 8-byte slots, and it will report the true base address of slot 0:

import array
A = array.array('q', [10, 20, 30, 40, 50])   # 'q' = signed 8-byte slots
base, length = A.buffer_info()                # the REAL address of slot 0
for i in range(length):
    print(i, base + i * A.itemsize)           # itemsize == stride == 8
# 0 2606972461072
# 1 2606972461080   <- exactly 8 bytes on from slot 0
# 2 2606972461088
# 3 2606972461096
# 4 2606972461104

Line 3 asks the array for its base address — an actual location in this process's RAM. Line 5 applies the formula: slot i sits at base + i × 8. The printed addresses climb by exactly 8 each step, with no gaps. That's proof the slots are contiguous, and proof that reaching any one is a single multiply-add. The machine never touched slots 0–3 to find slot 4; it computed straight to it.

And it's flat on the clock, not just in theory. Watch what happens when we time index access on lists of wildly different sizes (the numbers depend on the machine, but the shape is the point):

import timeit
for n in (1_000, 100_000, 10_000_000):
    L = list(range(n))
    t = timeit.timeit(f"L[{n//2}]", globals={"L": L}, number=2_000_000)
    print(n, round(t/2e6*1e9, 1), "ns")
# 1000       13.9 ns
# 100000     13.7 ns
# 10000000   14.4 ns   <- a 10,000x bigger list, same access time

Reaching the middle of a thousand-element list and the middle of a ten-million-element list both cost about 14 nanoseconds on our machine. The list grew ten-thousand-fold, and the access time didn't budge. That is O(1) you can see on a stopwatch.

Instant reads sound like a free lunch. They aren't — the same tight packing that makes index a jump makes the middle a wall →

03The price of the packing: the shift

The array's contiguity is a promise: no gaps, ever. Reads love that promise. Inserts hate it. Suppose you want to slip a new track into the middle of the playlist, at position i. There's no empty slot waiting there. Slot i is occupied by its neighbour, and that neighbour by its neighbour, all the way to the end. To open a hole at i without breaking the "no gaps" promise, every element from i onward must slide one slot to the right. That's n − i elements moved for a single insertion. Deleting in the middle is the same thing in reverse: everything after the hole shifts left to close it.

So insertion and deletion are O(n): the cost grows with how much sits after the cut. Insert at the very end (i = n) and nothing shifts, so it's cheap. Insert at the front (i = 0) and all n elements move, the worst case. The measurement is clear. Inserting at the front of lists ten times larger costs ten times more:

import timeit
for n in (10_000, 100_000, 1_000_000):
    L = list(range(n))
    t = timeit.timeit("L.insert(0, 99)", globals={"L": L}, number=1000)
    print(n, round(t/1000*1e6, 1), "us per front-insert")
# 10000        1.7 us
# 100000      17.1 us    <- 10x the elements, ~10x the shift
# 1000000    185.0 us    <- and again: linear, O(n)

Each L.insert(0, 99) forces CPython to shove every existing element up one slot before writing the new value into slot 0. As n goes 10k → 100k → 1M, the time goes 1.7 → 17 → 185 microseconds — a clean straight line. There's O(n), lived. (Appending to the end of these same lists, by contrast, runs in tens of nanoseconds. That's thousands of times faster, because it shifts nothing.)

The array so far has a fatal-sounding flaw: a fixed size. Lay six slots and you've committed to six. So how does list — which you .append to forever — live on top of it? →

04Static vs dynamic: how a fixed block grows

A raw array is static: its length is fixed the moment it's allocated, because the slots after it may belong to something else. Python's list is a dynamic array — the same contiguous block, wrapped in a trick that lets it grow. The trick is overallocation. The list quietly asks for more slots than it currently needs, and keeps the spare capacity in reserve. Appending just writes into the next spare slot and bumps a length counter: O(1), no copying. Only when the spare runs out does the list allocate a bigger block, copy everything across, and free the old one.

You can watch the reserve fill and refill. sys.getsizeof reports the block's real byte size, and it only changes when the underlying capacity does:

import sys
L, size = [], sys.getsizeof([])          # empty list header = 56 bytes
for i in range(40):
    L.append(i)
    s = sys.getsizeof(L)
    if s != size:                        # only prints when it RESIZED
        print(len(L), s, "bytes  capacity", (s - 56)//8)
        size = s
# 1   88 bytes  capacity 4
# 5  120 bytes  capacity 8
# 9  184 bytes  capacity 16
# 17 248 bytes  capacity 24
# 25 312 bytes  capacity 32
# 33 376 bytes  capacity 40

The empty list is a 56-byte header with zero slots. The first append jumps it to capacity 4 (88 = 56 + 4×8). Appends 2, 3, and 4 are then free: they fill the reserve without changing the size. The 5th append exhausts capacity 4, so CPython grows to 8, copies the four elements over, and carries on. The pattern of capacities — 4, 8, 16, 24, 32, 40 — shows the block growing by a shrinking proportion each time, roughly 1.125×, not doubling. Those gaps between resizes are why almost every append is cheap.

Doesn't that copy-everything resize make append secretly O(n)? Sometimes it does — a single append that triggers a resize really does move all n elements. But it happens so rarely (only when capacity fills) that spread across all the appends, the average cost stays constant. That's amortized O(1), the honest-average accounting from Volume 3. Timing the whole build proves it: the per-append cost stays flat even as the list grows 100×.

# build a list of n by appending, then divide total time by n
100_000  appends:  ~28 ns each
1_000_000 appends:  ~38 ns each
10_000_000 appends: ~40 ns each     <- flat: amortized O(1) per append

That last line hides the biggest surprise in this chapter. A Python list of a million numbers is far heavier than a million numbers — and the reason is what the slots actually hold →

05References vs values: why a list weighs 4× an array

Here's the twist that trips up almost everyone. A Python list's slots do not hold your numbers. They hold references — 8-byte addresses (Volume 1: a name is a reference) pointing to full int objects that live scattered elsewhere on the heap. Each of those integer objects carries the ~28-byte object header every Python object pays (refcount, type pointer, the digits). So one integer in a list costs you two things: 8 bytes in the contiguous slot block, plus ~28 bytes for the boxed object it points at. The block itself is tidy and contiguous, but the values it references are strewn across memory.

The array module offers the other layout: a packed array that stores the raw values directly, with no per-element object and no reference indirection. The size difference is not subtle. We measured it:

import sys, array
n = 1_000_000
L = list(range(n))
A = array.array('q', range(n))            # packed 8-byte values

sys.getsizeof(L)                          # 8_000_056  → just the references
sum(sys.getsizeof(x) for x in set(L))     # 28_000_000 → the boxed ints behind them
sys.getsizeof(A)                          # 8_183_816  → raw values, no boxing

The list's slot block is ~8 MB — a clean million 8-byte references. But follow those references and you find a million 28-byte int objects: another ~28 MB. The list's true footprint is about 36 MB (≈36 bytes per element). The packed array holds the identical numbers in ~8.2 MB (~8 bytes each). Same data, 4.4× less memory, because the array pays no object tax and stores no pointers — just values back to back.

Lighter is only half the win. The packed block is also the shape the CPU physically runs fastest over — and that's not a metaphor, it's the cache →

06Why the metal loves a block: cache locality

Big-O counts operations and treats every memory access as one unit. The hardware disagrees, and the array is where the disagreement pays off. Recall the memory hierarchy from Volume 3: an L1 cache hit costs ~1 ns, a miss out to RAM ~100 ns, and the CPU never fetches one byte at a time. On every miss it hauls in the whole surrounding cache line, ~64 bytes. For a packed array of 8-byte values that's eight neighbours per fetch: one miss, then seven free hits. Walk the block in order and the prefetcher, seeing the straight march, fetches the next line before you ask. A contiguous scan is, quite literally, the fastest thing a CPU does.

To prove the speed comes from the layout and nothing else, walk the same block twice: once in order, once through a shuffled set of indices. The reads are identical and the count is identical. Only the address pattern differs:

import timeit, random
n = 5_000_000
data = list(range(n))
seq  = list(range(n))                     # visit 0,1,2,... in order
rnd  = list(range(n)); random.shuffle(rnd)   # same indices, shuffled
def walk(order):
    s = 0
    for i in order: s += data[i]
    return s
# walk(seq): ~140 ms
# walk(rnd): ~1139 ms   → 8.1x slower, exact same reads

Both loops touch every element exactly once and add it up: same n, same O(n), same interpreter overhead per step. The only difference is that seq marches through consecutive addresses (cache-friendly) while rnd leaps to random ones (a miss almost every time). The result: the ordered walk ran ~8× faster on our machine. That gap isn't in the operation count, since Big-O is identical. It's the constant the layout bakes in, and it's why the contiguous array beats a scattered structure with the same complexity.

Light, instant to index, cache-loving, cheap to append. It's no accident this is where every other structure begins →

07The 1% move: the array is the default, and the foundation

Being "good at data structures" is mostly knowing which one fits the access pattern, and the array is the default, the one others must earn their way past. Here's its profile: O(1) indexing, O(1) amortized append, unbeatable cache behaviour, and minimal overhead (packed: ~8 bytes/element; boxed list: ~36). In exchange, you pay O(n) middle inserts and deletes, and, when packed, a fixed element type. So the rule is sharp: if you access by position, iterate in order, and grow at the end, use an array. Reach for something else only when your dominant operation is middle churn, keyed lookup, or hierarchical order — and the chapters ahead are exactly those "something elses."

The human insight worth taking with you is the one that made all of it possible: turn position into arithmetic. Someone realised that if you fix the slot size, an element's location stops being something you store and search for and becomes something you compute: base + i × stride, one multiply-add. That single idea — address as a formula — is the seed of the whole field. A stack and a queue are arrays with a rule about which end you touch. A heap is a tree flattened into an array, where a node's children are found by arithmetic (2i+1, 2i+2). A matrix is an array indexed by row × width + col. Even a hash table (Volume 1) is an array whose index you compute from the key. Learn to see the block under all of them, and the rest of this volume stops being thirteen unrelated tricks and becomes variations on one move.

The everyday version is real too. A parking garage numbers its spaces so you find yours by arithmetic instead of wandering. A packed shelf shoves every book down when you wedge one into the middle. The array is the oldest idea in computing because it's the most human one: put things in a row of equal boxes, and you'll always know where each one is.

The next chapter unbolts the block. The linked list throws away contiguity, scatters its elements as nodes joined by pointers, and buys back the one thing the array can't do cheaply — O(1) insertion in the middle — at the price of the multiply-add that made indexing free. Two structures, opposite deals with memory. →