Discussion on Linked Lists

Discover more aspects regarding linked lists.

We'll cover the following

Additional notes

Both singly-linked and doubly-linked lists are established techniques, having been used in programs for over 4040 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, uu, 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

u.next=u.prev ˆ u.nextprev\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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy