need for doubly linked list

Discussion in 'C Programming' started by dssuresh6, Nov 18, 2004.

  1. dssuresh6

    dssuresh6 Guest

    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
    ------------------------------------------------------------------------
    dssuresh6, Nov 18, 2004
    #1
    1. Advertising

  2. dssuresh6

    Lew Pitcher Guest

    -----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-----
    Lew Pitcher, Nov 18, 2004
    #2
    1. Advertising

  3. dssuresh6

    Ben Pfaff Guest

    dssuresh6 <> 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
    Ben Pfaff, Nov 18, 2004
    #3
  4. >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
    Gordon Burditt, Nov 18, 2004
    #4
  5. dssuresh6 <> 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?
    J. J. Farrell, Nov 19, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    921
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    453
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    321
    Terry Reedy
    Sep 5, 2005
  4. Daniel
    Replies:
    5
    Views:
    381
  5. zoro
    Replies:
    2
    Views:
    303
Loading...

Share This Page