Chapter 2 — Arrays and the Memory You Can Feel

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds

“Everyone then who hears these words of mine and does them will be like a wise man who built his house on the rock. And the rain fell, and the floods came, and the winds blew and beat on that house, but it did not fall, because it had been founded on the rock.” — Matthew 7:24–25

Why This Matters

Last week you learned to count the cost. You predicted how a program would scale, you instrumented it, you ran it, and you let the measured curve tell you whether your prediction was honest. That was the architect’s first move: measure, predict, confirm.

This week you build the first foundation that every other structure in this book stands on. The array.

Here is the thing about the array that no one tells you in a beginner course: the array is not really a Python concept, or a Java concept, or a C++ concept. The array is a hardware concept. An array is what you get when you ask the machine for a run of memory and agree, in advance, that every slot will be the same size. That single agreement — same size, side by side — is what buys you the most valuable property in all of computing: you can compute exactly where the tenth element lives without looking at the first nine. One multiplication, one addition, one fetch. O(1). Random access. The whole machine is built to make that fast.

In Coding 1 you saw this with your own hands. In C++ you wrote int scores[100]; and you knew — because we made you know — that this was one hundred integers laid end to end in memory, and that scores[i] was nothing more than “start at the address of scores, walk forward i times four bytes, and read.” You wrote int* p = scores; and watched *(p + i) mean the exact same thing as scores[i]. The pointer was the truth and the subscript was the sugar. In Java you wrote int[] scores = new int[100]; and the memory was hidden behind a reference, but the shape was the same: a contiguous block, fixed element size, O(1) indexing.

Python hides all of this. You write scores = [0] * 100 and the language tells you nothing about what is happening underneath. That hiding is convenient and it is also a trap, because you cannot reason about the cost of a structure whose memory you cannot see. So this week we are going to see through Python. We are going to take the C++/Java mental model you already own — explicit memory, fixed element size, address arithmetic — and use it as X-ray glasses on the Python list. By the end you will know precisely why append is usually instant and occasionally expensive, why a Python list of integers costs more than a C++ vector<int>, and why walking an array in order is faster than walking it in a scramble even though both are “O(n).”

The Christian question for the week is the wise builder’s question: what is built on a firm foundation? The array is the rock under the house. Get the array wrong — misjudge its costs, reach for it when its costs don’t fit — and every structure you stack on top inherits the crack. The rain comes for every house. The question is what you founded it on.

2.1 — What an Array Is (At the Level of the Metal)

Strip away every language. Here is an array.

You ask the operating system for a block of memory — say, room for ten 4-byte integers, so forty contiguous bytes. The OS hands you back the address of the first byte. Call it base. That is the entire structure. There is no header listing the elements, no chain of pointers, no bookkeeping between the slots. Just forty bytes in a row, and one number — base — that says where they start.

Now you want element i. The machine computes:

address_of(array[i]) = base + i * element_size

That is the whole secret. Element size is fixed (4 bytes for our int), so the address of any element is a single multiply-and-add away from base. The machine doesn’t walk the array. It doesn’t count. It computes the address directly and fetches. This is address arithmetic, and it is why indexing is O(1) — constant time, independent of i and independent of the array’s length. Element zero and element nine million cost exactly the same.

In C++ you can watch this happen:

int scores[10];
int* base = scores;          // base is the address of element 0
int x = scores[7];           // sugar for: *(base + 7)
int y = *(base + 7);         // identical: walk 7 * sizeof(int) bytes, read
// x == y, always

scores[7] and *(base + 7) compile to the same instructions. The subscript operator is address arithmetic wearing a friendly face.

Two consequences fall out of “same size, side by side,” and you must internalize both:

1. Random access is O(1). Any element, any time, one address computation. This is the array’s superpower.
2. The element size must be fixed and known. If elements could be different sizes, base + i * element_size would be a lie — you wouldn’t know how far to jump. This is why a C++ int[] holds only ints, and a Java int[] holds only ints. Same size is not a convenience; it is the precondition for the address arithmetic to work.

