468,253 Members | 1,293 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,253 developers. It's quick & easy.

need for doubly linked list


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?

--
dssuresh6
------------------------------------------------------------------------
Posted via http://www.codecomments.com
------------------------------------------------------------------------

Nov 14 '05 #1
4 2559
-----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)

iD8DBQFBnPwQagVFX4UWr64RArTvAJ9zW3Nr7yiNX81cbWqYBw oroDRTvgCeLBWt
wuZXxQK46EMlgJHCZJJJzUs=
=R+w8
-----END PGP SIGNATURE-----
Nov 14 '05 #2
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
Nov 14 '05 #3
>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
Nov 14 '05 #4
dssuresh6 <ds**************@mail.codecomments.com> wrote in message news:<1100806655.sXMKofQvvJZTtyhOrpcBCQ@tng>...
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?
Nov 14 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

3 posts views Thread by surrealtrauma | last post: by
5 posts views Thread by free2cric | last post: by
1 post views Thread by drewy2k12 | last post: by
2 posts views Thread by zoro | last post: by
3 posts views Thread by maruf.syfullah | last post: by
5 posts views Thread by adam.kleinbaum | last post: by
kim6987
4 posts views Thread by kim6987 | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.