Linked list

From DmWiki

At its most basic level, a linked list is a data structure consisting simply of a series of node structures, which are linked to each other.

In each structure, there is a pointer of the structure's type, to the "Next" item in the list. e.g.

struct Node
{
    // data goes here
    Node *next;
};

Now you declare the first item. This is your handle into the linked list

Node *linked_list;
linked_list->next = NULL;

Making sure to set the next pointer to NULL so that we know that this Type item has no next item.

Now lets say we wanted to add an item to the end of the list. We'd just do this:

linked_list->next = new Node;

Simple as that. Obviously when we close down, or delete the list, we'd need to delete the next item. This can all be sorted out in a destructor.

As we keep adding on items, it becomes clear that we can't simply say "I'd like the 5th item in the list". We have to traverse through the list. For this reason, linked lists are not appropriate if you need random access to various members. However, if you have data that you will only be accessing in order, it is very fast, because you don't have to look up the item each time you just use a loop, or a recursive function, to follow the next pointer each time.

If you need to go both directions along the list, it's clear enough that you can simply add a Type *prev; pointer to the structure, and fill it up when appropriate. This is called a doubly-linked list.

Now lets say you had 3 items in the list, and you wanted to add a new item after the first. This is really easy with linked lists.

Node *second = linked_list->next; // get the current second item's location
linked_list->next = new Node; // allocate memory for the new item, after the first item
linked_list->next->next = second; // make the new item's next item the previous second item

Maybe that's a little clumsy, but you obviously wouldn't be doing this with absolute references to the items involved. With a doubly linked list you just need to add a little extra code to set up the prev; pointers too. That is, inserting and removing elements in the middle is done in constant time, O(1), with linked lists.

STL implementation: std::list (http://www.sgi.com/tech/stl/List.html)