Hold on to point 2. It is the seed of the entire Python-versus-C++ cost story we reach in §2.5.

Coach’s Note — When you indexed an array in Coding 1, you were doing pointer arithmetic whether you knew it or not. C++ made it visible; Java hid the pointer but kept the math; Python hides both. The architect keeps the C++ picture in their head in every language, because the picture is what tells you the cost. You are not learning a new structure this week. You are learning to see the one you already used.

2.2 — Cache Lines: Why Order Is Fast

Here is a fact that the Big-O notation cannot tell you, and that will haunt — productively — the rest of this book: not all memory accesses cost the same, even though Big-O pretends they do.

Your CPU is much faster than your main memory (RAM). If the CPU had to wait for RAM on every single read, it would spend almost all its time idle. So the hardware cheats, brilliantly. Between the CPU and RAM sit small, fast caches (L1, L2, L3). When the CPU reads one address from RAM, it does not fetch just that byte. It fetches a whole cache line — typically 64 bytes — and stashes the line in cache. The bet is simple and usually right: if you just read this byte, you’ll probably want the bytes right next to it very soon. That bet is called spatial locality.

Now connect it to the array. An array is contiguous. The elements sit next to each other in memory. So when you walk an array front-to-back, the very first read pulls a whole cache line — say sixteen 4-byte integers — into fast cache. The next fifteen reads are then nearly free, because the data is already there. You pay one slow trip to RAM and get sixteen elements out of it. Walk an array in order and the hardware is on your side.

Walk memory in a scramble — random indices, or chasing pointers all over the heap — and you lose the bet on almost every access. Each read lands on a different cache line, forces a slow trip to RAM, and the fifteen neighbors you dragged along go unused. Same number of reads. Same O(n). Wildly different wall-clock time.

# Both loops touch n elements — both are "O(n)". They are NOT equally fast.
def sum_in_order(data):
    total = 0
    for i in range(len(data)):      # 0, 1, 2, 3, ... — sequential, cache-friendly
        total += data[i]
    return total

def sum_in_scramble(data, order):
    total = 0
    for i in order:                 # a shuffled list of indices — cache-hostile
        total += data[i]
    return total

On a large enough array, sum_in_order can be several times faster than sum_in_scramble, and nothing in the Big-O notation predicts that. Both are O(n). The difference is the constant factor, and the constant factor here is cache behavior.

This is the deepest theme of Phase 1, first met in Chapter 1 and now made concrete: asymptotics describe how cost grows; they do not describe how much the cost is. Two O(n) algorithms can differ by 10x because of the memory access pattern. The array’s contiguity is not just about O(1) indexing — it is about being kind to the cache, and that kindness is a constant-factor gift that compounds across millions of operations. When, in Week 3, a linked list with the same Big-O loses a footrace to an array, this is the reason. File it away.

Coach’s Note — “It’s all O(n), so it doesn’t matter” is the single most expensive sentence a junior engineer says. At small n the constant factor is invisible. At the scale where it matters, the constant factor is the performance. Cache locality is the first place you will feel this, and the array is the structure that gives it to you for free. Respect the gift.

2.3 — Fixed-Size Arrays and the Growth Problem

The classic array has a wart, and you felt it in Coding 1 without maybe naming it: its size is fixed at creation.

When you wrote int scores[100]; in C++, you committed to one hundred slots. Not 99, not 101. The size is baked into the request to the OS — it has to be, because the OS needs to know how many contiguous bytes to set aside. The same is true of a Java int[]: new int[100] is one hundred slots forever. You cannot append a 101st element to a full array. There is no room. The memory immediately after your array belongs to something else.

So what do you do when you don’t know in advance how many elements you’ll have? Real programs almost never know. You’re reading lines from a file, names from a user, events from a network — the count is whatever it turns out to be.

The naive answer is “make a new, bigger array and copy everything over.”

