Referencing lists by an edge

ABSTRACT

An edge reference into a list structure is a pair of pointers to adjacent nodes. Such a reference often requires little additional space, but its use can yield efficient algorithms. For instance, a circular link between the ends of a list is redundant if the list is always referenced by that edge, and list traversal is easier when that link is null. Edge references also allow threading of nonrecursive lists, can replace some header, cells, and enhance the famous exclusive-or trick to double-link lists.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 2: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 3: G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
• 4: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 5: Siklosy, L. Fast read-ordy algorithms for traversing trees without an auxiliary stack. Inf. Proc. Lett. 1, 4 (June 1972), 149-152.
• 6: Vitulli, N. VW: a small but potent machine-independent text editor. M.S. Th., Indiana U. ( April 1976).

INDEX TERMS

Keywords:
circular, cursor, doubly linked, header cell, list processing, overlapping sublist, pointer