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.
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.
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.
Yeah that's one of the first ones I looked at.
I just don't get how it stats with
and what's with theCode:root->next = 0; //I guess it's just going to the next object in line?
?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?
Let's look at the code in the example from the tutorial:
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; }; 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 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.Code:struct node { int x; node *next; };
Now the first line of main()...
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:node *root; // This will be the unchanging first node
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 = new node; // Now root points to a node struct
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.Code:root->next = 0; // The node root points to has its next pointer // set equal to a null pointer
The next line sets x in root to 5:
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->x = 5; // By using the -> operator, you can modify the node // a pointer (root in this case) points to.
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.Code:root->next = new node; root->next->next = NULL; root->next->x = 10;
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.
It nice to know how they work, but you should also realize that you will probably never need to write one in C++.
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.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; } }
Last edited by MacGyver; 05-14-2007 at 06:51 PM.
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?
It's actually easier to read than the recursive version, in my opinion.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; } }
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.
I guess you should never do something like this, though:
Code:delete n; n = n->next; //oops!
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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; } }
It's a lot easier to understand when it's broken down and explained. Thanks all