On this page

How Data Structures Live in Memory

Why this exists

Big-O counts operations. The machine does not execute operations; it moves bytes between a CPU and a memory system that is roughly a hundred times slower than the CPU for anything that is not already close by. A linked list and an array both give you traversal. On the machine this lesson was written on, traversing four million integers in order took 2.9 ms and traversing the same integers in a random order took 23.5 ms — an 8x gap for identical Big-O and an identical number of additions. The gap is not noise and it is not an implementation detail. It is the shape of modern hardware showing through, and it decides interviews, benchmarks and production incidents alike.

The history matters because it explains why textbooks are quiet about this. In the 1970s and 1980s, when CLRS-style analysis crystallised, a memory access cost roughly the same as an arithmetic instruction. The random-access machine (RAM) model — every memory cell reachable in unit time — was a reasonable approximation. Since then CPU speed has grown far faster than DRAM latency. A main-memory access today costs on the order of 60–100 ns; the CPU can execute a few hundred simple instructions in that time. To hide the gap, hardware grew a hierarchy of caches, and the price of an algorithm became dominated by how many times it misses those caches rather than how many instructions it executes.

This lesson gives you the model you need to predict that price. You will learn how arrays, linked structures, hash maps and trees are laid out in bytes; what a cache line is and why 64 bytes is the real unit of memory traffic; why vector beats list in C++ even for insertions in the middle; why Python's dict is a pair of arrays rather than a tree of nodes; and how much an "integer" actually costs in Python, Java, C++ and JavaScript. Every number in it was measured with a script or verified against the implementation's source, and every number that depends on hardware is marked as such.

It sits in Module 0 between Complexity Analysis, which teaches the counting model, and Your Language's Data Structures, which catalogues what each standard library gives you. The capstone asks you to measure everything claimed here on your own machine. Treat that as the real test of understanding: if you can predict the curve before you run the benchmark, you have the model.

When memory layout decides the winner

Two solutions with the same Big-O are not equal, and some problems hint that layout is the whole point. Learn to read the signals.

