TAOCP 2.2.4 Exercise 17

Section 2.2.4: Circular Lists

Exercise 17. [22] What advantage is there in representing polynomials with a circular list as in this section, instead of with a straight linear linked list terminated by $\Lambda$ as in the previous section?

Verified: no
Solve time: 35s

Solution

The principal advantage is that the circular representation eliminates special cases at the ends of the list.

In the polynomial representation of this section, every polynomial contains a special node with ABC = -1, and this node links back to the leading term. Consequently there is always a successor node, and the algorithm can proceed by repeatedly following links without testing for \Lambda.

This feature is used directly in Algorithm A. The pointers P and Q move through their respective polynomials simply by assignments such as

$$ P \leftarrow LINK(P), \qquad Q \leftarrow LINK(Q), $$

and termination is detected when

$$ ABC(P)=ABC(Q)=-1. $$

No test for the end of a list is required. The special node acts as a sentinel, and comparison of exponent fields alone determines the control flow.

With a straight linear linked list terminated by $\Lambda$, every traversal would require additional checks to determine whether a pointer had reached the end of its list. In polynomial addition and multiplication, where the lists are scanned repeatedly, these tests would complicate the algorithms and introduce extra operations.

A second advantage is that the zero polynomial is represented naturally by the special node alone. Thus every polynomial has the same structural form, and there is no empty-list case requiring separate treatment.

Hence the circular representation provides a sentinel that removes end-of-list tests, simplifies the algorithms, and avoids special handling of the zero polynomial.

$$ \boxed{\text{The circular list representation uses a sentinel node and cyclic links, eliminating }\Lambda\text{-termination tests and special empty-list cases.}} $$