TAOCP 2.4 Exercise 5
Algorithm B is modified by replacing the indexed access to $P_k$ with sequential traversal of the linked structure beginning at $T$.
Section 2.4: Multilinked Structures
Exercise 5. [**] [20] In practice, Algorithm B may be given a linked list of Symbol Table
references as input, instead of what we called "P0, P1, ..., Pn." Let T be
a pointer variable such that
$$ \operatorname{INFO}(T) = P_0,\quad \operatorname{INFO}(\operatorname{RLINK}(T)) = P_1,\quad \ldots,\quad \operatorname{INFO}(\operatorname{RLINK}^{[n]}(T)) = P_n,\quad \operatorname{RLINK}^{[n+1]}(T) = \Lambda. $$
Show how to modify Algorithm B so that it uses such a linked list as input.
Verified: no
Solve time: 1m37s
Algorithm B is modified by replacing the indexed access to $P_k$ with sequential traversal of the linked structure beginning at $T$. The first element is obtained by setting $S \leftarrow T$ and defining $P_0 \leftarrow \operatorname{INFO}(S)$.
For $k \ge 0$, if $\operatorname{RLINK}(S) \ne \Lambda$, then $S \leftarrow \operatorname{RLINK}(S)$ and $P_{k+1} \leftarrow \operatorname{INFO}(S)$; otherwise the process terminates with $P_k$ as the final input element. The loop structure of Algorithm B is then executed unchanged with $P_0, P_1, \ldots, P_n$ produced in this manner.