Week 36: TAOCP 2.2.3 Linked Allocation

Linked lists, the available-space (free) list, and how to implement stacks and queues with links. The highlight is topological sorting: putting items in an order consistent with a set of "must come before" relations.

Time About 9 hours this week

Why it matters

Topological sort runs your build system, package manager and task scheduler. Free lists are the simplest memory allocator and still used in game engines and kernels.

Before you start

2.2.2 Sequential Allocation
C pointers (clox)

How to approach it

This is a long and very rewarding section. Implement the free-list allocator in C. Then implement Knuth's topological sort algorithm from the text, run it on a small dependency graph from a real project, and check the output order.

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

Losing nodes when you forget to return them to the free list.
Topological sort with a cycle in the input: decide what your code should do.