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
[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 FunctionalProgrammingLanguage
s (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