Problem Detail: Are there advantages of implementing a singly instead of a doubly linked list other than space?
Asked By : PRX
Answered By : babou
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28496 Ask a Question Download Related Notes/Documents