TAOCP 2.2.3 Exercise 6
In operation (14), a new node is inserted at the rear of the queue.
Section 2.2.3: Linked Allocation
Exercise 6. [21] In operation (14) we set LINK(P) ← Λ, while the very next insertion at the rear of the queue will change the value of this same link field. Show how the setting of LINK(P) in (14) could be avoided if we make a change to the testing of "F = Λ" in (17).
Verified: no
Solve time: 39s
Solution
In operation (14), a new node is inserted at the rear of the queue. The step
$$ \text{LINK}(P)\leftarrow\Lambda $$
is used only to guarantee that the last node of the queue has null link. When the next insertion occurs, this field is immediately overwritten by
$$ \text{LINK}(R)\leftarrow P, $$
where $R$ is the former rear node. Hence the assignment to $\text{LINK}(P)$ is unnecessary if the deletion algorithm is modified so that it never relies on the rear node having link $\Lambda$.
The difficulty occurs when the queue contains exactly one node. In operation (17), after
$$ P\leftarrow F,\qquad F\leftarrow \text{LINK}(P), $$
the test
$$ F=\Lambda $$
is used to determine whether the queue has become empty, in which case $R$ must also be set to $\Lambda$. This test is valid only when the unique node of the queue has link $\Lambda$.
To avoid setting
$$ \text{LINK}(P)\leftarrow\Lambda $$
during insertion, the deletion algorithm should test whether the node being deleted is the rear node. Since a queue with one element satisfies $F=R$, replace the test "$F=\Lambda$" in (17) by the test
$$ P=R. $$
Then operation (17) becomes
$$ \text{If }F=\Lambda,\ \text{then UNDERFLOW;} $$
$$ P\leftarrow F,\qquad F\leftarrow \text{LINK}(P),\qquad Y\leftarrow \text{INFO}(P), $$
$$ \text{if }P=R,\ \text{then }R\leftarrow\Lambda, $$
$$ \text{AVAIL}\Leftarrow P. $$
When the queue contains more than one node, $P\neq R$, so $R$ remains unchanged. When the queue contains exactly one node, $P=R$; after deletion both $F$ and $R$ are set to $\Lambda$, regardless of the value stored in $\text{LINK}(P)$.
Therefore the assignment
$$ \text{LINK}(P)\leftarrow\Lambda $$
in operation (14) may be omitted, provided that operation (17) tests $P=R$ instead of $F=\Lambda$. ∎