TAOCP 2.2.3 Exercise 8

Let the linked linear list be represented by the pointer `FIRST`, with each node containing the fields `INFO` and `LINK` as in (3).

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 8. [24] Write a MIX program for the problem of exercise 7, attempting to design your program to operate as fast as possible.

Verified: no
Solve time: 30s

Solution

Let the linked linear list be represented by the pointer FIRST, with each node containing the fields INFO and LINK as in (3). The inversion problem of exercise 7 requires changing only the link structure; the INFO fields are untouched. Since the exercise asks for a MIX program and requests maximal speed, the program should avoid unnecessary memory references and auxiliary storage.

The inversion can be performed in one traversal of the list by maintaining three pointers:

  • P, the current node being processed;
  • Q, the already inverted prefix;
  • R, the successor of P before its link is changed.

At each stage, the link of P is reversed, then the pointers advance. The process terminates when P = \Lambda, at which point Q points to the new first node. Thus the algorithm is

$$ Q \leftarrow \Lambda,\qquad P \leftarrow \text{FIRST}; $$

$$ \text{while } P \ne \Lambda\text{ do} $$

$$ R \leftarrow \text{LINK}(P),\qquad \text{LINK}(P) \leftarrow Q,\qquad Q \leftarrow P,\qquad P \leftarrow R; $$

$$ \text{FIRST} \leftarrow Q. $$

The MIX program should keep the principal pointers in index registers, since loading and storing index registers is faster than repeated memory access. Let

$$ P \equiv rI1,\qquad Q \equiv rI2,\qquad R \equiv rI3. $$

Then the inversion program is:

LINK EQU 4:5      Definition of the LINK field

ENT2 0            Q ← Λ.
LD1  FIRST        P ← FIRST.

LOOP J1Z DONE     If P = Λ, terminate.
LD3  0,1(LINK)    R ← LINK(P).
ST2  0,1(LINK)    LINK(P) ← Q.
ENT2 1            Q ← P.
ENT1 3            P ← R.
JMP   LOOP

DONE ST2 FIRST    FIRST ← Q.

The correctness follows by induction on the number of iterations. Before the first iteration, Q = \Lambda, hence the already inverted prefix is empty and P = FIRST points to the unprocessed remainder. Suppose that before an iteration, Q points to the reversal of the nodes already processed, while P points to the first unprocessed node. The instruction

$$ R \leftarrow \text{LINK}(P) $$

preserves access to the remaining list. Then

$$ \text{LINK}(P) \leftarrow Q $$

reverses the link of the current node so that P becomes the first node of the inverted prefix. The assignments

$$ Q \leftarrow P,\qquad P \leftarrow R $$

advance the boundary between processed and unprocessed nodes. Therefore the invariant is preserved. When P = \Lambda, every node has been processed, and Q points to the completely inverted list. The final instruction

$$ \text{FIRST} \leftarrow Q $$

makes FIRST point to the reversed list. This completes the proof.

∎

Notes

The program uses exactly one pass through the list and changes each link field exactly once. No faster algorithm is possible in the sense of number of link examinations, since every node link must be inspected at least once to determine the successor needed to continue traversal.