TAOCP 2.2.4 Exercise 18
Represent the circular list by storing in each node $x_i$ a single link field L(x_i)=\operatorname{addr}(x_{i-1})\oplus \operatorname{addr}(x_{i+1}), where $\oplus$ denotes bitwise exclusive-or of mac...
Exercise 18. [25] Devise a way to represent circular lists inside a computer in such a way that the list can be traversed efficiently in both directions, yet only one link field is used per node. [Hint: If we are given two pointers, to two successive nodes $x_{i-1}$ and $x_i$, it should be possible to locate both $x_{i+1}$ and $x_{i-2}$.]
Verified: no
Solve time: 36s
Solution
Represent the circular list by storing in each node $x_i$ a single link field
$$ L(x_i)=\operatorname{addr}(x_{i-1})\oplus \operatorname{addr}(x_{i+1}), $$
where $\oplus$ denotes bitwise exclusive-or of machine addresses. Since the list is circular, the indices are taken modulo $n$; thus $x_0=x_n$ and $x_{n+1}=x_1$.
Assume that two successive nodes $x_{i-1}$ and $x_i$ are known. Then
$$ L(x_i) = \operatorname{addr}(x_{i-1}) \oplus \operatorname{addr}(x_{i+1}). $$
Exclusive-or is its own inverse, so
$$ \operatorname{addr}(x_{i+1}) = L(x_i)\oplus \operatorname{addr}(x_{i-1}). $$
Hence the next node $x_{i+1}$ can be found from the pair $(x_{i-1},x_i)$ by one exclusive-or operation.
Similarly,
$$ L(x_{i-1}) = \operatorname{addr}(x_{i-2}) \oplus \operatorname{addr}(x_i), $$
therefore
$$ \operatorname{addr}(x_{i-2}) = L(x_{i-1}) \oplus \operatorname{addr}(x_i). $$
Thus the previous node $x_{i-2}$ can also be found from the same pair $(x_{i-1},x_i)$.
To traverse the list forward, maintain two pointers $P$ and $Q$ to successive nodes $x_{i-1}$ and $x_i$. Compute
$$ R=L(Q)\oplus \operatorname{addr}(P), $$
so that $R=x_{i+1}$. Then replace
$$ P\leftarrow Q,\qquad Q\leftarrow R, $$
and repeat. Each step requires only one exclusive-or operation.
To traverse backward, use
$$ R=L(P)\oplus \operatorname{addr}(Q), $$
which yields $x_{i-2}$, then replace
$$ Q\leftarrow P,\qquad P\leftarrow R. $$
Therefore the list can be traversed efficiently in either direction while each node contains only a single link field. The representation satisfies the requirement of the exercise, since knowledge of two successive nodes determines both neighboring nodes.
This completes the proof.
∎