TAOCP 2.2.4 Exercise 2

Let $L_1$ consist of nodes a_1, a_2, \dots, a_m, with pointer $\mathrm{PTR}_1 = a_m$ and

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 2. [20] Draw "before and after" diagrams illustrating the effect of the concatenation operation (3), assuming that PTR₁ and PTR₂ are $\ne \Lambda$.

Verified: yes
Solve time: 1m34s

Solution

Let $L_1$ consist of nodes

$$ a_1, a_2, \dots, a_m, $$

with pointer $\mathrm{PTR}_1 = a_m$ and

$$ \mathrm{LINK}(a_m) = a_1, $$

so that traversal starting at $a_1$ proceeds

$$ a_1 \to a_2 \to \cdots \to a_m \to a_1 \to \cdots $$

in a circular fashion.

Let $L_2$ consist of nodes

$$ b_1, b_2, \dots, b_n, $$

with pointer $\mathrm{PTR}_2 = b_n$ and

$$ \mathrm{LINK}(b_n) = b_1, $$

so that traversal starting at $b_1$ proceeds

$$ b_1 \to b_2 \to \cdots \to b_n \to b_1 \to \cdots $$

in a circular fashion.

Assume $\mathrm{PTR}_1 \ne \Lambda$ and $\mathrm{PTR}_2 \ne \Lambda$. Operation (3) applies, which interchanges

$$ \mathrm{LINK}(\mathrm{PTR}_1) \leftrightarrow \mathrm{LINK}(\mathrm{PTR}_2) $$

and updates the pointers:

$$ \mathrm{PTR}_1 \leftarrow \mathrm{PTR}_2, \qquad \mathrm{PTR}_2 \leftarrow \Lambda. $$

Before concatenation

The two circular lists are disjoint:

$$ L_1: a_1 \to a_2 \to \cdots \to a_m \to a_1, \quad \mathrm{PTR}_1 = a_m $$

$$ L_2: b_1 \to b_2 \to \cdots \to b_n \to b_1, \quad \mathrm{PTR}_2 = b_n $$

Initially,

$$ \mathrm{LINK}(a_m) = a_1, \qquad \mathrm{LINK}(b_n) = b_1. $$

After swapping these links:

$$ \mathrm{LINK}(a_m) = b_1, \qquad \mathrm{LINK}(b_n) = a_1. $$

All other links remain unchanged.

After concatenation

Pointers are updated:

$$ \mathrm{PTR}_1 = b_n, \qquad \mathrm{PTR}_2 = \Lambda. $$

The resulting single circular list contains all nodes of $L_1$ and $L_2$. Traversal starting from $\mathrm{PTR}_1 = b_n$ follows the updated links:

$$ b_n \to a_1 \to a_2 \to \cdots \to a_m \to b_1 \to b_2 \to \cdots \to b_{n-1} \to b_n. $$

Thus the concatenated list visits all nodes of $L_1$ first, followed by all nodes of $L_2$, and returns to the starting node $b_n$.

Summary of traversal order

  • Before concatenation:

  • $L_1$ circular: $a_1 \to a_2 \to \cdots \to a_m \to a_1$

  • $L_2$ circular: $b_1 \to b_2 \to \cdots \to b_n \to b_1$

  • After concatenation:

  • Single circular list starting at $\mathrm{PTR}_1 = b_n$:

$$ b_n \to a_1 \to \cdots \to a_m \to b_1 \to \cdots \to b_{n-1} \to b_n $$

This correctly reflects the effect of the link swap. ∎

-, If desired, a diagrammatic representation can be included:

Before:

L1: a1 → a2 → ... → am
      ↑              ↓
      ← ← ← ← ← ← ← ←

L2: b1 → b2 → ... → bn
      ↑              ↓
      ← ← ← ← ← ← ← ←

After:

Concatenated list starting at PTR1 = bn:
bn → a1 → a2 → ... → am → b1 → b2 → ... → bn
↑                                      ↓
← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ←

This accurately shows traversal order.