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]

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.

When you understand the concept of linked lists, make sure to use std::list because the std namespace is your friend [wink].