Thread: Linked Lists?

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    20

    Linked Lists?

    Hi, this is a newbie question but here goes...

    I cannot seem to understand linked lists! Its one of those things you just don't get. I've read the tutorial about 1,000 times and I still don't get it. Could someone just explain the absolute basics of how it works, or show me a good tutorial?

    -Thanks a ton

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Imagine a series of post-it notes on a piece of string.

    Adding to either end is pretty easy, adding to the middle is harder (cut the string, add the note, tie the two strings back together again).

    What else did you want to know?
    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.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    20
    No offense, but what is that supposed to mean?

    I mean like code.
    Such as:

    Code:
    Blah, blah, blah.

    The first blah means....

    and so on.

    -Thanks Anyway

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Code:
    |HP|------->  |Dell|------->  |Acer|-------->  |Mac|-------->  |Sony|
    so that's a linked list. one points to another, the next one.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The principle of linked lists is that they have a "link" from one element to the next. This link is usually called "next".

    The link is often a pointer, but you can make linked lists with arrays, where the "next" component is an index to the next item.

    The whole idea is to "chain" things together, and not have to shuffle things if you need to insert or remove items.

    Aside from that, please try to explain better what part you don't understand.

    --
    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.

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    20
    Maybe i should have been more specific. I mean like syntax.
    such as:

    Code:
    Some commands and stuff... // This command means...
    
    More commands and explanations...
    Like a sample program with explanations on what each part is for.

    This is the code I have been looking at:

    Code:
    struct node {
      int x;
      node *next;
    };
    
    int main()
    {
      node *root;      
      root = new node; 
      root->next = 0;  
                       
      root->x = 5;     
    }
    One of the things I don't understand is why are there two pointers (specifically root) when i looks like the "next" would be a pointer to for every node you use. I realize "root" is a part of the struct but then I get really confused when I try to think about why it would be a pointer then!!!
    Last edited by Suudsu2200; 10-07-2007 at 04:12 PM.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You need a pointer to the beginning of the list - this is the "root" from which the list grows.

    Code:
    int main()
    {
      node *root;      // Pointer to the first node
      root = new node;  // Get memory for the first node.
      root->next = 0;  // Mark the "next" node as "not there".
                       
      root->x = 5;     // Fill in the list with some value. 
    }
    However, this is pretty meaningless - that's like saying you have a SET of tools when you have one screwdriver. This is a linked list with one element, which is valid, and one screwdriver is a set of tools too - but very limited.

    A more reasonable example:
    Code:
    #include <iostream>
    
    struct node {
      int x;
      node *next;
    };
    
    int main()
    {
      node *root;      // Pointer to the first node
      root = new node;  // Get memory for the first node.
      root->next = 0;  // Mark the "next" node as "not there".
                       
      root->x = 5;     // Fill in the list with some value. 
    // Since this is C++, we can introduce new variables later.
      node *newNode;
      newNode = new node;   // Create one more item. 
      newNode->x = 7;   // Set x to 7. 
      newNode->next = 0;  // Mark this as the end. 
      root->next = newNode; // Insert it after root. 
      for(int i = 0; i < 3; i++) {
         node *current = newNode; // This is the previously inserted node.
         newNode = new node;   // A further node.
         newNode->x = i + 10;  // Set x to a something.
         newNode->next = 0;  // Mark the end.
         current->next = newNode;   // Insert the node AFTER current. 
      }
      
      node *temp;  // A temporary node pointer.
      temp = root; // Set it to the start of the list. 
      while (temp != 0) {  // Check if we are at the end (0), if not, go print the contents of the list
    	  std::cout << "x = " << temp->x << std::endl;   // Print the "x" for this node.
         temp = temp->next;   // Go to the next item in the list. 
      }
      return 0;
    }
    Output:
    Code:
    x = 5
    x = 7
    x = 10
    x = 11
    x = 12
    --
    Mats
    Last edited by matsp; 10-07-2007 at 04:45 PM. Reason: completing the code and giving output.
    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.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    20
    That is really helpful but (and I don't want to sound ungrateful but) 2 things:



    1. Could you please supply a complete code (Something I can cut and Paste and run)

    2. I am pretty newbish (as you probably know) and I'm just coming back to C++ after a while, do you think you could supply a simpler example?

    -Thanks a bunch, I really appreciate it.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Because I'm so kind, I've added the necessary include file and copied the structure from your example into the extended example I wrote. Instead of re-posting some twenty or so lines of identical code, I edited the original post above.

    If you don't want the LONG example I showed, then use the short "screwdriver is a set of tools" example that you gave (copy the #include line in my previous post - or remove all of the extension from my example)- but it DOES absolutely nothing other than create a single element linked list.

    --
    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
    Oct 2001
    Posts
    2,129
    root is just so that the list doesn't get lost in memory.

    also, in your example, root was not part of a struct. (not to say that it shouldn't be like that)

  11. #11
    Registered User
    Join Date
    Sep 2007
    Posts
    20
    Thanks matt and everyone else,

    P.S. You are so kind

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Just one further comment that I thought of after I had shut the computer down.

    The analogy that Salem gives isn't bad, but I prefer to look at it as a chain of paperclips, with post-it notes on each paper-clip. The hook that connects one paper-clip to another is the "next" pointer, and the "clip" bit is the part "holding your data" (x in the above example-code).

    --
    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.

  13. #13
    Registered User
    Join Date
    Sep 2007
    Posts
    20
    For anyone else with this problem

    http://richardbowles.tripod.com/cpp/...t/linklist.htm

    Really cleared it up for me.

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, 04: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, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM