dssuresh6 <ds**************@mail.codecomments.com> writes:
Whether browsing forward or backward can be done using a singly linked
list. Is there any specific case where a doubly linked list is needed?
For people who say that singly linked list allows traversal only in one
direction, I would say that using appropriate loops/recursion, traversal
in opposite direction is also possible. Then why the need for doubly
linked list?
When you use recursion to traverse a singly linked list in the
opposite of natural order, you are actually storing the backward
links in the automatic variables of the recursing function
activations. That memory doesn't come for free, and on most real
systems you'll use more memory and CPU time doing it that way
than by storing a second link in each list.
If you're going to do it using a loop, you either have to waste
lots of time traversing from the front of the list on each
backward traversal, or you have to, again, maintain a list.
The right thing to do is to use a singly linked list if it
naturally fits the algorithm you want to execute, or a doubly
linked list if it is more appropriate. "Use the right tool for
the job", in other words.
--
"...Almost makes you wonder why Heisenberg didn't include postinc/dec operators
in the uncertainty principle. Which of course makes the above equivalent to
Schrodinger's pointer..."
--Anthony McDonald