# A fixed-capacity buffer, full. We want to add one more element.
capacity = 4
buffer = [10, 20, 30, 40]        # full
# To "grow", we must:
new_buffer = [None] * (capacity + 1)   # 1) allocate a bigger block
for i in range(capacity):              # 2) copy every existing element
    new_buffer[i] = buffer[i]
new_buffer[capacity] = 50              # 3) write the new element
buffer = new_buffer                    # 4) the old block is now garbage

That works. But look at the cost of “add one element”: you copied all capacity existing elements. That single append was O(n). And if you grow by exactly one slot every time you append, every append copies the whole array, and building up n elements costs 1 + 2 + 3 + ... + n copies — which is O(n²). Building a list of a million elements would cost on the order of a trillion copy operations. Catastrophic.

This is the growth problem, and the structure that solves it is the dynamic array — an array that grows itself, cheaply, on demand. Python’s list, Java’s ArrayList, C++‘s vector, Go’s slice: all of them are dynamic arrays. They all solve the growth problem the same clever way, and that way is one of the most beautiful pieces of cost-accounting in computer science. It’s next.

2.4 — Doubling and Amortized O(1): The Beautiful Trick

The fix for the growth problem is almost too simple to believe: when the buffer fills up, don’t grow by one — grow by a multiple. Double it.

A dynamic array keeps two numbers: its capacity (how many slots the underlying buffer has) and its length (how many slots are actually in use). Appends fill unused slots for free. Only when length equals capacity — when the buffer is genuinely full — do you allocate a new, bigger buffer (twice the size) and copy everything over.

# The shape of append in a doubling dynamic array (pseudocode of what you'll build).
def append(self, value):
    if self._length == self._capacity:      # full — must grow
        self._resize(self._capacity * 2)    # double capacity, copy O(n) elements
    self._buffer[self._length] = value      # the common case: just write
    self._length += 1

Most appends just write into an existing empty slot — O(1). Occasionally one append triggers a resize and copies everything — O(n). The genius is in how rarely the expensive case happens, and the tool for proving it is called amortized analysis: spreading the cost of the rare expensive operations across the many cheap ones.

Let’s account for it honestly. Start with capacity 1 and append n elements, doubling each time the buffer fills. The resizes happen at lengths 1, 2, 4, 8, 16, … and each resize copies that many elements:

Add up the copies across all n appends. The total copying work is:

1 + 2 + 4 + 8 + ... + (largest power of 2 below n)

That is a geometric series, and here is the fact that makes the whole thing work: a doubling geometric series sums to less than twice its largest term. 1 + 2 + 4 + 8 + 16 = 31, which is less than 2 * 16 = 32. In general, 1 + 2 + 4 + ... + n ≈ 2n. So the total copy work to build an array of n elements is about 2n — which is O(n) total, spread across n appends. That comes to O(1) per append, on average. Each append “pays” a constant amount; the rare expensive copies are covered by the savings banked on all the cheap appends before them.

That is amortized O(1). It does not mean every append is fast. It means the average over a long run of appends is constant, even though individual appends occasionally spike to O(n). A single append might copy a million elements. But you only paid that price once on the way to a million, and it was bankrolled by the 999,999 free appends around it.

Coach’s Note — Amortized is not the same as average-case, and it is not a hand-wave. Average-case talks about probability over random inputs. Amortized makes a guarantee about a sequence of operations: across any n appends, total cost is O(n), period — no probability involved. When a recruiter asks “what’s the cost of append on a Python list?” the correct, complete answer is “amortized O(1) — usually constant, but a resize occasionally makes one append O(n), and the doubling growth policy keeps the total at O(n) across n appends.” That full sentence is the difference between someone who memorized a table and someone who understands the structure.

Why double, specifically? Why not grow by a fixed 100 slots each time, or by 1.5x? The growth factor is a real engineering decision with a real tradeoff — bigger factor means fewer copies but more wasted memory; smaller factor means less waste but more copies. You will measure this tradeoff with your own hands in this week’s project and recommend a default the way a standard-library author would. (Spoiler the project will make you earn: growing by a fixed k is O(n²) and doomed; the survivors are the multiplicative policies, and the famous ones really do cluster around 1.5x to 2x for good reasons.)

