Linear Structures

Arrays and memory

Contiguous cells and why index access is instant

~11 minLesson 3 of 25Written by Claude Opus 4.8

The humblest data structure there is - a row of boxes in memory - and the one that quietly underpins strings, lists, matrices, and every tensor you will ever meet.

Memory is one long strip of numbered boxes. An array is just a promise: "give me $n$ boxes in a row, all the same size." That single promise - contiguous and uniform - is what makes reading any element instant, and it is also what makes inserting in the middle slow. Everything else in this course is built on top of it.

A street of equal-width houses

Picture a street where every house is exactly the same width and the addresses count up: 100, 104, 108, 112... To find house number

i

, you do not walk past every door - you compute the address in your head: start + i x width. Arrays work identically. Because the boxes are contiguous and uniform, the computer jumps straight to any index. That jump is the whole superpower.

A street of houses in memory

Say an array of 32-bit integers starts at byte $base$ in memory, and each integer occupies $s = 4$ bytes. Element $i$ does not need a search - its location is pure arithmetic. One multiply, one add, one fetch, and you have it, whether $i$ is 0 or 9,999,999:

The address formula (this is why indexing is O(1))

addr (i) = base + i \times s

Here $base$ is where the block starts and $s$ is the size of one element in bytes. The formula never mentions $n$ , the array's length - that is exactly why random access is O(1). Reaching the millionth element costs the same as reaching the first.

# Same cost for A[0] or A[999999] - it's just arithmetic
def get(A, i):
    addr = A.base + i * A.item_size   # one multiply, one add
    return memory[addr]                # one fetch   ->   O(1)

Random access in pseudocode - no loop, no search.

Contiguity buys a second, quieter prize: . When the CPU fetches one element it drags the neighbouring bytes into a fast cache line alongside it, betting you will want them next. Walk an array front-to-back and you mostly hit that cache - often far faster than the Big-O count alone suggests. Scatter the same data across memory (as a linked list does) and you forfeit that bet on every step.

Fixed vs. dynamic

A raw array has a fixed length chosen when it is allocated - you cannot just glue a box onto the end, because the next byte of memory may already belong to something else. A (Python's list, Java's ArrayList, C++'s vector) hides that limit: it keeps spare capacity, and when it runs out it quietly allocates a bigger block and copies everything across. The demo below lets you watch both the pain of the middle-insert and the magic of that regrow.

See the cost: shift, then grow

Two things arrays make you pay for. Inserting in the middle means every later element must slide one slot right to open a gap - so cost grows with how far from the end you insert. Appending to a full dynamic array triggers a resize: allocate double, copy everything, then continue. Switch modes and drive each one; the meters keep the score.

Memory gridpick index · insert

will movemoving nowcopiednew element

012

127

234

341

458

563

insert at index = 3

shifted last insert: 0array length: 6

Pick an index, then Insert - count how many later elements have to move.

Rare pain, cheap on average

A single resize is expensive - it copies all

n

elements, an O(n) jolt. But because capacity doubles each time, resizes get rarer exactly as fast as they get costlier. Sum the copies over many appends and the total stays proportional to the number of appends, so the average append is only about two element-moves. That is amortized O(1) - watch the "moves / appends" readout spike right after a doubling, then drift back toward 2.

Two dimensions, one strip of memory

Memory is one-dimensional, so a 2-D array is a polite fiction. A grid with $C$ columns is stored one row after another - row-major order - and the index arithmetic just flattens the two coordinates into one offset:

addr (r, c) = base + (r \times C + c) \times s (C columns per row)

Element $(r, c)$ lives $r \times C + c$ slots into the flat strip. This is why looping a matrix row-by-row is cache-friendly (you walk memory in order) while column-by-column jumps around and thrashes the cache. Same data, same Big-O, very different wall-clock time - the layout is doing the talking.

Check yourself

Inserting a value at the front of an n-element array must shift every later element over, so it costs:

Doubling capacity on every resize makes the cost of append, averaged over many appends:

Why is reading A[i] O(1) but inserting in the middle O(n)?

Contrast a single address computation against a cascade of shifts. Try to state it, then check.

Lock it in

An array is one promise: $n$ boxes in a row, all the same size - contiguous and uniform.
Random access is O(1) because $addr (i) = base + i \times s$ never mentions the length.
Inserting in the middle is O(n): every later element slides one slot right to open a gap.
A dynamic array keeps spare capacity and doubles on overflow, making append amortized O(1).
A 2-D array is flattened row-major, so row-by-row loops stay cache-friendly.

Primary source

Harvard's CS50x builds memory, arrays, and pointers up from zero - the clearest first pass on what "contiguous" actually means at the byte level. For the dynamic-array resizing analysis and clean reference implementations, work through the arrays and resizing-array material on Princeton's algs4 booksite.

Ask your teacher

Want to see how delete-in-the-middle mirrors insert, or why a linked list trades O(1) insert for O(n) access and lost cache locality? Ask and I will build the follow-up. Here is the thread worth pulling: the array is literally the atom that becomes a vector, then an embedding, then a tensor on the LLM path - a batch of token embeddings is nothing more exotic than a 2-D array, i.e. a matrix, laid out in exactly the row-major memory you just watched.