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?
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.
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
A most excellent diagram!
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
hmmm interesting, Thanks Salem for that
ssharish2005
Opinion is divided - http://cboard.cprogramming.com/showthread.php?t=88282
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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.
Can somebody post a link?I can't view profile.Maybe you should read Prelude's texts on the lists? See the link to her site in her profile.