Thread: Linked Lists

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    92

    Linked Lists

    Does anyone know of a really good Linked List tutorial for C++? I've been looking online and in my texts and most of it is confusing.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    There's a tutorial on linked lists on this website.

    The basic idea for a simple linked list is that you have 2 parts to a struct or class:

    1) The pointer to the next element in the linked list.
    2) The payload, which is basically the data that you're storing at this element, be it a number, a string, or whatever else.

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    92
    Yeah that's one of the first ones I looked at.

    I just don't get how it stats with
    Code:
    root->next = 0; //I guess it's just going to the next object in line?
    and what's with the
    Code:
    root->x = 4
    ?

    but then my book does stuff like
    Code:
    root->info // without explaining what info is.... is it a function or just something that nodes can use?

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Let's look at the code in the example from the tutorial:

    Code:
    struct node {
      int x;
      node *next;
    };
    
    int main()
    {
      node *root;      // This will be the unchanging first node
    
      root = new node; // Now root points to a node struct
      root->next = 0;  // The node root points to has its next pointer
                       //  set equal to a null pointer
      root->x = 5;     // By using the -> operator, you can modify the node
                       //  a pointer (root in this case) points to.
    }
    The first important thing to realize is that the linked list is made up of objects of this struct:

    Code:
    struct node {
      int x;
      node *next;
    };
    The link to the next node in the list is the member variable next. The actual payload is member variable x. This will be a linked list consisting simply of just numbers.

    Now the first line of main()...

    Code:
    node *root;      // This will be the unchanging first node
    This is a pointer to an object of type node, but it's just a pointer pointing nowhere in particular, so we need to initialize it to point to somewhere. Next line we do this:

    Code:
    root = new node; // Now root points to a node struct
    Now we manually have to set the x and next member variables of this new struct object that we dynamically allocated. So first in this example, the first next variable is handled.

    Code:
     root->next = 0;  // The node root points to has its next pointer
                       //  set equal to a null pointer
    Why 0 was chosen I have no idea, but imo it should be NULL since we're dealing with pointers, but it doesn't matter deep down since the idea is the same. What this does is set the next pointer of object root to NULL (or 0). This is how you know that you've reached the end of a linked list: namely when the next pointer points to NULL.

    The next line sets x in root to 5:

    Code:
    root->x = 5;     // By using the -> operator, you can modify the node
                       //  a pointer (root in this case) points to.
    You now have created one element of a linked list. If you wanted to create another element in the list, you could do this:

    Code:
    root->next = new node;
    root->next->next = NULL;
    root->next->x = 10;
    An important thing that this tutorial fails to do is to deallocate the memory for a linked list. If you don't do this, you have memory leaks, which are always bad.

    The idea is that you have a struct of an object that points to another struct of an object. As long as you have the root node, you can sequentially go through the linked list and find any element inside of it.
    Last edited by MacGyver; 05-14-2007 at 04:42 PM.

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    88
    It nice to know how they work, but you should also realize that you will probably never need to write one in C++.

  6. #6
    Registered User
    Join Date
    Apr 2007
    Posts
    26
    Quote Originally Posted by MacGyver View Post

    An important thing that this tutorial fails to do is to deallocate the memory for a linked list. If you don't do this, you have memory leaks, which are always bad.
    How would you go about doing that?

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Quote Originally Posted by vrek View Post
    How would you go about doing that?
    Code:
    void deleteList(node *n)
    {
    	if(n != NULL)
    	{
    		if(n->next != NULL) /* Optional check */
    		{
    			deleteList(n->next);
    		}
    		std::cout << "Deleting element with value: " << (n->x) << std::endl; /* For debugging purposes. */
    		delete n;
    	}
    }
    Technically, you don't even need that second condition checked; you could just go ahead and call deleteList(n->next) anyway. Eventually you'll pass NULL to it, which the function will handle by just ignoring it. So you either have an extra check for every iteration vs one extra function call for the entire list.
    Last edited by MacGyver; 05-14-2007 at 06:51 PM.

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Personally, I think that recursively freeing linked lists is a bad idea. (More complicated data structures, like binary trees, are another matter altogether.)

    The alternative, of course, is iteration (like while loops). Iteration can be slightly faster, because there is no overhead of a function call. Recursive functions can cause stack overflows if you try to free too much memory with them. Debugging recursive functions can be very difficult, especially compared with iterative ones. However, some compilers can convert recursive functions into iterative ones -- but one shouldn't rely on this.

    So . . . an iterative version?
    Code:
    void deleteList(node *n)
    {
    	while(n != NULL) {
    		std::cout << "Deleting element with value: " << (n->x) << std::endl; /* For debugging purposes. */
    		delete n;
    
    		n = n->next;
    	}
    }
    It's actually easier to read than the recursive version, in my opinion.

    In some situations (like the towers of Hanoi), recursive versions can be much simpler than iterative versions. Sometimes an iterative version is impossible. But for the relatively simple task of freeing a linked list, which is a linear structure, there's really no call for recursion.

    Just my two cents.
    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.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I guess you should never do something like this, though:
    Code:
    delete n;
    n = n->next; //oops!
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    I agree the iterative approach is better, but yeah you shouldn't deallocate n and then try to access its next member.

    Slight alterations:

    Code:
    void deleteList(node *n)
    {
    	node *temp;
    	while(n != NULL) {
    		std::cout << "Deleting element with value: " << (n->x) << std::endl; /* For debugging purposes. */
    		temp = n;
    		n = n->next;
    		delete temp;
    	}
    }

  11. #11
    Registered User
    Join Date
    Mar 2007
    Posts
    92
    It's a lot easier to understand when it's broken down and explained. Thanks all

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