2.5 — Python’s list Is a Dynamic Array (of Pointers)

Now we turn the X-ray glasses on Python. When you write this:

nums = []
for i in range(1000):
    nums.append(i)

…CPython is running exactly the doubling dynamic array from §2.4 under the hood. A Python list is a dynamic array. It over-allocates (keeps spare capacity so appends are usually free) and resizes by a growth factor when full. Everything you just learned is literally how list.append behaves. That’s why the Python docs and every serious reference say list.append is amortized O(1) — now you know what that phrase is buying.

But here is the crucial difference from your C++ int[], and it is the cost lesson of the section. A C++ vector<int> stores the integers themselves, contiguously: forty bytes hold ten 4-byte ints, end to end. A Python list does not store the integers. It stores pointers to integer objects that live elsewhere on the heap.

Recall §2.1, point 2: the array’s address arithmetic requires every slot to be the same size. A Python list can hold an int, a str, another list, anything — objects of wildly different sizes. The only way to keep the slots uniform is to make each slot hold not the object but a pointer to the object (8 bytes on a 64-bit machine, always the same size whatever it points at). So a Python list is a contiguous array of 8-byte pointers, and each pointer aims at a separately-allocated Python object scattered somewhere on the heap.

C++ vector<int> {10, 20, 30}:        Python list [10, 20, 30]:

  [ 10 ][ 20 ][ 30 ]                   [ ptr ][ ptr ][ ptr ]   <- contiguous pointers
   the ints, contiguous                   |      |      |
                                          v      v      v
                                       (int 10)(int 20)(int 30)  <- boxed objects, scattered

This costs you in two ways, and both matter:

1. Memory. Each Python int is a full object with a header (reference count, type pointer) — roughly 28 bytes — plus the 8-byte pointer in the list slot. Storing a million small integers in a Python list costs tens of megabytes. The same million ints in a C++ vector<int> cost 4 MB. That gap is the boxing cost: Python “boxes” every value in an object.
2. Speed (cache, again). The list’s pointers are contiguous and cache-friendly, but the objects they point to are scattered across the heap. Summing a Python list means: read a pointer (fast, cached), then chase it to a random heap location to read the actual int (slow, cache-hostile). You pay the pointer-indirection tax on every element. A C++ vector<int> has the ints themselves contiguous, so the cache bet from §2.2 pays off fully. This is a major reason numeric Python uses NumPy, whose arrays are contiguous unboxed numbers like a C array — you’ll meet that idea again when raw numeric speed matters.

Here is the three-language comparison, the table to burn into memory:

Two footnotes that matter for accuracy. First, Java’s int[] (a primitive array, not ArrayList<Integer>) does store raw contiguous ints like C++ — boxing only happens with the generic ArrayList<Integer>. The primitive-vs-boxed distinction is exactly the Python cost in Java clothing. Second, CPython’s list does not grow by a clean 2x; its over-allocation formula grows the buffer by roughly one-eighth (new = old + old/8 + a small constant), a deliberately modest factor that trades a few more resizes for less wasted memory. The append is still amortized O(1) — any growth by a constant factor (1.125, 1.5, 2, anything > 1) gives amortized O(1); only growing by a fixed amount breaks it. You’ll prove that distinction in the project.

Coach’s Note — “Python is slow” is lazy. The honest statement is: Python trades raw memory layout for flexibility, and that trade has a measurable price in cache misses and boxing. An architect doesn’t sneer at the trade — sometimes flexibility is exactly worth it. An architect names the trade, so that when raw numeric throughput is the constraint, they reach for NumPy or drop to C, and when developer flexibility is the constraint, they happily pay the tax. The skill is knowing which constraint you’re under. That is the whole book.

2.6 — The Array Cost Table

Here is the array’s complete cost profile. This is the first row of the master cost table you will fill in over the next six chapters — one structure per row, memorized cold, the way a doctor knows lab reference ranges.

