TAOCP 2.3.5 Exercise 1

Section 2.3.5: Lists and Garbage Collection

Exercise 1. [**] [M21] In Section 2.3.4 we saw that trees are special cases of the "classical" mathematical concept of a directed graph. Can Lists be described in graph-theoretic terminology?

Verified: yes
Solve time: 1m01s

A List can be described as a directed graph in which each node corresponds to a List element or atom, and each pointer (DLINK, RLINK, or LLINK) corresponds to a directed edge from one node to another. The RLINK field gives the usual successor relation along the linear sequence of the List, while the DLINK field gives edges to the heads of sub-Lists. Header nodes, atoms, and sub-List elements can all be represented as vertices with outgoing edges determined by the fields they contain.

Unlike trees, Lists may contain cycles or multiple references to the same sub-List, so the corresponding graph is generally a directed multigraph, possibly with loops. The absence of cycles and multiple references reduces a List to a tree or forest, as in Section 2.3.3, but in general the graph-theoretic description allows arbitrary sharing and recursive structure. This completes the proof.

∎