Double Linked List

Type of LinkedList where each node knows both its neighbors (left and right).

Its advantage over SingleLinkedList is that removing operations to each node can be done without accessing the entire list, that is, O(1) instead of O(n).

The obvious drawback is the need for more memory space than SingleLinkedList, but see TwoPointersInOneWord for a way to save space in certain circumstances.

A perhaps less obvious drawback is that you cannot have two lists share a common tail.

two lists share a common tail

I'm curious. Have any of you ever deliberately done this?.

I've done it. In an implementation of a FunctionalProgrammingLanguage it makes sense not to copy structures. I had a list to which I prepended items, but the original still had to be accessible. Then I prepended different items to the original and I had two lists with a common tail. Worked well, allowing for its limitations. Saved a lot of unnecessary copying

It that case you need to implement CopyOnWrite semantics.

[This is done in LispLanguage all the time. If you take the cdr of any other list, as far as Lisp can tell, the result is a separate list that happens to have a common tail with the first one. Assuming, of course, that you don't try and change the cdr/car of any of the involved cons nodes...]

In most FunctionalProgrammingLanguages (but not Lisp and Scheme), lists are immutable, so CopyOnWrite is never needed (no writes => no copies).

Nearly every time I've used a SingleLinkedList it has eventually been replaced with a DoubleLinkedList. I no longer bother with SingleLinkedList.

CategoryDataStructure