473,239 Members | 1,582 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,239 software developers and data experts.

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 2897
-----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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: surrealtrauma | last post by:
I want to ask what's the differences between doubly liked list and linear liked list, and also the circular doubly liked list in terms of implementation. THX
5
by: free2cric | last post by:
Hi, how to detect head and tail in cyclic doubly link list ? Thanks, Cric
1
by: drewy2k12 | last post by:
Heres the story, I have to create a doubly linked list for class, and i have no clue on how to do it, i can barely create a single linked list. It has to have both a head and a tail pointer, and...
2
by: zoro | last post by:
hello: i'm not sure what the operations that would be affected if we didn't maintain a tail pointer in doubly linked list? so why is it important? your help is appreciated thank you
8
by: tonywinslow1986 | last post by:
I'm reading MIT's book "Introduction to Algorithms". The following is one of the excercises from it: < 10.2-8 Explain how to implement doubly linked lists using only one pointer value np per...
3
by: maruf.syfullah | last post by:
Consider the following Class definitions: class AClass { int ai1; int ai2; public: CClass* c; AClass(){}
5
by: adam.kleinbaum | last post by:
Hi there, I'm a novice C programmer working with a series of large (30,000 x 30,000) sparse matrices on a Linux system using the GCC compiler. To represent and store these matrices, I'd like to...
4
kim6987
by: kim6987 | last post by:
can you please spend a little time evaluating this code. I can not run it successfully thanks :) #include<stdio.h> #include<conio.h> #include<stdlib.h> #define SIZE 10 typedef struct dlist
1
by: Mahesh | last post by:
Hi Coders, I was asked to write a program to interchange numbers using doubly linked list @ Amazon. Here is the details with Code that i wrote. i/p: 1 2 3 4 5 6 7 8 .....n,n-1. o/p: 2 1 4...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.