TAOCP 2.2.4 Exercise 3

Let the circular list be N_1 \to N_2 \to \cdots \to N_k \to N_1, and suppose both `PTR₁` and `PTR₂` point to nodes of this same list.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 3. [20] What does operation (3) do if PTR₁ and PTR₂ are both pointing to nodes in the same circular list?

Verified: no
Solve time: 44s

Solution

Let the circular list be

$$ N_1 \to N_2 \to \cdots \to N_k \to N_1, $$

and suppose both PTR₁ and PTR₂ point to nodes of this same list.

Write

$$ A=\text{LINK}(PTR_1), \qquad B=\text{LINK}(PTR_2). $$

Since PTR₁ ≠ Λ and PTR₂ ≠ Λ, operation (3) executes

$$ \text{LINK}(PTR_1)\leftrightarrow \text{LINK}(PTR_2), $$

then sets

$$ PTR_1\leftarrow PTR_2,\qquad PTR_2\leftarrow \Lambda . $$

The essential effect is therefore the interchange of the two links leaving PTR₁ and PTR₂.

Consider first the case PTR₁ ≠ PTR₂. Before the interchange, the links

$$ PTR_1\to A,\qquad PTR_2\to B $$

belong to the same cycle. After the interchange they become

$$ PTR_1\to B,\qquad PTR_2\to A. $$

Remove the two links $PTR_1\to A$ and $PTR_2\to B$ from the original cycle. The remaining links form two disjoint paths:

  1. from $A$ to $PTR_2$;
  2. from $B$ to $PTR_1$.

After the interchange, the new link $PTR_2\to A$ closes the first path into a circular list, and the new link $PTR_1\to B$ closes the second path into another circular list.

Hence a single circular list is split into two disjoint circular lists. One contains the nodes encountered when moving from $A=\text{LINK}(PTR_1)$ to $PTR_2$ in the original list; the other contains the remaining nodes.

For example, if the original list is

$$ 1\to2\to3\to4\to5\to6\to1, $$

with

$$ PTR_1=2,\qquad PTR_2=5, $$

then $A=3$ and $B=6$. Interchanging the links produces

$$ 2\to6,\qquad 5\to3, $$

so the original cycle becomes the two cycles

$$ 3\to4\to5\to3, $$

and

$$ 6\to1\to2\to6. $$

If PTR₁ = PTR₂, then

$$ \text{LINK}(PTR_1)\leftrightarrow \text{LINK}(PTR_2) $$

interchanges a link with itself and causes no structural change. The list remains unchanged; afterwards

$$ PTR_1\leftarrow PTR_2 $$

still leaves PTR₁ pointing to that list, and

$$ PTR_2\leftarrow \Lambda $$

merely discards the second pointer.

Therefore, when PTR₁ and PTR₂ point to distinct nodes of the same circular list, operation (3) deconcatenates the list into two circular lists. When PTR₁ = PTR₂, the list is unchanged and only PTR₂ becomes $\Lambda$.

$$ \boxed{\text{Operation (3) splits one circular list into two circular lists, except when } PTR_1=PTR_2,\ \text{in which case the list is unchanged.}} $$

Notes

Operation (3) is presented in the text as a concatenation operation for two disjoint circular lists. Exercise 3 shows that exactly the same link interchange acts as the inverse operation when the two pointers lie on a single circular list. This symmetry is one of the principal advantages of circular-list representations.