Linked Lists

This is a discussion on Linked Lists within the C++ Programming forums, part of the General Programming Boards category; Ok so im pretty new to C++ and am using the tutorials to get started. So far ive been pretty ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    8

    Linked Lists

    Ok so im pretty new to C++ and am using the tutorials to get started. So far ive been pretty good but when i got to linked lists i got lost. I understand the concept but the acutally code makes absolutly no sense. While i realize there are comments if someone has a easy way to explain it or could help me with adding more detailed comments it would be greatly appreciated. You can reply to the post of reach me at <<snipped>>. Thankz

    Code:
    struct node {
      int x;
      node *next;
    };
    
    int main()
    {
      node *root;       // This won't change, or we would lose the list in memory
      node *conductor;  // This will point to each node as it traverses the list
    
      root = new node;  // Sets it to actually point to something
      root->next = 0;   //  Otherwise it would not work well
      root->x = 12;
      conductor = root; // The conductor points to the first node
      if ( conductor != 0 ) {
        while ( conductor->next != 0)
          conductor = conductor->next;
      }
      conductor->next = new node;  // Creates a node at the end of the list
      conductor = conductor->next; // Points to that node
      conductor->next = 0;         // Prevents it from going any further
      conductor->x = 42;
    }
    Last edited by Salem; 12-22-2007 at 04:33 AM. Reason: Snip email address

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So, do you have a real question, or do you just want someone to write arbitrary comments that you MAY find useful?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    8
    Well adding more detailed comments or getting on a IM would be great but here

    What exactly is "->" mean through the code

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    -> requires a pointer to a struct on the left, and a member of that struct on the right. The result is the value of the member in the struct pointed to. So: root->x is the "x" variable in the structure that root points to.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    something->other is short for (*something).other. So what it means is:
    something is a pointer, and I want to get to the element other that the pointer points to.

    This is part of "pointer to structure" learning, and is an essential part of linked lists, since linked lists are structures with a pointer to the next structure.

    [Silly note: This is my 0x1000th post!]

    --
    Mats
    Last edited by matsp; 12-21-2007 at 06:26 PM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Scroll down to "Pointers to structures": http://www.cplusplus.com/doc/tutorial/structures.html

    [edit] Too slow. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Dec 2007
    Posts
    8

    ok...

    ok so its using pointers and changing the members of the structures...

    and secondly why does it use a pointer as a acutally member of the structure at first.

    Code:
    struct node {
      int x;
      node *next;
    };

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    8
    and thanks for your quick answers amd help i really am not grasping this concept

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Bleu_Cheese View Post
    ok so its using pointers and changing the members of the structures...

    and secondly why does it use a pointer as a acutally member of the structure at first.

    Code:
    struct node {
      int x;
      node *next;
    };
    Well, the short answer is "That's how linked lists work".

    The idea behind linked lists is that you can extend the list at the end, and add nodes in the middle of the list. To do that, you need some sort of "link" to the next element in the list. This is your "next" pointer.

    It has to be a pointer, because the next node isn't part of the current element - it is the NEXT element. Does that make sense?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Dec 2007
    Posts
    8

    Final explanation ... i hope

    ok im starting to understand maybe parts of this. I added comments in here explaining what i could but there are many parts that im not exactly sure. If anyone would be willing to replace my comments with some kind of explanation i believe i will understand this. If not thanks for your help and ill try to figure it out.

    Code:
    struct node {
      int x;        
      node *next;
    };  
    int main()
    {
      node *root;       // these are 2 pointers to the structure
      node *conductor;  
      root = new node;  // it uses a ptr to make a starting point
      root->next = 0;   // Need more explanation
      root->x = 12;     // Need more explanation
      conductor = root; // sets the other ptr = the ptr conductor
      if ( conductor != 0 ) {       // if the conductor not = to 0 ... how does it know that? never defined?
        while ( conductor->next != 0)   // Need more explanation
          conductor = conductor->next;  // Need more explanation
      }
      conductor->next = new node;  // Need more explanation
      conductor = conductor->next; // Need more explanation
      conductor->next = 0;         // Need more explanation
      conductor->x = 42;           // Need more explanation
    }

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Code:
    struct node {
      int x;        
      node *next;
    };  
    int main()
    {
      node *root;       // these are 2 pointers to the structure
      node *conductor;  
      root = new node;  // it uses a ptr to make a starting point
    Code:
      root->next = 0;   // Need more explanation
    That's the same as (*root).next = 0. What it's doing is setting the "next" member of the newly allocated structure assigned to root to 0, or NULL -- the standard value used to indicate that the pointer is in fact pointing at nothing at all.
    Code:
      root->x = 12;     // Need more explanation
    This is setting the x value of the first node in the list, the element that was dynamically allocated and assigned to root. It's syntactically equivalent to (*root).x = 12;.
    Code:
      conductor = root; // sets the other ptr = the ptr conductor
    Code:
      if ( conductor != 0 ) {       // if the conductor not = to 0 ... how does it know that? never defined?
    What do you mean? conductor was "defined" -- it's a variable of type node*.

    Basically that's checking to see if conductor is pointing at a valid element or not. If it's not, conductor will contain 0 or NULL. Presumably this is so the contents of conductor can be used. Accessing a node that doesn't really exist is not a very good idea.
    Code:
        while ( conductor->next != 0)   // Need more explanation
          conductor = conductor->next;  // Need more explanation
    This loop loops while the next element of the structure that conductor is pointing to is a valid node. Every time, it advances conductor to point to the next node.

    In effect, after this loop executes, conductor will be pointing at the last element in the linked list, because conductor->next will be NULL -- there will be no node after the current one.
    Code:
      }
      conductor->next = new node;  // Need more explanation
    conductor->next, which was NULL, is now being assigned to a new, dynamically allocated node.
    Code:
      conductor = conductor->next; // Need more explanation
    Just like in the loop, conductor is advanced to point to the new node.
    Code:
      conductor->next = 0;         // Need more explanation
      conductor->x = 42;           // Need more explanation
    }
    42! The answer to life, the universe, and everything! Never mind.

    The data in the new node is being set up. Before this happens, the node will contain random data, so setting it is a good idea.
    Last edited by dwks; 12-21-2007 at 06:53 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Registered User
    Join Date
    Dec 2007
    Posts
    8
    Thanks much, I think I have some what of a basic understanding of this now. Do you happend to have something that really puts this to use ?

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    Well, a linked list is typically used when you have elements (or nodes) that refer to each other. One idea might be a game where there are lots of rooms. Since a room would typically be a class, it would have members that points to the next room depending on the direction you would walk.
    So it contains a pointer for north, south, west and east. They all point to another room object.

    That's one thing I can think of.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Dec 2007
    Posts
    8
    you know ... that concept just turned the little light bulb in my head on lol ... i think it actually makes sense lol

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 09:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21