Read this table as a shape, not as facts to recite. The array is brilliant at the ends and at random reads, and terrible in the middle. Append, pop, index — all cheap. Insert-at-front, delete-from-middle — all O(n), because contiguity that gives you O(1) indexing is the same contiguity that forces you to shift everyone over when you open or close a gap. The array’s strength and its weakness are the same property viewed from two sides.

# Why insert-at-front is O(n): everyone shifts right.
data = [10, 20, 30, 40]
data.insert(0, 5)        # 5 goes to front -> [5, 10, 20, 30, 40]
# Internally: 40->slot4, 30->slot3, 20->slot2, 10->slot1, then 5->slot0.
# Four elements moved to insert one. With a million elements, a million moves.

When the data has lots of front/middle insertion and deletion, the array’s O(n) middle starts to hurt — and that is precisely the workload where next week’s linked list claims it can do better (O(1) insert/delete if you already hold the spot). Whether the linked list actually wins that race — given the cache lesson of §2.2 — is the cliffhanger of Chapter 3. Hold the question.

2.7 — When the Array Is the Right Tool (and When It Isn’t)

The architect’s whole job is choosing, so let’s choose. Reach for an array (or its dynamic-array cousin, the Python list) when:

• You append and read far more than you insert/delete in the middle. This is most programs. Building a collection and then iterating it is the array’s home turf.
• You need fast random access by index. “Give me the 5,000th record” is O(1) on an array and painful on a linked list.
• You iterate the whole thing often, in order. Cache locality (§2.2) makes sequential scans of an array faster than any pointer-chasing structure, often by a large constant factor.
• Memory is tight and the elements are uniform numbers. A contiguous unboxed array (C array, C++ vector<int>, Java int[], NumPy array) is the most compact way to hold n numbers, full stop.

Reach for something else when:

• You insert and delete in the middle or at the front constantly. Every such operation is O(n) on an array. (Candidate: linked list — Chapter 3. Verify it actually wins — it often doesn’t.)
• You need fast membership tests (“is X in here?”) on large data. Search is O(n) on an unsorted array. (Candidate: hash table — Chapter 5, average O(1).)
• You need the data kept in sorted order with fast lookup and fast insertion. (Candidate: balanced tree — Chapter 6.)
• You need last-in-first-out or first-in-first-out discipline as the interface. (Candidate: stack/queue — Chapter 4, often backed by an array anyway.)

Notice that several of those “something elses” turn out to be built on top of an array — a stack and a queue are usually just an array with a restricted interface. The array is the rock under the house. Even the structures that beat it in some workload often stand on it. That is why we built the foundation first.

Coach’s Note — “Just use a list” is the right default in Python because its costs fit the vast majority of programs: append-heavy, index-heavy, iterate-heavy. The architect’s discipline is not to distrust the default — it’s to know exactly when the default’s costs stop fitting the problem, and to have the next structure ready when they do. You earn that knowledge by building the default yourself, which is exactly what the project asks.

2.8 — Common Bugs

The bugs that bite when you work with arrays and dynamic arrays — and when you build one.

Bug: Off-by-one between capacity and length. You let append write at index length but never checked it against capacity first, so you wrote one past the end of the buffer. Example: self._buffer[self._length] = value when self._length == self._capacity — IndexError (or, in C/C++, silent memory corruption, which is worse). Fix: Always grow before you write when length == capacity. Capacity is the buffer’s size; length is how much is used; length <= capacity is an invariant you check on every append.

Bug: Multiplying a list of mutable objects with * and getting shared references. Example: grid = [[0] * 3] * 3 makes three references to the same inner list. grid[0][0] = 1 changes all three rows. Fix: Build independent rows: grid = [[0] * 3 for _ in range(3)]. The * operator copies the reference, not the object — a direct callback to Coding 1’s reference-vs-value lesson.

