need for doubly linked list

[dssuresh6]

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?

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

dssuresh6 wrote:
| 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?

Why the need for doubly linked lists? Why, to avoid having to code inappropriate
loops or recursion in order to traverse a list bidirectionally, of course.


- --
Lew Pitcher
IT Consultant, Enterprise Data Systems,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed are my own, not my employers')
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32)

iD8DBQFBnPwQagVFX4UWr64RArTvAJ9zW3Nr7yiNX81cbWqYBworoDRTvgCeLBWt
wuZXxQK46EMlgJHCZJJJzUs=
=R+w8
-----END PGP SIGNATURE-----

 

[Ben Pfaff]

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.

 

[Gordon Burditt]

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?

Multiplication can be done by repeated addition which can be done
by repeated incrementation. Why the need for a * operator? Most
likely, EFFICIENCY. Also remember that if you're using recursion
that recurses to a depth that depends on the input data, you can
unexpectedly run out of memory for activation frames (some people
would say "on the stack" here) without any (portable, or even
un-portable) way of checking ahead of time before your program dies.

Another issue for some uses of linked lists is how you can safely
update them while other {threads, processes, whatever} are using
them. You want the code where you have to lock out other accesses
to be short. This is outside the scope of portable C, though, which
doesn't have "other processes".

Gordon L. Burditt

 

[J. J. Farrell]

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?

To avoid loops/recursion. Perhaps people want to be able to browse
backwards using a couple of memory accesses in the same way as they
can browse forwards, instead of needing millions of memory accesses.

In a vague attempt to make this discussion even marginally topical
for this newsgroup, are you not also puzzled about why C has a
multiply operator, since its functionality can be achieved by using
appropriate loops/recursion with the addition operator?