Are there advantages of implementing a singly instead of a doubly linked list other than space?
3 Answers
$\begingroup$
$\endgroup$
2
Other than saving space, the first advantage I can see for singly linked lists over doubly linked lists is to avoid having to update two links instead of one when you modify the list, when adding an element for example.
Of course, one might say that you can always ignore the second link, but in that case, it is no longer doubly linked, but only an unused field.
What might also be seen as an advantage is that singly linked list are necessarily consistent, though possibly wrong when there are bugs in the program. Doubly linked lists can end-up having inconsistent links forward and backward. But it is debatable which of the two cases, if any, is an advantage.
update:
I had tried to see some impact on garbage collection, but found none. Actually, there is one when storage reclamation is done by reference counting, as reference counting is defeated by loops, and doubly linked lists contain loops. Singly linked list escape the problem. Of course, there are ways around it for doubly linked lists, such as the use of weak pointers, or programmable reference counting as part of data abstraction.
-
$\begingroup$ Would knowing that the list is always traversed in one direction have benefits for multithreaded programming? (Aside: an alternative to completely ignoring the second link would be to have that address as advisory, requiring a check to confirm correctness. If eventually consistent updates on insert/delete and checks on probes were cheaper than consistent updates, such might make sense. Just noodling.) $\endgroup$– user4577Commented Jul 18, 2014 at 20:19
-
$\begingroup$ @PaulA.Clayton I tried to imagine possible impact on garbage collection or the use of weak pointers. Nothing came to mind, except right now what I just added as I was answering you. I do not really have precise answers to your suggestions, but they do make sense a priori, and it might be nice to have actual examples. After all, there may be more than one would expect from this apparently innocuous question. $\endgroup$– babouCommented Jul 18, 2014 at 23:00
$\begingroup$
$\endgroup$
Yes. Singly linked lists are easier to work with in highly concurrent situations, because there's less data to keep consistent.
For example, suppose you want to append a lot of items to a linked list in a wait-free way. It's okay if consuming the items is not wait free, but producers absolutely must not block no matter what the other threads are doing.
With a singly linked list you can just do:
var newNode = new Node(someValue);
var prevNode = Interlocked.Exchange(ref _insertionNode, newNode);
prevNode.next = newNode; //note: next is volatile; this is a write-release
Easy! Guaranteed progress for every producer. Produced nodes may not be immediately visible from the head of the list (a previous producer may have yet to update the next pointer of the node it got), but they eventually will be.
With a doubly-linked list, you need CAS loops and other try-retry-retry-fix-up sorts of constructs. It's a lot easier to make a mistake, so I won't try to just zip off an example.
$\begingroup$
$\endgroup$
Single-link lists are easier to work with, and in many cases are adequate for the problem, but any application requiring moving both ways on the list requires a double-linked list. Presuming you were writing a text editor where each line was a dynamically generated string (so you don't waste tons of memory allocating strings much larger than any specific line normally is), in order to move, say, up to the previous line, or up or down a screen, you'd have to be able to quickly traverse the pointers to the next/previous line (or page/screen) in memory.
Also, a double-linked list does not have to be a loop. Each entry has a "prev" and "next" pointer, prev pointing to the prior (previous) entry, next pointing to the next one. The top of the list has a null prev pointer, the last one has a null next pointer.
