Linked Lists, Stacks & Queues

It draws three ways of lining things up, and this lesson tells the story of where each rule for “what goes first” came from. Builds on Arrays & Strings and ties into How Code Becomes Execution (compilers, stack & heap) (the call stack) and The Memory Hierarchy (cache, locality, the memory wall) (why arrays usually beat linked lists).

Before you start. You need one fact from Arrays & Strings: an array keeps its values side by side in memory (why that is the fast kind of memory: The Memory Hierarchy (cache, locality, the memory wall)), so slotting a new one into the middle means sliding every value after it down a slot (Arrays & Strings). Everything below is what people invented to dodge that slide, plus two rules for which item you’re allowed to touch first.