Track 2
Data structures
Ways to organize data in memory, from arrays and linked lists to hash maps, trees and heaps, and what each makes fast or slow.
6 pages, each with a live figure. Read them in order: later pages build on earlier ones.
- 2.1ArraysStep throughValues stored side by side in memory, so any position can be reached directly by its index.
- 2.2Stacks and queuesStep throughTwo ways to hold items in order: a stack gives back the newest item first, a queue the oldest.
- 2.3Linked listsSandboxA chain of nodes where each one holds a value and a pointer to the next, so items can be added without shifting anything.
- 2.4Hash mapsStep throughStore values under keys, using a hash of each key to jump straight to where it lives.
- 2.5Binary search treesSandboxA tree where every node's left side holds smaller values and its right side holds larger ones, so a search can skip half the tree at each step.
- 2.6HeapsSandboxA tree where every parent is smaller than its children, kept in an array, so the minimum is always at the front.