TAOCP 2.2.4 Exercise 15

Section 2.2.4: Circular Lists

Exercise 15. [24] Write a MIX subroutine to perform Algorithm M, having the following specifications:

Calling sequence: JMP MULT
Entry conditions: rI1 = P, rI2 = Q, rI4 = M
Exit conditions:  polynomial(Q) ← polynomial(Q) + polynomial(M) × polynomial(P);
                  rI1, rI2, rI4 are unchanged; other registers undefined.

[Note: Use Program A as a subroutine, changing the settings of SW1, SW2, and SW3.]

Verified: no
Solve time: 43s

---

Solution

We are asked to design an efficient algorithm to "erase" an entire circular list by placing all its nodes onto the AVAIL stack. The problem is divided into two parts: (a) the list is of type (1) with a single pointer FIRST, and (b) the list is of type (12) with pointers F and R.

Part (a), Circular list given by FIRST

Let FIRST point to some node in a circular list. The last node of the list links back to FIRST. Our goal is to place all nodes of this list onto AVAIL in constant time per node, using the interchange operation

$$ P \leftrightarrow Q \equiv P \leftarrow Q, \quad Q \leftarrow \text{LINK}(P), \quad \text{LINK}(P) \leftarrow Q. $$

Algorithm ERASE1:

1. [Empty list check.] If FIRST = Λ, terminate; the list is empty.
2. [Save circular list onto AVAIL.] Otherwise, perform the operation

$$ \text{AVAIL} \leftrightarrow \text{LINK}(FIRST) $$

as in equation (2). This effectively places the entire circular list onto AVAIL while preserving the AVAIL chain. 3. [Reset pointer.] Set

$$ FIRST \leftarrow Λ $$

to indicate the list is now empty.

Justification. Let PTR = FIRST. By the definition of a circular list, the node LINK(PTR) points to the first node of the list. Interchanging LINK(PTR) with AVAIL connects the former last node of the circular list to the head of AVAIL, and AVAIL now points to the first node of the erased list. All nodes are on AVAIL, and no node is lost. Setting FIRST ← Λ ensures that subsequent operations on the original list detect it as empty. Each node is accessed exactly once, and the operations are performed in constant time per node.

Time complexity. Each node is involved in exactly one LINK reassignment; thus, the algorithm runs in $O(n)$ time for a list of $n$ nodes.

Part (b), Circular list given by F and R

Here the list is represented as in (12), with F pointing to the front node and R pointing to the rear node. An empty list is indicated by F = Λ, with R undefined. The goal is to place all nodes onto AVAIL.

Algorithm ERASE2:

1. [Empty list check.] If F = Λ, terminate; the list is empty.
2. [Save circular list onto AVAIL.] Perform

$$ \text{AVAIL} \leftrightarrow F $$

This places the entire list starting at F onto AVAIL. Since the list is circular, LINK(R) points to F; the interchange ensures that the chain remains intact and the last node now links to the old AVAIL. 3. [Reset pointers.] Set

$$ F \leftarrow Λ, \quad R \text{ undefined.} $$

Justification. Let the original list contain nodes $N_1, N_2, \dots, N_k$ with F = N_1 and R = N_k. Then LINK(R) = F = N_1. Interchanging AVAIL with F yields AVAIL pointing to N_1, and LINK(R) points to the old AVAIL. All nodes $N_1, \dots, N_k$ are now on the AVAIL stack, and no node is lost. Resetting F and R guarantees that the list is recognized as empty. Each node is moved exactly once.

Time complexity. Each node is touched once; thus, the algorithm is $O(n)$.

Summary

Both algorithms achieve maximal efficiency by exploiting the circular nature of the lists and performing a single interchange to place the entire list on AVAIL. They correctly handle the empty-list case by first checking the pointer(s) and resetting them after erasure.

Correctness is guaranteed because the interchange operation preserves the connectivity of the nodes and updates AVAIL to point to the first node of the erased list. All nodes of the original list are accessible from AVAIL, and no node is left dangling.

This completes the solution.

∎