# doubly linked list tail pointer in struct

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 06-08-2007
bazzano
doubly linked list tail pointer in struct
Hi guys just a question about doubly linked lists... Do you have to declare a tail pointer in a struct to create a doubly linked list? If not when would you if you do?
• 06-08-2007
vart
Yes this is the idea (if you mean the pointer to the next node...
Code:

```struct node {   struct node* next;   struct node* prev;   void* data; }```
if you mean - that you need to store pointer to the last node - then it depends if the list is cyclic (the last node next points to the first node...
In this case you need to store only head and can walk the list any direction...

Maybe you should read Prelude's texts on the lists? See the link to her site in her profile.
• 06-08-2007
bazzano
I have done pointers to both previous and next in the struct but i am unsure as to why you need a tail pointer in a struct when in a doubly linked list you just need next and previous.
• 06-08-2007
KONI
Well, one of the advantages of a double linked list is that you can iterate it in two directions. To be able to iterate it backwards though, you need a pointer to the last element (the tail).

Code:

```struct myList{   struct node *head;   struct node *tail; }```
Let's say you have a list filled with data and want to find a value. If you know that the item is closer to the end, you can iterate from the tail backwards. You could also iterate in a threaded approach forwards and backwards simultaneously.
• 06-08-2007
bazzano
So if i did the threaded approach with pointers to next and previous that would still be of a doubly linked list type technically?
• 06-08-2007
Salem
A doubly linked list just means it has next and prev pointers.

How many pointers (and where they point) you have to point to your linked list (double or otherwise) is a completely separate issue.

Code:

```              +========+           +---|  Head  |           |  |        |           |  |  Tail  |------------------------------------------+           |  +========+                                          |           |                                                      |           |                                                      |           V                                                      V         +========+    +========+    +========+    +========+    +========+         |  Next  |--->|  Next  |--->|  Next  |--->|  Next  |--->|  Next  |--->NULL         |        |    |        |    |        |    |        |    |        |  NULL<---|  Prev  |<---|  Prev  |<---|  Prev  |<---|  Prev  |<---|  Prev  |         +========+    +========+    +========+    +========+    +========+```
There is nothing to stop you only having a head pointer to a double linked list.

Nor is there anything to stop you having both head and tail pointers to a singly linked list.
• 06-09-2007
iMalc
A most excellent diagram!
• 06-10-2007
ssharish2005
Salem, I have tried to do that many times to draw a diagram while posting. But because of these spaces and tabs i never get the right diagram when i click on post button.

Did u draw it on a normal editor and then posted it or did u drew on the web-form editor itself.

ssharish2005
• 06-10-2007
Salem
Use a normal code editor, and make sure all the indentation is only spaces (never use tabs).
Then post the result inside code tags.
• 06-10-2007
ssharish2005
hmmm interesting, Thanks Salem for that

ssharish2005
• 06-10-2007
zacs7
Quote:

Originally Posted by Salem
Use a normal code editor, and make sure all the indentation is only spaces (never use tabs).
Then post the result inside code tags.

Related question, Is it a good idea to use tabs when indenting source or spaces?
• 06-10-2007
Salem
• 06-10-2007
brewbuck
Quote:

Originally Posted by bazzano
I have done pointers to both previous and next in the struct but i am unsure as to why you need a tail pointer in a struct when in a doubly linked list you just need next and previous.

How about so you don't have to traverse the entire list just to append an element?

A better question would be, under what circumstances should you NOT have a tail pointers? One example is the use of a linked list as a stack -- all the operations occur on only one end of the list, so you don't need a tail.
• 06-11-2007
dukysta
Quote:

Maybe you should read Prelude's texts on the lists? See the link to her site in her profile.
Can somebody post a link?I can't view profile.
• 06-11-2007
MacGyver
Quote:

Originally Posted by dukysta
Can somebody post a link?I can't view profile.

http://www.eternallyconfuzzled.com
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last