49The array — the block everything is built on

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

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, where each box holds one byte and carries an address, its number in the row. An array is the simplest way to lay a sequence into that row: you pick a slot size, then set the elements down in consecutive slots starting at some address. That starting address is the array's base, and the slot size, how many bytes each element occupies, is what we call the stride. Now watch what is not there. Nothing marks where one element ends and the next begins, except the plain fact that they are all the same width. So the machine can always find element i by counting, skipping i strides from the base to stand right on it.

The word doing all the work is contiguous, meaning "touching, in one unbroken run." The slots are neighbours in physical memory. There is no header between them, no pointer from one to the next, no bookkeeping of any kind. That absence is the whole trick. 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 is pure arithmetic: to find element i, the machine computes its address directly, with no lookup and no search along the way:

address(i) = base + i × stride

That is one multiply and one add: the CPU forms the address and reads the slot, with no scanning, no comparing, and no walking from the front. It does not matter whether i is 0 or 9,999,999, because the same two operations land on the exact byte either way. That is what O(1), or constant time, really means, since the cost does not 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.

Notice what that formula quietly depends on: every slot being the same width. That is the price the array charges for its speed, because a fixed width is what lets the stride be a single constant number. Picture the alternative, where the elements had different sizes. To reach slot 100 you would first have to add up the lengths of all 99 slots ahead of it, walking the whole run just to learn where the next one begins. The moment the widths vary, base + i × stride stops working and the O(1) jump is gone. So the uniform slot is not a small detail. It is the whole bargain that turns position into arithmetic.

Let's make that concrete with real numbers. Say our array of track lengths starts at base address 1000, and each slot is 8 bytes wide. Slot 0 sits at 1000, because 1000 + 0 × 8 is just 1000. Slot 1 sits at 1000 + 1 × 8 = 1008, and slot 3 sits at 1000 + 3 × 8 = 1024. Notice we jumped straight to slot 3 without ever looking at slots 1 or 2. That is the whole point. The machine does one multiply and one add, then reads. It would do the exact same two operations to reach slot 3 or slot three million.

