Discussion on Linked Lists

Additional notes

Both singly-linked and doubly-linked lists are established techniques, having been used in programs for over $40$ years. They are discussed, for example, by KnuthD. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, third edition, 1997.. Even the SEList data structure seems to be a well-known data structures exercise. The SEList is sometimes referred to as an unrolled linked listZ. Shao, J. H. Reppy, and A. W. Appel. Unrolling lists. In Proceed- ings of the 1994 ACM conference LISP and Functional Programming (LFP’94), pages 185–195, New York, 1994. ACM..

Another way to save space in a doubly-linked list is to use so-called XOR-lists. In an XOR-list, each node, $u$, contains only one pointer, called u.nextprev, that holds the bitwise exclusive-or of u.prev and u.next. The list itself needs to store two pointers, one to the dummy node and one to dummy.next (the first node, or dummy if the list is empty). This technique uses the fact that, if we have pointers to u and u.prev, then we can extract u.next using the formula

$$\text{u.next} = \text{u.prev} \ \^{} \ \text{u.nextprev}$$

(Here ^ computes the bitwise exclusive-or of its two arguments.) This technique complicates the code a little and is not possible in some languages, like Java and Python, that have garbage collection but gives a doubly-linked list implementation that requires only one pointer per node. See Sinha’s magazine articleP. Sinha. A memory-efficient doubly linked list. Linux Journal, 129, 2005. URL: http://www.linuxjournal.com/article/6828 [cited 2013-06-05]. for a detailed discussion of XOR-lists.