TAOCP 2.3.5 Exercise 2
Yes, List structures can be threaded analogously to trees.
Section 2.3.5: Lists and Garbage Collection
Exercise 2. [**] [20] In Section 2.3.1 we saw that tree traversal can be facilitated using a threaded representation inside the computer. Can List structures be threaded in an analogous way?
Verified: yes
Solve time: 1m11s
Yes, List structures can be threaded analogously to trees. A threaded List is one in which null RLINK or DLINK pointers are replaced by references to the logically next node in some traversal order. For example, in a straight-linked List, the last element of a sub-List can store a pointer to the first element following that sub-List in the containing List, so that traversal can proceed without recursion or an explicit stack. Similarly, circular or doubly linked Lists can be augmented so that header nodes point directly to their successors or predecessors in a chosen traversal, enabling efficient linear or nested iteration. Threading preserves all nodes and sub-Lists while providing a deterministic path through the structure, just as in threaded trees.
This completes the proof.
∎