Thread: doubly linked list tail pointer in struct

  1. #1
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252

    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?

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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.
    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

  3. #3
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252
    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.

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  5. #5
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252
    So if i did the threaded approach with pointers to next and previous that would still be of a doubly linked list type technically?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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"

  8. #8
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    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

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

  10. #10
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    hmmm interesting, Thanks Salem for that

    ssharish2005

  11. #11
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Quote Originally Posted by Salem View Post
    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?

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by bazzano View Post
    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.

  14. #14
    Registered User
    Join Date
    Jun 2007
    Posts
    7
    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.

  15. #15
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Quote Originally Posted by dukysta View Post
    Can somebody post a link?I can't view profile.
    http://www.eternallyconfuzzled.com

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  3. Bi-Directional Linked Lists
    By Thantos in forum C Programming
    Replies: 6
    Last Post: 12-11-2003, 10:24 AM
  4. Doubly linked list woes
    By foniks munkee in forum C Programming
    Replies: 3
    Last Post: 03-06-2002, 03:04 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM