Doubly Linked Lists

I have known Lisp now for over 20 years. Lisp uses singly linked lists. Each cell in a list contains the contents of the cell and a pointer to the next cell. This means that if you have a list X = (a b c), you can add an item d to it to make a new list Y = (d a b c), without altering the value of X. There are numerous advantages of this which are immediately apparent to any Lisp programmer. Lisp does give you the ability to modify lists, but this has to be used with care. Prolog, and functional languages such as Haskell, also support singly linked lists, which cannot be modified.

Cells in doubly-linked lists have a pointer to the previous cell as well as to the next cell. To a naive programmer, this gives them the edge over singly linked lists, as in them you cannot access the previous cell, but this comes as a heavy price: when you add an item to the list, you've changed the value of the list.

And what is the previous cell, anyway? In Lisp, I can do this:

eval> (setf x '(a b c))

(a b c)

eval> (setf y (cons 'd x))

(d a b c)

eval> (setf z (append '(e f) x))

(e f a b c)

eval> y

(d a b c)

eval> z

(e f a b c)

eval> x

(a b c)

and the value of x stays the same. But if I'd used doubly linked lists, the list would change value when the d was consed onto it, and the append operation would then be faced with a d that shouldn't be there.

What about things like implementing queues? With doubly linked lists, I can add an extra cell to one end, and remove a cell from the other, in constant time. With a singly linked list, I can't without one of the operations requiring a list traversal, which is linear time. Think again. Here's the solution in Emblem: queue.lisp.txt It just required a bit of thought. (NB queue.lisp.txt contains shared source code, so if you download it at work you mustn't save a copy.)

On only one occasion have I used doubly linked lists, and it soon became clear that this was a mistake. This was when I tried to implement a simple text editor, with each line of text being a list item. This is the wrong approach because text is composed of characters, and newline characters should be treated, for most purposes, like any other character. Lists, doubly or singly linked, are not the right data structure here.

Doubly linked lists are often used by other programmers, yet each time I see one, I have found that it was either better implemented differently, or the previous pointers were never used! They were also once included as library code in MacLisp (where they were called threads), but ditched when Common Lisp and Emacs Lisp were defined. I have therefore come to the conclusion that doubly linked lists are an anti-pattern.

Deques

Doubly linked lists are used in C++'s STL to implement deques ( double ended queues). Leaving aside the issue of what the deque they're actually useful for, deques don't need to be implemented as doubly linked lists. You can implement then as arrays with pointers to each end, and if they fill up, malloc some more memory (say, twice the size of the original array), move the old data there and continue.


This page was linked to from

and was last updated on 2006-01-03 at 20:56.

© Copyright Donald Fisk 2006