Bug: Treating list.insert(0, x) or list.pop(0) as cheap inside a loop. Each is O(n); in a loop you’ve built an O(n²) program by accident. Example: while data: process(data.pop(0)) — looks innocent, secretly quadratic because every pop(0) shifts the whole list left. Fix: If you need fast front operations, you do not want an array — you want a deque (Chapter 4). Pop from the end (pop(), O(1)) when order allows, or reverse your thinking.

Bug: Assuming append is always O(1) and being surprised by a latency spike. Example: A real-time loop that appends to a list of millions occasionally stalls — that’s a resize copying the whole buffer in one append. Fix: It’s amortized O(1), not worst-case O(1). If you know the final size, pre-size the buffer ([None] * n) to avoid resizes entirely. Knowing the difference between amortized and worst-case is the whole point of §2.4.

Bug: Reading sys.getsizeof(my_list) and thinking it tells you the memory the data uses. Example: sys.getsizeof([1, 2, 3]) reports the size of the list’s pointer array and header — not the integer objects the pointers aim at. The boxed ints are extra (§2.5). Fix: To count the real footprint, add the list’s own size plus the size of each element object. The pointer array is only part of the cost; the boxing is the rest.

Bug: Iterating a list by repeatedly indexing in a hot loop and assuming it’s as fast as it’d be in C. Example: for i in range(len(data)): total += data[i] pays pointer-indirection and boxing on every element (§2.5); it is correct but not C-fast. Fix: For raw numeric throughput, reach for NumPy (contiguous unboxed) or a different language. For correctness and flexibility, the Python list is fine — just don’t expect C numbers from it. Name the trade.

2.9 — Reps

Open the exercises for the full set. This week’s reps build the muscles you’ll need for the project: predicting cost from structure, feeling cache locality in real timings, and hand-building the doubling logic. AI stays OFF — Phase 1. You cannot reason about the cost of a structure you have never built yourself.

A preview:

• Rep 1 — Predict, then measure, the cost of insert(0, x) in a loop vs append.
• Rep 4 — Watch a Python list resize by printing sys.getsizeof as it grows; find the resize points.
• Rep 7 — Build the resize-and-copy loop by hand on a raw fixed buffer.
• Rep 11 — Measure sequential vs scrambled traversal and explain the gap with §2.2.

Do every one. The reps are the conditioning; the project is the game.

2.10 — This Week’s Project

You’re ready for Project 2 — Build a Dynamic Array, in Project 2.

You will implement a growable array on top of a fixed-capacity buffer — without using list.append for your storage, because the whole point is to build the thing append does. You’ll support get, set, append (with doubling on full), length, and __str__, and you’ll write tests that prove the capacity doubles and that append is amortized O(1). The Medium tier adds insert and delete with measured O(n). The Hard tier makes you compare growth policies — 2x vs grow-by-fixed-k vs 1.5x — across a million appends, and recommend a default the way a standard-library author would, with the numbers to back it.

Like every Phase 1 project, it ends in a measurement memo. The code is half the grade; the honest accounting of what it cost is the other half.

2.11 — Coach’s Final Word for Week 2

This week you took the structure you’ve used since your first program and you saw through it. You know now that an array is contiguous memory with a fixed element size; that indexing is one multiply-and-add; that the cache rewards you for walking in order; that append is amortized O(1) because doubling banks the cost of the rare expensive resize across many cheap ones; and that Python’s friendly list is a dynamic array of pointers to boxed objects, paying memory and cache for its flexibility.

You did not memorize a cost table. You earned one, by understanding why each cell holds the value it holds.

If you find the amortized-O(1) argument slippery: that’s the gap. Build the array in the project, watch the resizes happen, and the argument will become something you can feel instead of something you recite. Close it.

The wise builder built on the rock, and the house stood when the storm came. The array is the rock. Every structure in this book stands on memory laid out the way you now understand it. Found your house well.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 2 and build your dynamic array. After that, Chapter 3 — linked lists and the cost of pointers, where we ask whether the array’s O(n) middle can really be beaten.

Previously: Chapter 1 — the architect’s question: measure, predict, confirm.