6
$\begingroup$

Are there advantages of implementing a singly instead of a doubly linked list other than space?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\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$ – Paul A. Clayton Jul 18 '14 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$ – babou Jul 18 '14 at 23:00
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.