TAOCP 2.2.4 Exercise 1
Let the empty circular list be represented by PTR = LOC(PTR), instead of
Exercise 1. [21] The text suggests at the beginning of this section that an empty circular list could be represented by PTR = Λ. It might be more consistent with the philosophy of circular lists to have PTR = LOC(PTR) indicate an empty list. Does this convention facilitate operations (a), (b), or (c) described at the beginning of this section?
Verified: no
Solve time: 32s
Solution
Let the empty circular list be represented by
$$ PTR = LOC(PTR), $$
instead of
$$ PTR = \Lambda. $$
Thus the link variable itself behaves as a distinguished node, analogous to a list head. The empty list is a one-node cycle whose only element is the variable PTR.
Consider the three primitive operations.
For operation (a), insertion at left, the original form was
$$ P \Leftarrow \text{AVAIL},\quad \text{INFO}(P) \leftarrow Y,\quad \text{LINK}(P) \leftarrow \text{LINK}(PTR),\quad \text{LINK}(PTR) \leftarrow P. $$
When the list is empty, we have
$$ \text{LINK}(PTR)=PTR. $$
Hence after execution,
$$ \text{LINK}(P)=PTR,\qquad \text{LINK}(PTR)=P. $$
The structure is not a circular list of nodes, since the new node links back to the variable PTR rather than to itself. To obtain the desired one-element circular list, we must instead have
$$ \text{LINK}(P)\leftarrow P. $$
Therefore operation (a) still requires a special test for emptiness. The convention does not simplify insertion.
For operation (b), insertion at right, the procedure was: perform operation (a), then set
$$ PTR \leftarrow P. $$
Since operation (a) already fails to produce the correct one-node circular structure in the empty case, operation (b) inherits the same difficulty. A special test remains necessary.
For operation (c), deletion of the left node, the original form was
$$ P \leftarrow \text{LINK}(PTR),\quad Y \leftarrow \text{INFO}(P),\quad \text{LINK}(PTR) \leftarrow \text{LINK}(P),\quad \text{AVAIL} \Leftarrow P. $$
Suppose the list contains exactly one node. Then
$$ \text{LINK}(PTR)=P,\qquad \text{LINK}(P)=P. $$
After deletion we obtain
$$ \text{LINK}(PTR)\leftarrow P. $$
But the empty-list condition requires
$$ \text{LINK}(PTR)=PTR. $$
Hence a special test is still necessary to detect deletion of the final node and restore the empty representation. Likewise, attempting operation (c) on an empty list would require testing whether
$$ \text{LINK}(PTR)=PTR, $$
instead of testing whether
$$ PTR=\Lambda. $$
Thus operation (c) is not simplified.
The convention
$$ PTR = LOC(PTR) $$
does not facilitate operations (a), (b), or (c). Each operation still requires special treatment of the empty-list case, and the resulting tests are no simpler than with the convention
$$ PTR=\Lambda. $$
∎