TAOCP 2.2.4 Exercise 5

Let a circular list be represented as in (1), with `PTR` pointing to the last node, so that `LINK(PTR)` points to the first node.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 5. [21] Design an algorithm that takes a circular list such as (1) and reverses the direction of all the arrows.

Verified: no
Solve time: 39s

Solution

Let a circular list be represented as in (1), with PTR pointing to the last node, so that LINK(PTR) points to the first node. Let P be a pointer used to traverse the list. The goal is to reverse all LINK fields in the list, so that traversal in the original direction becomes traversal in the opposite direction, while maintaining the circular property. We proceed as follows.

Let FIRST ← LINK(PTR) denote the original first node. Initialize a pointer variable P ← FIRST. Introduce a pointer PREV to keep track of the node whose link we have just processed. Initially, set PREV ← PTR. This choice ensures that after the reversal, the former first node (FIRST) points back to PTR, preserving the circular property.

The algorithm iteratively reverses the LINK field of each node as it traverses the list. Let NEXT be a temporary variable to store the original LINK(P) before overwriting it. Then at each step we execute:

  1. NEXT ← LINK(P)
  2. LINK(P) ← PREV
  3. PREV ← P
  4. P ← NEXT

The invariant maintained is that at the start of each iteration, all nodes preceding P in the original order have their LINK fields reversed. The traversal stops when P = FIRST again, completing one full cycle around the list. At that point, all LINK fields have been reversed. Finally, update PTR ← FIRST to reflect that the last node in the reversed list is the original first node.

Formally, the algorithm is:

R1. [Initialize.] Set FIRST ← LINK(PTR), P ← FIRST, PREV ← PTR.

R2. [Reverse link.] Set NEXT ← LINK(P), LINK(P) ← PREV, PREV ← P, P ← NEXT.

R3. [Continue?] If P ≠ FIRST, return to R2. Otherwise, set PTR ← FIRST and terminate.

Correctness. Initially, LINK(PTR) points to FIRST. At each iteration, the LINK field of P is replaced by the pointer to the previous node in the original order, so after visiting all nodes, every LINK points to the preceding node, achieving reversal. The circular property is preserved because the original last node PTR becomes the next node of the original first node FIRST during the first iteration, and PTR is updated at the end to the former first node.

Complexity. Each node is visited exactly once, and each iteration performs exactly three assignments (NEXT ← LINK(P), LINK(P) ← PREV, PREV ← P, ignoring P ← NEXT which moves the traversal pointer), so the total number of assignments is $4n$, where $n$ is the number of nodes in the list. No auxiliary storage beyond three pointers (P, PREV, NEXT) is required.

This completes the proof.

∎