Sign in to follow this  
DarkSuicide

Linked list

Recommended Posts

I am reading the book Teach Yourself C++ in 21 Days and the explanation they provide for linked lists is really confusing. I was wondering if anyone could provide me with a link to a good tutorial or somthing about linked lists. Thank you for your help.

Share this post


Link to post
Share on other sites
Here you go: link

There's quite a few good tutorials at that link.

EDIT: As an overview, a linked list is a data structure where each element in the structure points to another (usually logically adjacent) element. Using pointers in this way allows the structure to grow and shrink easier than an array, for instance.

To traverse the structure, one would start at the head of the list, then move to the next element through the head's next pointer, continuing until the last element - or tail - which usually contains a null pointer to the next element (since there is none).

Linked lists can be singly or doubly linked, meaning one can traverse the list in a forward direction only or back and forth, respectively. Singly linked list elements contain a pointer to the following element, while doubly-linked list elements contain pointers to both the following and previous elements.

To insert an element into a linked list, one would point the element just prior to the insertion point at the new element, then point the new element at the element that was once previously pointed to, like:

[a|->b] [b|->c] [c|->null] // 3 element list
[a|->b] [b|->newElement] [newElement|->c] [c|->null] // inserting a new element after b

The only change to the list is that of element b, whose next pointer now points to the new element. If this was an array, all elements after b - in this case just c - would have to be moved to the right to make room for the new element. Here, we just change and set a couple pointers.

To remove an element from a linked list, one would take the element just prior to the element being removed and point it at the element following the element to be removed, like:

[a|->b] [b|->c] [c|->d] [d|->null] // 4 element list
[a|->b] [b|->d] [d|->null] // 3rd element removed

Again, the only change to the list is the element b, whose next pointer now points to element d. All elements after the removal - in this case just d - are not affected. Compare this with an array, whose elements following a removal must be moved over to the left to fill in the space created by the removed element.

Doubly-linked lists work the same way, except that elements contain a previous pointer, and that pointer must be updated along with the next pointer in any insertion/removal actions.

This is just a brief overview, and the tutorials I linked to will explain it in much more detail.

[Edited by - stylin on December 4, 2005 3:52:47 PM]

Share this post


Link to post
Share on other sites
I think there is an article on them in resources/articles/general programming.

I can try and explain them to you, though:

A linked list is sort of a way to, well, link a bunch of items together, in a manner similar to how you would use an array. It has some advantages and disadvantages. One advantage is that to add or remove members, you don't have to resize the array and add the new elements after copying the whole array. You simply tell the last "node" in the chain to point to another element.

Linked lists are pretty complex, though they can be useful for some things. They require a pretty strong knowledge of pointer arithmetic. In C++, you would do something like this:

Each node has a pointer to the node in front of it and behind it. The head node's pointer to the one in front of it is NULL, since there isn't a node in front of it, and the tail node's pointer to the one behind of it is NULL for the same reason. When you add a node, you set the tail node's pointer to the one behind it to the memory address of the new node, and set the new node's "last" pointer (pointer to the one in front of it) to the original tail node. You set its "next" pointer to NULL, so that it becomes the new tail node.

It's hard to explain, but if you understand the purpose of the next and last pointers, you can draw yourself a picture of how it works and you'll probably figure it out. I don't think anybody can understand how to make a linked list properly without drawing it out. They are pretty complex constructs.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rob Loach
When you understand the concept of linked lists, make sure to use std::list because the std namespace is your friend [wink].


Seconded. While knowing how a linked list works and how to implement one is important, std::list is your friend.

Here's an overview from the C++ Faq Lite as to why you should consider using the standard containers rather than rolling your own.

On a side note, I haven't taken a look at Teach Yourself C++ in 21 Days, but if it has a section on creating dynamically resizable arrays, you probably want to be using std::vector, rather than rolling your own. Here's a tutorial. Here's another tutorial that covers vectors and lists.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this