TAOCP 2.2.6 Exercise 13

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 13. ▶ [**] [22] Why were circular lists used in Fig. 14 instead of straight linear lists? Could Algorithm S be rewritten so that it does not make use of the circular linkage?

Verified: no
Solve time: 37s

Circular lists are used because they eliminate end-of-list cases. Every row list returns to its row header, and every column list returns to its column header; hence Algorithm $S$ can continue advancing through links until it encounters the appropriate header node again. The header itself serves as a natural sentinel, so no null links are needed and no special tests for reaching the end of a row or column are required. This simplifies both traversal and updating during the pivot operation, since rows and columns are treated uniformly whether they contain many entries, one entry, or none.

Algorithm $S$ could be rewritten to use straight linear lists. In that case the list heads would contain links to the first element of each row or column, and the last element would contain a null link. Every traversal would then require explicit tests for null links and additional treatment of empty rows and columns. The algorithm would therefore become somewhat longer and less elegant, but no essential part of the pivot method depends on circular linkage. The circular lists are used for convenience and simplification of the program, not because they are indispensable.