We can watch the formula on real memory. The array module hands us a block of packed 8-byte slots and 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, so slot i sits at base + i × 8. The printed addresses climb by exactly 8 each step, with no gaps. That proves the slots are contiguous, and 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 in the clock, not just in theory. Watch what happens when we time index access on lists of wildly different sizes (machine-dependent numbers, 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; the access time didn't budge. That is O(1) you can see on a stopwatch.

Sit with how strange that is for a moment. The collection got ten thousand times bigger, and the machine did not work one bit harder to reach into it. That is the array's first gift, and it falls out of nothing but the fixed stride and a little arithmetic. But every gift in this chapter has a matching bill. The same tight packing that makes a read a single jump is about to make a middle insert an expensive shuffle, and for the exact same reason: no gaps, ever.

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 is no empty slot waiting there — slot i is occupied by its neighbour, and its 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. Delete in the middle and it's the same in reverse: everything after the hole shifts left to close it.

Count it on a real playlist. Say you have 6 tracks in slots 0 through 5, and you want the new track at position 2. Slots 2, 3, 4, and 5 each have to slide one to the right, which is n − i = 6 − 2 = 4 moves before you can write the newcomer into slot 2. Insert near the front and you move almost the whole array. Insert at the very back and you move nothing. The cost is not fixed. It is exactly however many elements sit to the right of the cut.

Deletion is the same story told backwards, and it is worth counting once. Take those same 6 tracks in slots 0 through 5, and pull the one at position 2 out. Now there is a hole at slot 2, and the array's no-gaps promise forbids it. So slots 3, 4, and 5 each slide one to the left to close it, which is n − i − 1 = 6 − 2 − 1 = 3 moves. An insert opens a hole and a delete closes one, but either way the machine pays for every element sitting past the cut.

So insertion and deletion are O(n), because the cost grows with how much sits after the cut. Insert at the very end (i = n) and nothing shifts at all, which is cheap. Insert at the front (i = 0) and all n elements have to move, which is the worst case. The measurement is unambiguous, and it shows that 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. That is a clean straight line, and there's the O(n), lived. Appending to the end of these same lists, by contrast, runs in tens of nanoseconds. That is 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, which is 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.

Why hand out spare slots at all? Picture the lazy alternative. The list grows by exactly one slot on every append, so every single append has to copy the whole block into a new, one-bigger block. Building a list of 1000 elements that way copies 1 + 2 + 3 + … + 1000 elements in total, which is 1000 × 1001 / 2 = 500500 copies for 1000 appends. That is O(n²), and it would make a growing list crawl. Overallocation is the fix: hand out a batch of spare slots, and most appends become a free write with no copy at all.

You can watch the reserve fill and refill for yourself, because sys.getsizeof reports the block's real byte size, and that size 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, 4 are then free, because 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 is 4, 8, 16, 24, 32, 40. It shows the block growing by a shrinking proportion each time, roughly 1.125×, not doubling. The gaps between resizes are why almost every append is cheap.

# A static array: capacity fixed at birth, and it bills you for every shift.
class FixedArray:
    def __init__(self, capacity):
        self._slots = [None] * capacity   # the block: allocated once, never grows
        self._n = 0                       # how many slots are filled
        self.capacity = capacity
        self.shifts = 0                   # elements physically moved, ever

    def __len__(self): return self._n

    def append(self, x):
        if self._n == self.capacity:
            raise OverflowError(f"array is full ({self.capacity} slots) - a static block cannot grow")
        self._slots[self._n] = x          # write into the next free slot: no shift
        self._n += 1

    def insert(self, i, x):
        if self._n == self.capacity:
            raise OverflowError(f"array is full ({self.capacity} slots) - a static block cannot grow")
        for k in range(self._n, i, -1):   # BACK to front, or you smear the value
            self._slots[k] = self._slots[k - 1]
            self.shifts += 1              # <- the O(n) made visible
        self._slots[i] = x
        self._n += 1

    def __getitem__(self, i):             # O(1): one index into the block
        if not 0 <= i < self._n: raise IndexError("index out of range")
        return self._slots[i]

    def __repr__(self): return f"FixedArray({self._slots[:self._n]}, cap={self.capacity})"

A = FixedArray(6)
for t in (200, 247, 245, 269):
    A.append(t)
print(A, "shifts so far:", A.shifts)

A.insert(0, 111)          # worst case: everything moves
print(A, "shifts so far:", A.shifts)
A.insert(len(A), 999)     # best case: nothing moves
print(A, "shifts so far:", A.shifts)
print("A[2] ->", A[2], "  (one index, no walk)")
try:
    A.append(1)
except OverflowError as e:
    print("OverflowError:", e)

# FixedArray([200, 247, 245, 269], cap=6) shifts so far: 0
# FixedArray([111, 200, 247, 245, 269], cap=6) shifts so far: 4
# FixedArray([111, 200, 247, 245, 269, 999], cap=6) shifts so far: 4
# A[2] -> 247   (one index, no walk)
# OverflowError: array is full (6 slots) - a static block cannot grow

# READ THE COUNTER. Four elements sat past index 0, so inserting there moved
# four -- exactly n - i. Inserting at the END moved none, and the counter did
# not budge. One method, two prices, decided by nothing but where you cut.
# Then swap [None]*capacity for a real block and you have CPython's list --
# except CPython, instead of raising, allocates a bigger block and copies.
# That single difference is the whole of "static vs dynamic".

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

Here's why the average really does stay flat. Watch the copies as the list grows through capacities 4, 8, 16, 24, 32, 40. A resize copies only the elements already there, so growing to cap 8 copies 4, to cap 16 copies 8, to cap 24 copies 16, and to cap 32 copies 24. To reach 40 elements the resizes copy 4 + 8 + 16 + 24 + 32 = 84 elements in total, spread across 40 appends. That is about 2 extra moves per append, a small constant that does not grow as the list gets longer. Double the final size and that per-append number barely moves. That is amortized O(1) in plain arithmetic.

# 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 is tidy and contiguous; the values it references are strewn across memory.

Put numbers on that tax. A list holding three large integers like 1000000, 2000000, and 3000000 spends 3 × 8 = 24 bytes on references in the tidy block, plus 3 × 28 = 84 bytes on the three boxed int objects scattered on the heap. The values weigh more than three times the slots that point at them. One honest caveat: CPython caches the small integers from −5 to 256, so a list of tiny numbers shares those objects and pays the object tax only once. Use large or distinct values, as here, and every one is its own 28-byte allocation.

Why references at all, though, instead of the numbers themselves? It comes straight back to the uniform slot from the start of this chapter. A Python list can hold anything at once, so [42, "hello", 3.14] mixes an int, a string, and a float, and those three objects have wildly different sizes in memory. A slot of fixed width simply cannot store an object of unknown width. So it stores the one thing that is always the same size: an 8-byte address pointing at the real object elsewhere on the heap. The reference is the price the list pays for holding any type in every slot.

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 in the way. The size difference is not subtle, and 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, roughly 36 bytes per element. The packed array holds the identical numbers in ~8.2 MB, about 8 bytes each. That is the same data in 4.4× less memory. The array pays no object tax and stores no pointers, just values back to back.

INPUTimport sys
from array import array
n = 1000
L = list(range(1000, 1000 + n))        # 1000 distinct ints, past the -5..256 cache
A = array('q', range(1000, 1000 + n))  # 'q' = signed 8-byte slots
box = sum(sys.getsizeof(x) for x in L)
print("list  block :", sys.getsizeof(L))
print("list  boxed :", box)
print("list  TOTAL :", sys.getsizeof(L) + box, "->", round((sys.getsizeof(L)+box)/n, 1), "B/elem")
print("array TOTAL :", sys.getsizeof(A), "->", round(sys.getsizeof(A)/n, 1), "B/elem")
print("itemsize    :", A.itemsize, "B == the stride")

OUTPUTlist  block : 8056
list  boxed : 28000
list  TOTAL : 36056 -> 36.1 B/elem
array TOTAL : 8320 -> 8.3 B/elem
itemsize    : 8 B == the stride

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, and a miss out to RAM costs ~100 ns. The CPU never fetches one byte. 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, so one miss buys 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.

The flip side makes the point sharper. Imagine the same million values stored not in a block but as a chain, where each one carries the address of the next and they sit scattered anywhere on the heap. Now every hop is a leap to an unpredictable address, so the CPU almost always misses the cache and waits the full ~100 ns for RAM. Worse, the prefetcher sees no fixed stride to guess from, so it cannot run ahead the way it does on a block. Same number of elements, same O(n) walk, but the scattered layout gives the hardware nothing to hold onto.

To prove the speed comes from the layout and nothing else, we walk the same block twice: once in order, then once through a shuffled set of indices. The reads are identical and the count is identical, so the only thing that differs between the two walks is the address pattern:

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. They share the same n, the same O(n), and the same interpreter overhead per step. The only difference is the address pattern. seq marches through consecutive addresses, which is cache-friendly. rnd leaps to random ones, which is a miss almost every time. The result is that the ordered walk ran ~8× faster on our machine. That gap is not 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.

Where does the ~8× come from? Do the back-of-envelope arithmetic. A 64-byte cache line holds 64 / 8 = 8 of our values, so the ordered walk pays one ~100 ns miss and then gets 7 near-free ~1 ns hits. That averages out to (100 + 7 × 1) / 8 ≈ 13 ns per element. The shuffled walk, by contrast, lands on a fresh line almost every read, so it pays close to the full ~100 ns each time. Divide the two and 100 / 13 lands right around the 8× we measured, even though the operation count never changed. The only thing that moved was the layout.

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. The array is the default, the one others must earn their way past. Here is its profile: O(1) indexing, O(1) amortized append, unbeatable cache behaviour, and minimal overhead of about 8 bytes per packed element against 36 for a boxed list. You pay for that with O(n) middle inserts/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. The chapters ahead are exactly those "something elses."

Put the rule to work on one real decision. Say you are holding a million sensor readings that you build up once, then scan again and again to average and plot. You add only at the end, you read by position, and you walk them in order, three green lights, with never a middle insert in sight. That is an array, and specifically a packed one, sparing you the ~28-byte object tax a million times over. The moment the job changed to constant inserts in the middle, you would reach for something else. Matching the layout to the access pattern is the whole skill.

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. Instead it becomes something you compute, namely 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 from 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. It becomes variations on one move.

The everyday transfer 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. →