The containers almost every program runs on, and what each one costs. Six topics: the contiguous array and the dynamic array built on it, linked lists, stacks, queues and ring buffers, the hash table, the attacks on its hash function, and a guide from the operation to the container.
6 topics
Chapter 4 ended on a lesson about memory: a contiguous array beats a pointer-based structure more often than Big-O predicts. This chapter starts from that array and builds upward. Indexing is one multiplication and one read, a scan streams whole cache lines, and the one thing an array does badly, inserting in the middle, turns out to matter less than textbooks suggest once the search for the position is counted honestly.
From there the chapter reaches the structure most programs quietly depend on. Every Python dictionary, set, module namespace and in-memory cache is a hash table, and Lantern's index from 1.5 million terms to their postings lists is one too. Its constant-time lookup is paid for with empty memory, an occasional full rebuild and a hash function that must stay unpredictable to anyone sending hostile keys.
Each topic puts numbers on the trade, measured on CPython 3.15 where Python can show it: a list that grows by an eighth, a queue drained from the wrong end, a dictionary that keeps its size after every key is deleted. The last topic turns the chapter into a habit. Name the hot operation first, and let it choose the container.
Every structure in this chapter, and the array underneath
Choosing a container
the hot operation picks the structure
Hash tables
an array of slots, a hash to pick one, a secret to keep it fair
Stacks, queues, ring buffers
an array or a chain of blocks, with the interface taken away
Linked lists
nodes and pointers: cheap splicing, expensive reaching