TAOCP Vol 1: Fundamental Algorithms · Week 45
TAOCP 2.4 Multilinked Structures: reading guide
Nodes that belong to several lists at once, illustrated by how a compiler for a COBOL-like language stores nested data declarations and implements a "move corresponding fields" operation.
Time About 6 hours this week
Why it matters
Symbol tables, ORMs and many in-memory databases use multilinked nodes. It is also a peek at real compiler engineering from the 1960s.
Before you start
- 2.3 Trees
How to approach it
Read the problem statement carefully and sketch the data layout yourself before reading Knuth's design. The details of COBOL are not important; the structure design is.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Getting lost in COBOL semantics. Focus on the data structure.