If the problem or situation says…Think of…
"in place", " extra space", "without allocating a new array"Rotating, reversing or compacting a contiguous block; cyclic replacements; the first row/column as scratch space
"the array is huge", "millions of elements", "streaming"Sequential access patterns, cache-friendly scans, avoiding pointer-per-element structures
"matrix", "grid", "2-D array"Row-major vs column-major traversal; blocking/tiling; a flat n*m array instead of a list of lists
"design a hash map / hash set / LRU cache"Open addressing vs chaining; load factor; the array-plus-linked-list combination and its pointer cost
"your solution is too slow" / a TLE with the right complexityConstant factors: boxing, pointer chasing, random access, allocation inside the loop
"insert into the middle of a sorted sequence many times"Shift cost of an array vs walk cost of a linked list — the array usually wins (Stroustrup's experiment, below)
"tiny ", "at most 16 elements", "inner loop of a hot path"Linear scan over a few cache lines beats binary search, hashing and trees
"many threads update counters"False sharing on one cache line; pad or shard the counters
"memory limit is tight", "out of memory with 10 million objects"Per-object overhead: 28 bytes per Python int, 16 bytes per Java Integer; use typed/primitive arrays
"sort then scan is fast enough"Sorting is cache-friendly; a sorted array plus a single pass can beat a hash set at scale

Intuition and first principles

Bytes, words and addresses

Memory is one long array of bytes, numbered from zero. The number of a byte is its address. On a 64-bit machine addresses are 64-bit integers, which is why a pointer costs 8 bytes. A word is the natural unit the CPU moves in one register: 8 bytes on today's mainstream machines. An int32 occupies 4 consecutive bytes; a double occupies 8; a pointer occupies 8.

Everything a program stores lives at some address, and every data structure is a convention about which addresses hold what. The CPU can do two things with an address: load the bytes there into a register, or store a register's bytes there. There is no "follow the list" instruction and no "find the key" instruction; those are sequences of loads, and the time they take is the time the loads take.

Stack versus heap

The stack is a region that grows and shrinks with function calls. Local variables of known size live there; allocation is a single subtraction from the stack pointer and deallocation is free when the function returns. Because the stack is reused constantly, its top is almost always in the L1 cache. The heap is everything you allocate dynamically: new, malloc, every Python object, every Java object, every JavaScript object that escapes a function. Heap allocation is a call into an allocator that must find a free block, which costs tens to hundreds of nanoseconds, and heap objects can land anywhere, which is the root of the pointer-chasing problem below. The allocator itself is an algorithmic topic covered in Memory Allocators.

The practical rule: a structure whose elements are all in one heap block (an array) is one allocation and one address range; a structure with one heap block per element (a linked list, a tree of nodes, a list of boxed objects) is allocations scattered over the address space.

The array: address arithmetic

An array stores elements of a fixed size bytes contiguously starting at a base address . The address of element is

This single formula is why array indexing is and why it is also fast : a multiply and an add, then one load. Element 0 of a 6-element int32 array at base 0x1000 lives at 0x1000, element 5 at 0x1014; the whole array occupies 24 bytes. Because they are adjacent, loading element 0 brings elements 1 to 15 along for free, as the cache-line section shows.

The formula also explains the costs. Insertion at position must move elements one slot to the right so that the formula still holds for them: moves, in the worst case, but each move is a copy of adjacent bytes that the hardware handles very efficiently (memmove copies gigabytes per second). Deletion is the mirror image. Append is if there is spare capacity and when the block must be reallocated and copied.

Dynamic arrays and growth factors

A dynamic array (std::vector, ArrayList, Python list, a JavaScript Array) keeps a capacity larger than its size and grows the capacity geometrically when it runs out. Geometric growth is what makes appends amortised : if the capacity multiplies by a factor on each reallocation, the total bytes copied over appends is a geometric series bounded by . Arithmetic growth (add a fixed 100 slots each time) would copy bytes in total. The proof is in the Correctness section.

The factor is an implementation detail, and it varies more than people assume. These are the values in the current sources at the time of writing; all of them can change between versions:

ImplementationGrowth ruleEffective factorSource
CPython listnew_allocated = (newsize + (newsize >> 3) + 6) & ~3about 1.125x for large lists; pattern 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, …Objects/listobject.c, list_resize
OpenJDK ArrayListnewLength(oldCapacity, minGrowth, oldCapacity >> 1)1.5xjava/util/ArrayList.java, grow
libstdc++ std::vector_M_check_len: grow by at least size()2xbits/stl_vector.h
MSVC STL std::vector_Geometric = _Oldcapacity + _Oldcapacity / 21.5xstl/inc/vector, _Calculate_growth
V8 JSArray elementsold_capacity + (old_capacity >> 1) + 161.5x plus 16 slotssrc/objects/js-objects.h, NewElementsCapacity

Measured on CPython 3.14.6, an empty list that receives appends one at a time passes through capacities 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128, 148, 172, 200, 232, 268, 308 — the ratio between consecutive capacities settles around 1.15 and converges to 1.125. CPython's mild factor trades a little more copying for less wasted memory, which fits a language where every list slot is only a pointer. The 2x of libstdc++ minimises copies; the 1.5x of MSVC and Java is a compromise, sometimes justified by the observation that with a factor below the golden ratio, freed blocks from earlier reallocations can be coalesced to fit a later one.

Why you still call `reserve`

Amortised hides a constant: with factor 2 every element is copied on average once more after its first write, with factor 1.125 about eight times. When you know in advance, vector.reserve(n), new ArrayList<>(n) and [None] * n in Python turn those copies into zero and, more importantly, give you one contiguous block whose address never changes.

Pointers, references and pointer chasing

A pointer is an address stored as data. A reference in Java, Python or JavaScript is a pointer that the language manages for you — you cannot do arithmetic on it, but it costs the same 8 bytes (or 4 with compression) and it incurs the same load. A linked list node holds a value and a pointer to the next node; a tree node holds a value and two or more pointers; a Python list holds pointers to int objects that live elsewhere.

Pointer chasing is following a chain of such pointers: load node, read its next field, load that node, read its next, and so on. Each step depends on the result of the previous load, so the CPU cannot start the next load until the current one returns. If each node lives on a different cache line that is not in cache, each step pays a full memory latency. A sequential array scan, by contrast, has no such dependency: the addresses are known in advance, the hardware prefetcher streams them, and several loads are in flight at once.

This is the single most important mechanism in this lesson. pointer chasing with a cache miss per step costs about ns; sequential scanning costs about ns. That is the 30x–100x gap behind "same Big-O, different speed".

Mechanics

The cache hierarchy

Between the CPU core and DRAM sit several levels of cache: small, fast memories holding copies of recently used lines. Typical latencies for a current desktop or server core — typical and machine-dependent, so measure yours — are:

LevelTypical sizeTypical latencyNotes
L1 data32–64 KB per coreabout 1 ns (4–5 cycles)Split instruction/data; the stack top lives here
L20.5–2 MB per coreabout 4 ns (12–16 cycles)Private per core
L38–96 MB sharedabout 10–20 ns (30–60 cycles)Shared by all cores on a die
DRAMgigabytesabout 60–100 nsPlus queuing under load; worse across NUMA nodes

The ratio from L1 to DRAM is around 100x. How Computers Work covers the hardware; here we care only about the consequence: the cost of a memory access depends on where the data is right now, and where it is depends on what you touched recently.

flowchart LR
    CPU["Core<br/>registers"] -->|"~1 ns"| L1["L1 data<br/>32-64 KB"]
    L1 -->|"~4 ns"| L2["L2<br/>0.5-2 MB"]
    L2 -->|"~10-20 ns"| L3["L3 (shared)<br/>8-96 MB"]
    L3 -->|"~60-100 ns"| DRAM["DRAM<br/>gigabytes"]
    DRAM -->|"~100 us"| SSD["SSD / disk<br/>(virtual memory)"]

Cache lines and locality

Caches do not move single bytes. They move cache lines of 64 bytes (on all mainstream x86 and most ARM designs; a few Apple and IBM parts use 128). When you load the 4-byte int32 at 0x1004, the hardware fetches all 64 bytes from 0x1000 to 0x103F into L1. The next 15 integers of the array are now free.

Two kinds of locality make caches work. Spatial locality: if you touched address , you will probably touch soon — true for array scans, false for pointer chasing. Temporal locality: if you touched , you will probably touch again soon — true for loop counters, small lookup tables and the top of the stack. Data structures that respect both run at cache speed; structures that respect neither run at DRAM speed.

Rule of thumb

Think of every memory access as fetching 64 bytes. The question to ask of a data structure is: of the 64 bytes I just paid for, how many will I use before they are evicted? An int32 array uses 64 of 64. A linked list of int32 with two 8-byte pointers uses at most 20 of 64 and usually only one node per line.

Prefetching and strided access

Modern cores include a hardware prefetcher that recognises sequential and constant-stride access patterns and fetches the next lines before the program asks for them. This is why a sequential scan can run faster than the DRAM latency would suggest: the loads overlap. The prefetcher is defeated by patterns it cannot predict — random indices, pointer chasing, and strides larger than a page (4 KB), where it typically stops.

A stride experiment shows the cache line directly. Summing every -th int32 of a 256 MB array on the test machine gave:

Stride (ints)Bytes per stepElements touchedTimens per touch
1467.1 M69 ms1.0
2833.6 M42 ms1.3
41616.8 M31 ms1.9
8328.4 M27 ms3.2
16644.2 M24 ms5.7
321282.1 M22 ms10.6

Touching 16x fewer elements (stride 16, exactly one per cache line) made the loop less than 3x faster, because every cache line still had to be fetched. Once the stride reaches 64 bytes, each touch costs a whole line; the time is set by memory bandwidth, not by the number of additions. These values are indicative for one machine; the shape — flat cost per line, not per element — is universal.

Row-major versus column-major traversal

A 2-D array must be stored as a 1-D block. Row-major order (C, C++, Python lists of lists, NumPy default, JavaScript arrays of arrays) stores row 0 then row 1; element of an matrix sits at . Column-major (Fortran, MATLAB, Julia, most BLAS libraries) stores column 0 first. Traversing in the stored order touches consecutive addresses; traversing against it jumps bytes per step — one cache line per element once , and one TLB miss per element once exceeds a page.

Measured with a compiled C++ loop summing an int32 matrix both ways (best of three, MSVC /O2):

NMatrix sizeRow-majorColumn-majorRatio
10244 MB0.60 ms5.4 ms8.9x
204816 MB2.5 ms48 ms19x
409664 MB10.7 ms329 ms31x
8192256 MB47 ms1342 ms29x

The ratio grows while the matrix stops fitting in each cache level and then saturates near 30x on this machine. Treat the number as indicative; the mechanism — same arithmetic, same Big-O, one version fetching 64 useful bytes per line and the other fetching 4 — is what you should remember. The classical fix is loop interchange (traverse in storage order) or tiling: process the matrix in blocks small enough that a block of both operands fits in cache. Matrix transposition and multiplication in every serious numeric library are tiled for exactly this reason.

Trace table: addresses and cache lines

Take a 6-element int32 array at base 0x1000. Each element is 4 bytes; the cache line is 64 bytes, so the line index is and the line starts at . Computed by script:

iaddressline startoffset in lineline index
00x10000x1000064
10x10040x1000464
20x10080x1000864
30x100C0x10001264
40x10100x10001664
50x10140x10002064

All six elements share one line: a scan costs one memory fetch. The same array at base 0x1038 — an alignment the allocator is free to give you — straddles two lines:

iaddressline startoffset in lineline index
00x10380x10005664
10x103C0x10006064
20x10400x1040065
30x10440x1040465
40x10480x1040865
50x104C0x10401265

Two fetches instead of one for the same data. This is why performance-sensitive code aligns hot arrays to 64 bytes (alignas(64) in C++, aligned_alloc, or a padded allocation).

Memory layout of hash maps

A hash map is an array plus a policy for collisions, and the two policies have very different layouts. Chaining keeps an array of bucket heads, each pointing to a linked list of entries: one allocation per entry, one pointer chase per collision, and a lookup touches at least two cache lines (bucket slot, then the node). Open addressing stores entries directly in the slot array and resolves collisions by probing to another slot: no per-entry allocation, and with linear probing the probe sequence stays inside one or two cache lines. The Hash Tables lesson covers the algorithms; here is what the four standard libraries actually lay out.

Python dict (CPython 3.6+) uses a compact layout: a small indices array of integers (1, 2, 4 or 8 bytes each depending on table size) that is probed with open addressing, plus a dense entries array of (hash, key, value) triples in insertion order. Lookup hashes the key, probes indices to find an entry number, then reads that entry. The compact layout is why dict preserves insertion order (guaranteed since Python 3.7), why iteration is a sequential scan of entries, and why memory dropped by roughly 20–25% compared with the pre-3.6 layout. The table resizes when two-thirds full.

Java HashMap uses chaining: a Node<K,V>[] table of power-of-two size, each Node holding int hash, K key, V value, Node next. The default load factor is 0.75. When a bucket's chain exceeds TREEIFY_THRESHOLD = 8 entries and the table has at least MIN_TREEIFY_CAPACITY = 64 slots, the chain is converted into a red-black tree of TreeNodes so that a flooded bucket costs instead of ; it reverts to a list below UNTREEIFY_THRESHOLD = 6. (Constants verified in OpenJDK java/util/HashMap.java.) Every entry is a separate heap object, so a lookup is at least two dependent loads plus the key object itself.

C++ std::unordered_map is required by the standard to expose buckets and to keep references to elements stable across rehashing, which in practice forces a node-based chaining design in libstdc++, libc++ and MSVC alike: a bucket array of pointers plus one heap node per element. Default max_load_factor is 1.0. It is the slowest of the four layouts per lookup and the reason "flat" open-addressing maps (Abseil flat_hash_map, Boost unordered_flat_map, Rust's hashbrown) exist.

V8 Map and Set use an ordered hash table: one flat backing array holding a bucket region followed by entries stored in insertion order as [key, value, chain-link] triples; deleted entries are tombstoned and compacted on rehash. The design (after Tyler Close's deterministic hash table) gives average operations and insertion-order iteration, which the ECMAScript specification requires for Map.

Trace table: slot layout for five keys

Insert keys 12, 20, 5, 29, 7 into a table of 8 slots with , computed by script.

Open addressing with linear probing:

InsertHome slotProbesLanded inTable after insert
12404[_, _, _, _, 12, _, _, _]
20415[_, _, _, _, 12, 20, _, _]
5516[_, _, _, _, 12, 20, 5, _]
29527[_, _, _, _, 12, 20, 5, 29]
7710[7, _, _, _, 12, 20, 5, 29]

The cluster in slots 4–7 shows primary clustering: 29 had to probe twice, and 7 had to wrap around. Every probe here stays inside one 64-byte line (8 slots of 8 bytes), so even the longest probe sequence is one cache fetch.

Chaining, same keys: bucket 4 → 12 → 20, bucket 5 → 5 → 29, bucket 7 → 7, the rest empty. Looking up 29 costs the bucket load, the 5 node load, then the 29 node load: three dependent memory accesses to three different heap addresses.

CPython-style compact dict, same keys and the same probing over the indices array:

StructureContents
indices (8 slots)[4, _, _, _, 0, 1, 2, 3]
entries (dense, insertion order)(12, v12), (20, v20), (5, v5), (29, v29), (7, v7)

The indices array carries only small integers (one byte each at this size), so the probe sequence is tiny, and the entries array is read sequentially during iteration.

flowchart LR
    subgraph IDX["indices (open addressing, 1-byte each)"]
        I0["0: 4"] ~~~ I1["1: _"] ~~~ I2["2: _"] ~~~ I3["3: _"] ~~~ I4["4: 0"] ~~~ I5["5: 1"] ~~~ I6["6: 2"] ~~~ I7["7: 3"]
    end
    subgraph ENT["entries (dense, insertion order, 24 bytes each)"]
        E0["0: hash, 12, v12"] ~~~ E1["1: hash, 20, v20"] ~~~ E2["2: hash, 5, v5"] ~~~ E3["3: hash, 29, v29"] ~~~ E4["4: hash, 7, v7"]
    end
    I4 --> E0
    I5 --> E1
    I6 --> E2
    I7 --> E3
    I0 --> E4

Memory layout of trees

A binary search tree node holds a key, a value and two child pointers (plus a parent pointer and a colour bit in a red-black tree). Each node is a separate allocation of 32–48 bytes, so a tree of a million keys is a million scattered heap blocks, and a lookup is dependent loads. If the tree does not fit in cache, that is 20 memory latencies, well over a microsecond, versus one or two for a hash lookup. Measured on the test machine, std::map lookups cost 80 ns at and 915 ns at — the growth is the tree falling out of L2, then L3 — against 6 ns and 59 ns for std::unordered_map.

B-trees exist to fix exactly this. A B-tree node packs many keys — hundreds in a database page — into one contiguous block, so one memory (or disk) fetch narrows the search by a factor of hundreds instead of two. The height of a B-tree over a billion keys is 3 or 4. The in-memory relatives (B+-trees with cache-line-sized nodes, "cache-sensitive" search trees) apply the same idea at 64-byte granularity. See Indexing Deep Dive for how databases exploit this and Storage Engines for the LSM alternative.

flowchart TD
    subgraph BST["Binary tree: 1 key per node, 20 pointer chases for 1M keys"]
        A["50"] --> B["25"]
        A --> C["75"]
        B --> D["12"]
        B --> E["37"]
    end
    subgraph BT["B-tree: hundreds of keys per node, 3-4 fetches for 1B keys"]
        N1["12 | 25 | 37 | 50 | 62 | 75 | 87 ..."]
        N1 --> N2["0..11 (block)"]
        N1 --> N3["13..24 (block)"]
    end

Object overhead per language

The "same" integer costs very different amounts of memory depending on the runtime. Measured on CPython 3.14.6 (64-bit Windows build) with sys.getsizeof:

Python objectBytesNotes
0, 1, any int below 2816-byte object header + size field + one 30-bit digit (4 bytes), padded
to 32Two digits
36Three digits
1.024Header + one C double
[]56Header, size, capacity, pointer to the item buffer
list(range(n))56 + 8nExactly, when built from a known length; the item buffer holds 8-byte pointers only
[] after appending 1000 items8856Over-allocated: 1100 slots for 1000 items
()48; (1, 2, 3) is 72Tuples store items inline: 48 + 8 per item, no spare capacity
{}64; 1000 int→int items is 36,952About 37 bytes per entry including the indices array
set()216; 1000 ints is 32,984Open addressing, 16-byte slots, load factor 3/5
"", "a", "hello"41, 42, 46Compact ASCII: 41-byte header + 1 byte per character

So a Python list of one million small ints costs bytes for the list plus bytes for the int objects — about 36 MB for 4 MB of information, a 9x overhead — except that CPython caches the ints from −5 to 256, so a list of a million small ints shares 262 objects. array('i') and NumPy store raw 4-byte values and remove the overhead entirely.

Java: every object has a header — 12 bytes on 64-bit HotSpot with compressed class pointers (the default), 16 without — and is padded to a multiple of 8 bytes. An Integer is 16 bytes (12 header + 4 payload); an int[] of is ; an Integer[] of is for the compressed references plus for the boxes, five times the primitive array. Integer.valueOf caches −128 to 127, so small boxed values are shared, and ArrayList<Integer> pays the boxing on every add and get. Project Lilliput (JEP 450, experimental compact headers, JDK 24+) shrinks the header to 8 bytes; check your JDK before quoting a number.

C++: std::vector<int> is 24 bytes of header (three pointers: begin, end, end-of-capacity; verified sizeof on MSVC) plus exactly 4 bytes per element and whatever spare capacity the growth policy left. A std::list<int> node is 24 bytes (two pointers + 4-byte value + 4 padding) plus allocator overhead of typically 16 bytes, so each 4-byte value costs around 40 bytes and one allocation.

JavaScript (V8): a Smi ("small integer", 31-bit with pointer compression) is stored directly in the slot; any other number is a boxed HeapNumber (a separate 8-byte double plus header). Arrays have elements kinds: PACKED_SMI_ELEMENTS (contiguous Smis, the fastest), PACKED_DOUBLE_ELEMENTS (unboxed doubles), PACKED_ELEMENTS (tagged pointers), and the HOLEY_ variants once an array has a gap. Transitions go one way — write a double into a Smi array and it stays a double array; create a hole with new Array(n) or arr[100] = x and it stays holey. Int32Array and the other typed arrays are raw contiguous buffers with none of this.

Struct of arrays versus array of structs

Store a million particles as an array of structs ({x, y, z, mass, velocity…} each) and a loop that updates only x loads every field of every particle: if the struct is 64 bytes, you use 4 of every 64 fetched. Store them as a struct of arrays (xs[], ys[], zs[]…) and the same loop streams a dense array of x values at full bandwidth and vectorises trivially. This is the design of columnar databases (Parquet, ClickHouse, DuckDB), of entity-component systems in game engines, and of NumPy and Pandas internally. The reverse holds too: a loop that uses every field of one record prefers array of structs, because one line brings the whole record. The question is always the same — of the 64 bytes fetched, how many will be used?

False sharing

Caches keep cores coherent at cache-line granularity: when core A writes a line, every other core's copy of that line is invalidated. If two threads increment two different counters that happen to share a 64-byte line, the line bounces between cores on every write and both threads slow to the speed of the coherence protocol — often 10x–50x slower than independent counters. This is false sharing. The fix is to pad each thread's hot variable to its own line (alignas(64) or std::hardware_destructive_interference_size in C++, @jdk.internal.vm.annotation.Contended in the JDK, striped counters such as Java's LongAdder). It is the first thing to suspect when a "lock-free" structure scales worse than a locked one; see Lock-Free Programming.

Alignment and padding

Hardware prefers an -byte scalar to live at an address divisible by : a 4-byte int at a multiple of 4, an 8-byte double at a multiple of 8. Compilers enforce this by inserting padding between struct fields and at the end, and the struct's own alignment is the largest alignment of its members. Field order therefore changes size. These sizes were verified by compiling with MSVC (/std:c++20); GCC and Clang on x86-64 Linux give the same values for these examples:

#include <cstdint>
#include <cstdio>

struct Padded   { char tag; std::int32_t id; char flag; };   // 1 + 3 pad + 4 + 1 + 3 pad = 12
struct Packed   { std::int32_t id; char tag; char flag; };   // 4 + 1 + 1 + 2 pad = 8
struct Mixed    { char tag; double x; std::int32_t id; };    // 1 + 7 pad + 8 + 4 + 4 pad = 24
struct Reorder  { double x; std::int32_t id; char tag; };    // 8 + 4 + 1 + 3 pad = 16

int main() {
    static_assert(sizeof(Padded) == 12);
    static_assert(sizeof(Packed) == 8);
    static_assert(sizeof(Mixed) == 24);
    static_assert(sizeof(Reorder) == 16);
    static_assert(alignof(Mixed) == 8);
    std::printf("Padded=%zu Packed=%zu Mixed=%zu Reorder=%zu\n", sizeof(Padded), sizeof(Packed), sizeof(Mixed), sizeof(Reorder));
    return 0;
}

Ordering fields from largest to smallest alignment removes the interior padding. A 12-byte struct fits 5 per cache line; the 8-byte reordering fits 8. In an array of a hundred million records that is the difference between 1.2 GB and 800 MB and, more importantly, 60% more records per memory fetch.

What this means for algorithm choice

The lessons in the rest of this course state complexities. Here is how layout bends them in practice:

  • Linear scan beats binary search for tiny . A sorted array of 16 int32s is one cache line. A linear scan is 16 predictable compares; a binary search is 4 compares with unpredictable branches. Measured in compiled C++ on the test machine, linear search won up to about and binary search won from (indicative; the crossover depends on element size, branch predictor and whether the compiler vectorises). This is why std::sort and Timsort switch to insertion sort for small runs and why B-tree nodes are searched linearly or with SIMD.
  • Sort then scan can beat a hash set. Deduplicating or intersecting a hundred million integers with a hash set means a hundred million random probes into a table that does not fit in cache: one DRAM miss each. Sorting them is but every pass is sequential; a merge-sort pass streams at bandwidth. Databases pick hash join or sort-merge join based on exactly this trade-off (Query Planning).
  • Timsort's design is cache design. Its minrun insertion sort works on 32–64 elements — a few cache lines — and its galloping merge mode skips ahead through a run with exponential then binary search, touching few lines when one run dominates. Both exploit the fact that runs are contiguous memory (Sorting & Searching).
  • insert(0, x) on a Python list is but it is a memmove of pointers: measured 44x slower than append at , not the thousands-of-times you might expect from "20,000 operations versus 1", because moving 160 KB of adjacent pointers is nearly free compared with 20,000 scattered accesses.
  • An ArrayDeque beats a LinkedList for queues. Both are per operation; the ring buffer touches one line per 16 elements and the list touches one line and one allocation per element.

The classic demonstration is Stroustrup's experiment (Bjarne Stroustrup, "Software Development for Infrastructure", IEEE Computer, January 2012, and his GoingNative 2012 keynote): generate random integers and insert each into its sorted position in a sequence, then remove them one by one at random positions. The textbook says the linked list should win — insertion once the position is found — and the vector should lose because of the shift. Measured here with MSVC /O2, inserting random integers in sorted order:

nvector, binary search + shiftvector, linear walk + shiftlist, linear walk + linklist / vector (both walking)
1,0000.1 ms0.2 ms0.8 ms3.7x
10,0002.8 ms13.6 ms175 ms13x
50,00072 ms577 ms11,005 ms19x
100,000454 ms1,459 ms61,439 ms42x

Rung 1 — linked list. Walk from the head comparing values ( pointer chases, each a likely cache miss), then splice a node in (, but a heap allocation). Total chases for inserts, each chase a dependent load.

Rung 2 — vector, linear walk. Same number of comparisons, but they stream through contiguous memory with the prefetcher ahead of you; then a memmove of the tail, which is a bandwidth-bound copy. The Big-O is identical to rung 1. The measured time is 13x–42x lower.

Rung 3 — vector, binary search + shift. std::lower_bound finds the position in ; the shift is still but is the only linear part left. Three to five times faster again than rung 2 at large . The remaining cost is pure memmove and could be attacked only by changing the structure (a B-tree-like blocked list, or a skip list).

RungFinding the slotMaking roomAllocationsCache behaviour
Linked list dependent loads relinkone per insertone miss per visited node
Vector, linear streamed compares memmoveamortised prefetched, bandwidth-bound
Vector, binary search memmoveamortised a few misses, then bandwidth

The removal half of Stroustrup's experiment behaves the same way, for the same reason: finding the -th element of a list is a walk; finding it in a vector is address arithmetic.

The lesson is not "never use linked lists"

Linked lists win when you already hold a pointer to the position (an LRU cache's node, an intrusive list in a kernel), when elements are large and must not move, or when you need to splice whole sequences in . They lose whenever finding the position dominates, which is nearly every interview and most application code.

Correctness

Two claims in this lesson deserve proofs rather than assertions.

Claim 1: geometric growth gives amortised append; arithmetic growth does not.

Let the capacity multiply by at each reallocation and suppose appends have been performed, so the final capacity satisfies . The reallocations copied elements in total (each reallocation copies the previous capacity). This is a geometric series bounded by . Dividing by appends gives at most copies per append: 2 for , 3 for , 9 for . Each append therefore costs amortised, with a constant that grows as approaches 1 — exactly the trade-off the growth-factor table shows.

Equivalently, with the potential method of Complexity Analysis: define clamped at 0; a cheap append raises by a constant and a reallocation's copying is paid by the drop in .

Now let the capacity grow by a constant instead. The -th reallocation copies elements, and there are of them, so the total copying is , i.e. per append. Arithmetic growth is quadratic; this is not a constant-factor difference.

Claim 2: the address formula is an invariant, and insertion preserves it.

The array invariant is: for all , element is stored at . Insertion at position moves elements to positions — necessarily from the back to the front so no element is overwritten before it is read (memmove handles the overlap) — then writes the new element at . After the move, every old element is at , which is its new index times plus the base; elements below are untouched; the new element is at index . The invariant holds for all elements. Deletion is the reverse. Because the invariant holds, indexing remains a single multiply-add, and the cache analysis of a scan — consecutive indices, consecutive addresses — remains valid.

Complexity: counting cache misses, not just operations

Big-O in the RAM model counts operations. The external-memory model (Aggarwal and Vitter, 1988) counts block transfers of size between a fast memory of size and a slow memory. Replace "disk block" with "cache line" and int32s, and the model predicts everything measured above:

OperationRAM-model costCache-line transfers (cold)Why
Sequential scan of ints16 ints per 64-byte line, prefetched
Random-order scan of ints (when cache)every access a new line
Linked-list traversalone node per line, dependent loads
Binary search, sorted arrayabout last 4 halvings are inside one line
B-tree search, keys per node compareseach node fetch narrows by
Hash lookup, open addressing expected1–2probe sequence stays in a line
Hash lookup, chaining expected2–3bucket, node, key object
Row-major matrix sumstorage order
Column-major matrix sum (row-major storage)one line per element, TLB misses too

Space complexity has the same two faces. space for a million ints is 4 MB as int32[], 36 MB as a Python list of ints, 20 MB as Integer[], 40 MB as std::list<int>. Whether the structure fits in L2, L3 or only DRAM decides which column of the latency table applies — and, as the row-major measurements show, the ratio between good and bad layouts grows as the data falls out of each cache level. Constants matter most precisely when is large, which is where people assume Big-O takes over.

Implementation: measure sequential versus random access

The canonical experiment. Fill an array with integers, traverse it in index order, then traverse it again in a random permutation of the indices. Same , same additions, same result — only the order of addresses changes. The programs assert that both sums are equal (correctness) and print the timing ratio (which depends on your machine and is deliberately not asserted).

import random
import time


def traverse(data: list[int], order) -> int:
    total = 0
    for i in order:
        total += data[i]
    return total


def main() -> None:
    n = 2_000_000
    data = list(range(n))                 # contiguous array of pointers to int objects
    perm = list(range(n))
    random.Random(42).shuffle(perm)       # same n, same work, different order

    traverse(data, range(n))              # warm-up
    t0 = time.perf_counter()
    s_seq = traverse(data, range(n))
    t1 = time.perf_counter()
    s_rand = traverse(data, perm)
    t2 = time.perf_counter()

    assert s_seq == s_rand == n * (n - 1) // 2
    seq_ms, rand_ms = (t1 - t0) * 1e3, (t2 - t1) * 1e3
    print(f"n={n}: sequential {seq_ms:.0f} ms, random {rand_ms:.0f} ms, ratio {rand_ms / seq_ms:.1f}x")


if __name__ == "__main__":
    main()
import java.util.Random;

public class SeqVsRandom {
    static long traverse(int[] data, int[] order) {
        long total = 0;
        for (int i : order) total += data[i];
        return total;
    }

    public static void main(String[] args) {
        int n = 4_000_000;
        int[] data = new int[n];
        int[] seq = new int[n];
        int[] perm = new int[n];
        for (int i = 0; i < n; i++) { data[i] = i; seq[i] = i; perm[i] = i; }
        Random rng = new Random(42);
        for (int i = n - 1; i > 0; i--) {          // Fisher-Yates shuffle
            int j = rng.nextInt(i + 1);
            int t = perm[i]; perm[i] = perm[j]; perm[j] = t;
        }
        for (int w = 0; w < 3; w++) { traverse(data, seq); traverse(data, perm); }  // JIT warm-up

        long t0 = System.nanoTime();
        long sSeq = traverse(data, seq);
        long t1 = System.nanoTime();
        long sRand = traverse(data, perm);
        long t2 = System.nanoTime();

        long expected = (long) n * (n - 1) / 2;
        if (sSeq != expected || sRand != expected) throw new AssertionError("sums differ");
        double seqMs = (t1 - t0) / 1e6, randMs = (t2 - t1) / 1e6;
        System.out.printf("n=%d: sequential %.1f ms, random %.1f ms, ratio %.1fx%n", n, seqMs, randMs, randMs / seqMs);
    }
}
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>

static std::int64_t traverse(const std::vector<std::int32_t>& data, const std::vector<std::uint32_t>& order) {
    std::int64_t total = 0;
    for (std::uint32_t i : order) total += data[i];
    return total;
}

int main() {
    const std::uint32_t n = 4'000'000;
    std::vector<std::int32_t> data(n);
    std::iota(data.begin(), data.end(), 0);
    std::vector<std::uint32_t> seq(n), perm(n);
    std::iota(seq.begin(), seq.end(), 0u);
    perm = seq;
    std::mt19937 rng(42);
    std::shuffle(perm.begin(), perm.end(), rng);

    using clk = std::chrono::steady_clock;
    traverse(data, seq); traverse(data, perm);           // warm-up
    auto t0 = clk::now();
    std::int64_t s_seq = traverse(data, seq);
    auto t1 = clk::now();
    std::int64_t s_rand = traverse(data, perm);
    auto t2 = clk::now();

    const std::int64_t expected = static_cast<std::int64_t>(n) * (n - 1) / 2;
    assert(s_seq == expected && s_rand == expected);
    double seq_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double rand_ms = std::chrono::duration<double, std::milli>(t2 - t1).count();
    std::printf("n=%u: sequential %.1f ms, random %.1f ms, ratio %.1fx\n", n, seq_ms, rand_ms, rand_ms / seq_ms);
    return 0;
}
import assert from "node:assert/strict";

function traverse(data: Int32Array, order: Uint32Array): number {
  let total = 0;
  for (let k = 0; k < order.length; k++) total += data[order[k]];
  return total;
}

function main(): void {
  const n = 4_000_000;
  const data = new Int32Array(n);
  const seq = new Uint32Array(n);
  const perm = new Uint32Array(n);
  for (let i = 0; i < n; i++) { data[i] = i; seq[i] = i; perm[i] = i; }
  let state = 42;                                   // small deterministic LCG for the shuffle
  const next = () => (state = (state * 1664525 + 1013904223) >>> 0);
  for (let i = n - 1; i > 0; i--) {
    const j = next() % (i + 1);
    const t = perm[i]; perm[i] = perm[j]; perm[j] = t;
  }
  for (let w = 0; w < 3; w++) { traverse(data, seq); traverse(data, perm); }  // JIT warm-up

  const t0 = performance.now();
  const sSeq = traverse(data, seq);
  const t1 = performance.now();
  const sRand = traverse(data, perm);
  const t2 = performance.now();

  const expected = (n * (n - 1)) / 2;               // 8e12 < 2^53, exact in a double
  assert.equal(sSeq, expected);
  assert.equal(sRand, expected);
  const seqMs = t1 - t0, randMs = t2 - t1;
  console.log(`n=${n}: sequential ${seqMs.toFixed(1)} ms, random ${randMs.toFixed(1)} ms, ratio ${(randMs / seqMs).toFixed(1)}x`);
}

main();

On the test machine the four programs printed ratios of 8.0x (Python, ), 6.8x (Java), 8.1x (C++) and 11.8x (TypeScript with typed arrays), all with for the compiled and JIT-compiled languages. Python's ratio is diluted by interpreter overhead on every iteration; its random traversal also chases a pointer from the list slot to the int object, which the sequential version does too but with the objects allocated in order. Expect different absolute numbers and a similar shape on your machine; the capstone makes this systematic.

Real-world uses

  • Database indexes and pages. B-trees pack hundreds of keys per 4–16 KB page so that a lookup on a billion rows costs three or four page fetches; the same reasoning at cache-line scale drives in-memory index designs. Indexing Deep Dive, How Databases Work.
  • Columnar storage and vectorised execution. Parquet, ClickHouse and DuckDB store each column contiguously (struct of arrays) so that scans and aggregates stream at memory bandwidth and vectorise; row stores (array of structs) win for point lookups that need a whole record. Storage Engines.
  • Redis. Small hashes, lists and sorted sets are stored as compact contiguous encodings (listpack, formerly ziplist) and converted to pointer-based structures only past a size threshold, trading operations on tiny collections for far better cache behaviour and memory. Redis Internals.
  • Language runtimes. CPython's compact dict, V8's elements kinds and Smi tagging, HotSpot's compressed oops and the JDK's ArrayDeque recommendation over LinkedList are all layout decisions made for cache reasons. Memory Allocators covers how malloc tries to keep sequential allocations adjacent.
  • Operating systems. The Linux kernel's intrusive list_head embeds list pointers inside the object so that a traversal that already touches the object pays no extra line; the page cache and the scheduler's run queues are tuned around cache-line and NUMA locality. CPU Scheduling, Virtual Memory.
  • Game engines and simulations. Entity-component systems store components in dense arrays per type (struct of arrays) so that "update all positions" is a linear scan.
  • Concurrency. Padding to avoid false sharing is standard in lock-free queues, per-core counters and the JDK's LongAdder. Lock-Free Programming, Concurrency Patterns.
  • Benchmarking methodology. Warm-up, medians and cache-state control exist because of everything above. Benchmarks.

Pitfalls and edge cases

  • Benchmarking the first run. The first traversal pays page faults and cold caches; the JIT in Java and V8 has not compiled yet. Always warm up and report a median — see the capstone harness.
  • Assuming getsizeof is the whole story. sys.getsizeof([1, 2, 3]) returns 80 (56 + 3 × 8) and says nothing about the three 28-byte ints. Use tracemalloc or sum recursively for the true footprint.
  • list(range(n)) versus appending. The former allocates exactly slots; the latter over-allocates by up to about 12.5%. Neither is wrong, but memory measurements differ.
  • Holey JavaScript arrays. new Array(1000) and arr[arr.length + 5] = x create holes; the array becomes HOLEY_ELEMENTS and every read must check for the hole. Prefer Array.from({length: n}, ...), new Array(n).fill(0), or a typed array.
  • Doubles poisoning Smi arrays. One 1.5 written into an integer array transitions it to double elements permanently; one object transitions it to tagged elements. Keep arrays monomorphic.
  • Java LinkedList as a queue. It allocates a node per element and chases pointers; ArrayDeque is a ring buffer and is faster in every measured case. LinkedList.get(i) is .
  • C++ std::list and std::unordered_map by default. Use std::vector unless you need stable addresses or splicing, and consider a flat open-addressing map when lookups are hot.
  • Pointer-size assumptions. 8 bytes on 64-bit, 4 with JVM compressed oops or V8 pointer compression. Do not hard-code either.
  • Iterating a 2-D structure the wrong way. for c in range(cols): for r in range(rows): m[r][c] is the 30x trap in every language. Loop over the inner dimension innermost.
  • Alignment and SIMD. Unaligned loads are legal and usually cheap on x86, but a vector load that straddles a cache line costs two line fetches, and some ARM and older SIMD instructions require alignment.
  • False sharing in "independent" counters. counts[threadId]++ with adjacent longs is the textbook case: eight threads, one cache line.
  • Trusting a growth factor. CPython's was newsize >> 3 + 3 (3.8) and is now + 6 rounded to a multiple of 4 (3.9+); Java's was (oldCapacity * 3) / 2 + 1 before Java 7. Cite the version if you quote a factor.
  • Measuring with the wrong . 4 MB of data fits in a modern L2 or L3; random access over it may look harmless. The cliff appears when the working set exceeds the last-level cache.

Variations

  • Blocked and unrolled lists. Store 16–64 elements per node (an unrolled linked list) to get most of the cache behaviour of an array with cheap splicing; std::deque uses fixed-size blocks plus an index array, which is why it has indexing and push at both ends but worse locality than vector.
  • B-trees and B+-trees. The blocked idea applied to search trees; the dominant disk and in-memory ordered index (Indexing Deep Dive).
  • Open addressing variants. Linear probing (best locality, clustering), quadratic probing, Robin Hood hashing, Swiss tables (Abseil, hashbrown) that store 1-byte metadata per slot in a separate contiguous array and probe 16 slots per SIMD instruction — the direct descendants of the compact-dict idea.
  • Struct of arrays, array of structs, and hybrids (array of structs of arrays, "AoSoA") used by SIMD code to get both locality within a record and vectorisation across records.
  • Cache-oblivious algorithms (Frigo, Leiserson, Prokop, Ramachandran, 1999): recursive layouts such as the van Emde Boas tree layout that achieve optimal cache-line transfers without knowing the line size.
  • Arena and slab allocation. Allocating all nodes of a tree or graph from one contiguous arena restores locality to pointer-based structures and makes freeing them a single operation; see Memory Allocators.
  • Succinct and implicit structures. A binary heap stores a complete tree in an array with children at and — no pointers at all (Heaps); Eytzinger layout stores a sorted array in heap order so that binary search touches adjacent lines.
  • Bit-packing. Bitsets and bitmaps store one element per bit, 512 per cache line (Bit Manipulation, Bloom Filters).

Practice ladder

Problems where the layout is the point. Each description is in our own words.

1. Move Zeroes (LeetCode 283) — easy. Push all zeros of an array to the end in place, preserving the order of the other elements. Teaches the write-pointer compaction idiom: one sequential pass, no extra array.

Hint

Keep an index w of where the next non-zero should go. Scan with r; when nums[r] != 0, swap it into w and advance w. Both pointers only move forward, so the pass is sequential.

2. Rotate Array (LeetCode 189) — medium. Rotate an array right by positions using extra space. Teaches that an in-place reversal is three cache-friendly sequential passes, while the "cyclic replacement" alternative jumps around.

Hint

Reverse the whole array, then reverse the first elements, then reverse the rest. Reduce modulo first.

Solution
def rotate(nums: list[int], k: int) -> None:
   n = len(nums)
   if n == 0:
       return
   k %= n

   def reverse(i: int, j: int) -> None:
       while i < j:
           nums[i], nums[j] = nums[j], nums[i]
           i += 1
           j -= 1

   reverse(0, n - 1)
   reverse(0, k - 1)
   reverse(k, n - 1)


a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
assert a == [5, 6, 7, 1, 2, 3, 4]
b = [1, 2]
rotate(b, 5)
assert b == [2, 1]
c: list[int] = []
rotate(c, 4)
assert c == []
print("rotate ok")

Time — exactly swaps across three passes — space . Each pass walks two pointers inward, so it touches each cache line twice at most.

3. Transpose Matrix (LeetCode 867) — easy. Return the transpose of an matrix. Teaches the row-major/column-major conflict head-on: one of the two matrices is necessarily traversed against its storage order, and large transposes are tiled.

Hint

Allocate the result and write out[c][r] = m[r][c]. Then ask: which side is strided? For a cache-friendly version, transpose in blocks.

Solution
def transpose(m: list[list[int]]) -> list[list[int]]:
   rows, cols = len(m), len(m[0])
   out = [[0] * rows for _ in range(cols)]
   for r in range(rows):            # read m sequentially, write out strided
       for c in range(cols):
           out[c][r] = m[r][c]
   return out


def transpose_blocked(m: list[list[int]], block: int = 2) -> list[list[int]]:
   """Same result; each block of m and the matching block of out fit together in cache."""
   rows, cols = len(m), len(m[0])
   out = [[0] * rows for _ in range(cols)]
   for r0 in range(0, rows, block):
       for c0 in range(0, cols, block):
           for r in range(r0, min(r0 + block, rows)):
               for c in range(c0, min(c0 + block, cols)):
                   out[c][r] = m[r][c]
   return out


m = [[1, 2, 3], [4, 5, 6]]
assert transpose(m) == [[1, 4], [2, 5], [3, 6]]
assert transpose_blocked(m) == transpose(m)
big = [[r * 7 + c for c in range(7)] for r in range(5)]
assert transpose_blocked(big, 3) == transpose(big)
print("transpose ok")

Time , space for the result. In Python the lists of lists add a pointer chase per row, so the blocked version only pays off in compiled code or NumPy; the idea is what matters.

4. Merge Sorted Array (LeetCode 88) — easy. Merge nums2 into nums1, which has enough trailing capacity, in place. Teaches filling from the back so that no element is shifted twice.

Hint

Three indices: the last valid element of each input and the last slot of nums1. Write the larger of the two tails into the last slot and move backwards.

5. Design HashSet (LeetCode 705) — easy. Build a set of integers in with add, remove and contains. Teaches that with a bounded key range a bitset or boolean array is the fastest hash table there is.

Hint

A bytearray(10**6 + 1) is a perfect hash with no collisions; a bitset is 125 KB. Then implement the general version with buckets to show you know the difference.

6. Design HashMap (LeetCode 706) — easy. Implement put, get and remove for integer keys without using the built-in map. Teaches the two layouts; implement open addressing with tombstones and explain why it is cache-friendlier than chaining.

Hint

Slot arrays keys, vals, state (empty, full, deleted). Probe linearly from hash(key) % capacity. Resize at load 0.5 by rebuilding without tombstones.

Solution
EMPTY, FULL, DELETED = 0, 1, 2


class MyHashMap:
   """Open addressing with linear probing; slots live in three parallel arrays."""

   def __init__(self, capacity: int = 8) -> None:
       self.cap = capacity
       self.keys = [0] * capacity
       self.vals = [0] * capacity
       self.state = [EMPTY] * capacity
       self.used = 0            # FULL + DELETED slots, controls resize

   def _find(self, key: int) -> int:
       """Index of key if present, else index of the first EMPTY/DELETED slot on the probe path."""
       i = (key * 2654435761) % self.cap   # Knuth multiplicative hash
       first_free = -1
       while True:
           s = self.state[i]
           if s == FULL and self.keys[i] == key:
               return i
           if s == EMPTY:
               return first_free if first_free != -1 else i
           if s == DELETED and first_free == -1:
               first_free = i
           i = (i + 1) % self.cap

   def _resize(self) -> None:
       old = [(k, v) for k, v, s in zip(self.keys, self.vals, self.state) if s == FULL]
       self.__init__(self.cap * 2)
       for k, v in old:
           self.put(k, v)

   def put(self, key: int, value: int) -> None:
       if (self.used + 1) * 2 > self.cap:
           self._resize()
       i = self._find(key)
       if self.state[i] != FULL:
           self.used += 1
       self.keys[i], self.vals[i], self.state[i] = key, value, FULL

   def get(self, key: int) -> int:
       i = self._find(key)
       return self.vals[i] if self.state[i] == FULL and self.keys[i] == key else -1

   def remove(self, key: int) -> None:
       i = self._find(key)
       if self.state[i] == FULL and self.keys[i] == key:
           self.state[i] = DELETED


m = MyHashMap()
m.put(1, 1)
m.put(2, 2)
assert m.get(1) == 1 and m.get(3) == -1
m.put(2, 1)
assert m.get(2) == 1
m.remove(2)
assert m.get(2) == -1
for k in range(1000):
   m.put(k, k * k)
assert all(m.get(k) == k * k for k in range(1000))
for k in range(0, 1000, 2):
   m.remove(k)
assert m.get(500) == -1 and m.get(501) == 501 * 501
print("hashmap ok")

Expected per operation at load factor at most 0.5; worst case for an adversarial key set. Every probe sequence walks adjacent slots, so it stays within one or two cache lines.

7. Spiral Matrix (LeetCode 54) — medium. Return the elements of an matrix in clockwise spiral order. Teaches boundary bookkeeping and that two of the four sides of each ring are traversed against storage order.

Hint

Maintain top, bottom, left, right. Walk the top row left to right, the right column top to bottom, then — only if rows remain — the bottom row right to left, and — only if columns remain — the left column bottom to top. Shrink the bounds.

Solution
def spiral_order(m: list[list[int]]) -> list[int]:
   if not m or not m[0]:
       return []
   out: list[int] = []
   top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
   while top <= bottom and left <= right:
       for c in range(left, right + 1):              # top row: sequential
           out.append(m[top][c])
       for r in range(top + 1, bottom + 1):          # right column: strided
           out.append(m[r][right])
       if top < bottom:
           for c in range(right - 1, left - 1, -1):  # bottom row, reversed
               out.append(m[bottom][c])
       if left < right:
           for r in range(bottom - 1, top, -1):      # left column, upwards
               out.append(m[r][left])
       top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1
   return out


assert spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
assert spiral_order([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
assert spiral_order([[7]]) == [7]
assert spiral_order([[1], [2], [3]]) == [1, 2, 3]
assert spiral_order([]) == []
print("spiral ok")

Time , each element visited once; space beyond the output. The two if guards prevent double-visiting the middle row or column of an odd-sized ring.

8. Set Matrix Zeroes (LeetCode 73) — medium. If a cell is zero, zero its entire row and column, in place with extra space. Teaches using the matrix's own first row and column as the marker arrays.

Hint

Record whether the first row and first column themselves need zeroing. Then use m[r][0] and m[0][c] as flags for the rest. Zero the interior from the flags, and finally handle the first row and column.

Solution
def set_zeroes(m: list[list[int]]) -> None:
   rows, cols = len(m), len(m[0])
   first_row_zero = any(m[0][c] == 0 for c in range(cols))
   first_col_zero = any(m[r][0] == 0 for r in range(rows))

   for r in range(1, rows):                  # mark: m[r][0] and m[0][c] become flags
       for c in range(1, cols):
           if m[r][c] == 0:
               m[r][0] = 0
               m[0][c] = 0

   for r in range(1, rows):                  # apply to the interior, row-major
       for c in range(1, cols):
           if m[r][0] == 0 or m[0][c] == 0:
               m[r][c] = 0

   if first_row_zero:
       for c in range(cols):
           m[0][c] = 0
   if first_col_zero:
       for r in range(rows):
           m[r][0] = 0


a = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
set_zeroes(a)
assert a == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
b = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
set_zeroes(b)
assert b == [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
c = [[1, 2], [3, 4]]
set_zeroes(c)
assert c == [[1, 2], [3, 4]]
print("set zeroes ok")

Time in two row-major passes, space . The two booleans exist because the cell m[0][0] would otherwise have to serve as the flag for both the first row and the first column.

9. Rotate Image (LeetCode 48) — medium. Rotate an matrix 90 degrees clockwise in place. Teaches that rotation = transpose + reverse rows, two passes that each stay close to storage order, versus the four-way cell swap that jumps between distant rows.

Hint

Transpose in place (swap m[i][j] with m[j][i] for j > i), then reverse each row.

10. LRU Cache (LeetCode 146) — medium. Get and put in with eviction of the least recently used key. Teaches the one place a linked list is the right answer — you already hold the node — and how a hash map and a list combine.

Hint

Hash map from key to node; doubly linked list in recency order with sentinel head and tail. get unlinks the node and relinks it at the front. In Python OrderedDict.move_to_end does exactly this.

Solution
class Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0) -> None:
        self.key, self.val = key, val
        self.prev: "Node | None" = None
        self.next: "Node | None" = None


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.map: dict[int, Node] = {}
        self.head, self.tail = Node(), Node()        # sentinels: head.next is most recent
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, n: Node) -> None:
        n.prev.next, n.next.prev = n.next, n.prev

    def _push_front(self, n: Node) -> None:
        n.next, n.prev = self.head.next, self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, key: int) -> int:
        n = self.map.get(key)
        if n is None:
            return -1
        self._unlink(n)
        self._push_front(n)
        return n.val

    def put(self, key: int, value: int) -> None:
        n = self.map.get(key)
        if n is not None:
            n.val = value
            self._unlink(n)
            self._push_front(n)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        n = Node(key, value)
        self.map[key] = n
        self._push_front(n)


c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)                 # evicts 2
assert c.get(2) == -1
c.put(4, 4)                 # evicts 1
assert c.get(1) == -1 and c.get(3) == 3 and c.get(4) == 4
print("lru ok")

per operation. Memory: one dict entry plus one node (about 100 bytes in CPython even with __slots__) per key, so a cache of ten million small ints costs about a gigabyte — the kind of number this lesson should let you estimate before running out of RAM.

Common mistakes and interview follow-ups

"Your solution is . Why is it slow?" The expected answer names a constant factor with a mechanism: boxing (ArrayList<Integer>, Python ints), pointer chasing (linked structures, lists of lists), random access over a working set larger than cache, allocation inside the loop, or a strided traversal. Then propose the fix: a primitive/typed array, a flat matrix, loop interchange, reserve, or an open-addressing map.

"Why not a linked list? Insertion in the middle is ." Only after finding the position, which is pointer chases and dominates. A vector's shift is a memmove of adjacent bytes and is cheaper in practice for moderate (Stroustrup's experiment). Linked lists win when you already hold the node — LRU caches, intrusive kernel lists — or when elements must never move.

"How much memory does your Python solution use for integers?" About bytes for the list plus for the ints, roughly 360 MB; array('q') or NumPy brings it to 80 MB; a set of them is around 400–500 MB. Showing the arithmetic is the point.

"What if the matrix is ?" It does not fit in RAM (40 GB of int32), so you are now in external memory: tile the computation so that blocks fit in cache and in RAM, and traverse in storage order. Same reasoning as the 30x row/column ratio, one level down the hierarchy.

"Why does Java's HashMap convert buckets to trees?" To bound the worst case at under hash flooding, at the price of a heavier node. Follow-up: why is Python's dict not vulnerable in the same way? Randomised string hashing (SipHash) since 3.3 plus open addressing with perturbation.

"Would a hash set or sorting be faster to deduplicate a billion 32-bit integers?" A hash set of a billion entries is 8–16 GB and every insert is a cache miss; sorting (radix or in-place) streams the data a handful of times at bandwidth, then one pass removes duplicates. Sorting typically wins, and it is the approach a database's planner would pick for a large distinct.

"Design an array that supports push at both ends." A ring buffer (ArrayDeque, collections.deque uses 64-slot blocks) — not a linked list. Discuss growth (copy into a larger ring) and why indexing stays .

"How would you measure this rather than argue about it?" Warm up, repeat, take a median, vary across cache sizes, assert correctness, and pin the thread if you can. Then explain the curve you see — the capstone.

Quick quiz

1. A 6-element int32 array starts at address 0x1038. How many 64-byte cache lines does a full scan touch?

Answer

Two. Elements 0–1 occupy 0x1038–0x103F in the line starting at 0x1000; elements 2–5 occupy 0x1040–0x104F in the line starting at 0x1040. Aligning the array to 0x1040 would make it one.

2. Why is appending to a dynamic array amortised with geometric growth but with "add 100 slots each time"?

Answer

With geometric growth factor the total elements copied over appends is a geometric series bounded by , so each append pays a constant on average. With constant growth , the -th reallocation copies elements and there are of them, giving total copying, per append.

3. Two loops sum a 4096 × 4096 int32 matrix, one row by row, one column by column. Which is faster, by roughly how much, and why?

Answer

Row by row, by an order of magnitude (about 30x in our measurement, machine-dependent). Row-major storage makes the row loop touch 16 useful integers per 64-byte line with the prefetcher ahead of it; the column loop touches one integer per line and jumps 16 KB between accesses, defeating the prefetcher and thrashing the TLB.

4. In CPython, how many bytes do [], [0], and list(range(1000)) occupy, excluding the integers themselves?

Answer

56, 64 (56 + one 8-byte pointer slot — though appending one element to an empty list over-allocates to 4 slots, 88 bytes), and 8056 (56 + 1000 × 8) because list(range(n)) allocates exactly slots. Measured with sys.getsizeof on CPython 3.14.6.

5. Two threads each increment their own counter a billion times; the counters are adjacent longs in one array. Why is this slow and how do you fix it?

Answer

False sharing: both counters live in the same 64-byte line, so each write invalidates the other core's copy and the line ping-pongs through the coherence protocol. Pad each counter to its own cache line (alignas(64), @Contended) or use per-thread striped counters such as LongAdder.

Further reading and sources

  • Ulrich Drepper, What Every Programmer Should Know About Memory (2007) — the definitive long-form treatment of caches, lines, prefetching and NUMA.
  • Bjarne Stroustrup, "Software Development for Infrastructure", IEEE Computer, January 2012, and the GoingNative 2012 keynote "Why you should avoid linked lists" — the vector-versus-list experiment.
  • Alok Aggarwal and Jeffrey Vitter, "The Input/Output Complexity of Sorting and Related Problems", Communications of the ACM, 1988 — the external-memory model.
  • Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran, "Cache-Oblivious Algorithms", FOCS 1999.
  • CPython source: Objects/listobject.c (list_resize, growth pattern), Objects/dictobject.c (compact layout notes at the top of the file), Objects/listsort.txt (Timsort: minrun and galloping).
  • OpenJDK source: java/util/ArrayList.java (grow), java/util/HashMap.java (treeify constants); JEP 450 (Compact Object Headers).
  • GCC libstdc++ bits/stl_vector.h (_M_check_len); Microsoft STL stl/inc/vector (_Calculate_growth).
  • V8 blog: "Elements kinds in V8" (Mathias Bynens, 2017) and "Pointer compression in V8" (2020); src/objects/js-objects.h (NewElementsCapacity).
  • CLRS, Introduction to Algorithms, 4th ed., Chapter 17 (amortised analysis) and Chapter 18 (B-trees); Sedgewick & Wayne, Algorithms, 4th ed., §1.4 (resizing arrays).
  • Agner Fog, Optimizing Software in C++, chapter on memory and cache; Intel 64 and IA-32 Architectures Optimization Reference Manual (prefetching, false sharing).

Module 0: Module overview · How to Use This Course · Complexity Analysis · Recursion & Induction · How Data Structures Live in Memory · Your Language's Data Structures · How to Solve Any Problem · Testing & Debugging Algorithms · Capstone · Course home

Previous: Recursion & Mathematical Induction · Next: Your Language's Data Structures

Related: Arrays & Strings · Linked Lists · Hash Tables · Trees · Advanced Data Structures · How Computers Work · Benchmarks