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?
Printable View
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?
Yes this is the idea (if you mean the pointer to the next node...
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...Code:struct node
{
struct node* next;
struct node* prev;
void* data;
}
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.
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.
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).
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.Code:struct myList{
struct node *head;
struct node *tail;
}
So if i did the threaded approach with pointers to next and previous that would still be of a doubly linked list type technically?
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.
There is nothing to stop you only having a head pointer to a double linked list.Code:+========+
+---| Head |
| | |
| | Tail |------------------------------------------+
| +========+ |
| |
| |
V V
+========+ +========+ +========+ +========+ +========+
| Next |--->| Next |--->| Next |--->| Next |--->| Next |--->NULL
| | | | | | | | | |
NULL<---| Prev |<---| Prev |<---| Prev |<---| Prev |<---| Prev |
+========+ +========+ +========+ +========+ +========+
Nor is there anything to stop you having both head and tail pointers to a singly linked list.
A most excellent diagram!
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
Use a normal code editor, and make sure all the indentation is only spaces (never use tabs).
Then post the result inside code tags.
hmmm interesting, Thanks Salem for that
ssharish2005
Related question, Is it a good idea to use tabs when indenting source or spaces?Quote:
Originally Posted by Salem
Opinion is divided - http://cboard.cprogramming.com/showthread.php?t=88282
How about so you don't have to traverse the entire list just to append an element?Quote:
Originally Posted by bazzano
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.
Can somebody post a link?I can't view profile.Quote:
Maybe you should read Prelude's texts on the lists? See the link to her site in her profile.
http://www.eternallyconfuzzled.comQuote:
Originally Posted by dukysta
Thx.