HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Using singly linked list instead of a doubly linked list?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
insteadsinglydoublyusinglistlinked

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#28496, answer score: 7

Revisions (0)

No revisions yet.