TAOCP 2.2.4 Exercise 8
The pointer `Q1` trails `Q` by one node to simplify insertions and deletions in `polynomial(Q)`.
Exercise 8. [10] Why is it useful to have Q1 trailing one step behind Q in Algorithm A?
Verified: yes
Solve time: 45s
The pointer Q1 trails Q by one node to simplify insertions and deletions in polynomial(Q). In step A4, when a term of Q becomes zero and must be removed, the assignment LINK(Q1) \leftarrow Q \leftarrow LINK(Q) relies on Q1 pointing to the node immediately preceding Q. Without Q1, the predecessor of Q would have to be located by scanning from the head of the list each time a deletion occurs, which would increase the time complexity from $O(1)$ per deletion to $O(n)$ per deletion. Similarly, in step A5, inserting a new term before Q is accomplished in constant time because Q1 already points to the correct predecessor; the assignment LINK(Q1) \leftarrow Q2 correctly links the new node into the list.
By maintaining Q1 one step behind Q, the algorithm avoids repeated scanning for predecessors, ensures that both insertions and deletions are performed efficiently, and preserves the circular order of the list throughout the traversal. This trailing pointer is essential for maintaining correct links while performing updates on polynomial(Q) in a single pass. This completes the proof.
∎