Beginner's Guide to Linked Lists

There seems to be a lot of beginners to C/C++ and Tek-Tips lately showing an interest in linked lists - what they are and how to use them. So I decided to write this FAQ on the subject to hopefully help make things easier for beginners to understand.

To understand linked lists, you'll need an understanding of what pointers are in C/C++. If your knowledge of pointers is a little shaky then you should first check out my other FAQ "A complete layman's guide to pointers" also in this FAQ area.

What is a linked list?
A linked list is kind of like an array of objects or variables. There is one big difference though: the linked list is not subject to a maximum containment size[sup]1[/sup] like a standard array. Consider this array of integers:[tt]

int myArray[1000];[/tt]

This array can only store up to 1,000 integers. If you try and add more later then it is a certifiable very bad thing!
A linked list, on the other hand, is not subject to this 'sizing' limitation. You do not declare a 'size' for your linked list when you declare it. You can keep adding and removing items to it at will.

Why use a linked list instead of an array?
Apart from not having a restricted size, linked lists can contain different kinds of variables and objects in a single list. This makes linked lists a very powerful feature of the C/C++ languages.

How does a linked list work?
To create a linked list, you need to create an object which will act as a container. This is easier to understand from a C++ perspective rather than C so for anyone who knows C and little C++ I'll try and throw as much light on it as possible.
The container is usually a structure ([tt]struct[/tt] or [tt]class[/tt]) which contains the information to be stored in the list plus a couple of special variables which help to link everything together into an array.
These special variables[sup]2[/sup] are simply pointers. One is a pointer to the very first item in the array, the second is a pointer to the next item in the array. These are usually called something like 'first' and 'next'.
The first pointer will remain static (or global) because its value is the same among all objects in the array. You need this pointer to be able to begin loops, etc. when looking through the list. In other words, the 'first' pointer is simply a kind of 'starting point' (akin to array[0]).
The second pointer 'next' is unique to each object in the array. The 'next' pointer will always point to the very next item in line in the array. If there are no more items (ie. the last object) then the 'next' pointer will be NULL.
If you think in terms of a box-standard array:[tt]

int myArray[1000];[/tt]

In a linked list, the integer at position [3] would contain a pointer to the integer at position [4] and so on until you get to position [999] who's 'next' pointer would be NULL because there's no more integers in the list!

I always like to use the picture of a group of school children crossing the road, in a line all holding hands, when explaining what a linked list is. You have a kid at the start, a kid at the end and loads of 'linked' kids inbetween.

So how do I create a linked list?
I'm going to use the C++ example because it's easier. If you're more familiar with C than C++ then please read the footnotes at the bottom for explanations on any keywords you may not be familiar with.
To create a linked list, you would first create a structure to hold the information. In this case we will use a [tt]class[/tt][sup]3[/sup].

[tt][color blue]class[/color] Child
{
[color blue]public[/color]:[sup]4[/sup]
char name[100];
Child* next;
[color blue]static[/color] Child* first;
};[/tt]

You can see that this [tt]Child[/tt] structure holds a c-style string for the kid's name. We also have the [tt]Child*[/tt] pointer 'next' and the static pointer 'first'. All of these members need initializing so it makes more sense to do this within the structure so that they are automatically initialized when you declare a [tt]Child[/tt] object. We will do this through the use of a constructor[sup]5[/sup].

[tt][color blue]class[/color] Child
{
[color blue]public[/color]:

Child() [color red]// the constructor[sup]5[/sup] member function[/color]
{
strcpy(name,"");
next = NULL;
if (first==NULL)
first = [color blue]this[/color][sup]6[/sup];
else
{
Child* last = GetLast();
last->next = [color blue]this[/color];
}
}

[color red]/* We also need to add a member function which will find the
very last Child in the array and return a pointer to it! - this
function loops through the entire list (using 'first' as a starting
point) until it finds the Child who's 'next' pointer = NULL, therefore
this must be the last Child. */[/color]
Child* GetLast([color blue]void[/color])
{
Child* last = first;
while (last->next != NULL)
last = last->next;
[color blue]return[/color] last;
}

[color red]/* For completeness, we'll add one more member function
to the structure to set the kid's name */[/color]
[color blue]void[/color] SetName(const char* str)
{
strcpy(name,str);
}

char name[100];
Child* next;
[color blue]static[/color] Child* first;
};[/tt]

There are several points to note regarding the above structure. Firstly, we cannot initialize the static 'first' pointer in the constructor (more about this later!). Secondly, we needed to add another member function which loops through the entire array to find the very last [tt]Child[/tt]. You'll see in the constructor function that if 'first' is NULL then we must be the very first [tt]Child[/tt] so we set its value to [tt]this[/tt] object. Otherwise, we must locate the very last [tt]Child[/tt] in the list and set that [tt]Child[/tt]'s 'next' pointer to point to us!
In the constructor, the 'next' pointer is always NULL because we are always the last [tt]Child[/tt] in the list upon creation/declaration.

Now back to that static 'first' pointer. Recall that a [tt]static[/tt] variable is shared amongst all objects of that [tt]class/struct[/tt]. It's value is therefore the same for the second [tt]Child[/tt] as it is for the first and any other [tt]Child[/tt] objects you may create in your program. You cannot initialize a [tt]static[/tt] member of your structure within the structure, you have to do this outside of the structure or any other functions (just like a 'global' variable!). You initialize it like this:

[tt]Child* Child::first = NULL;[/tt][sup]7[/sup]

Putting it into practise
Believe it or not, we're all set to go for a test run! We have created our linked list structure and we're fixing to create our dynamic array of kids crossing the road. Here's the full listing for a simple program:[tt]

[color blue]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

class[/color] Child
{
[color blue]public[/color]:

Child()
{
strcpy(name,"");
next = NULL;
if (first==NULL)
first = [color blue]this[/color];
else
{
Child* last = GetLast();
last->next = [color blue]this[/color];
}
}

Child* GetLast([color blue]void[/color])
{
Child* last = first;
while (last->next != NULL)
last = last->next;
[color blue]return[/color] last;
}

[color blue]void[/color] SetName(const char* str)
{
strcpy(name,str);
}

char name[100];
Child* next;
[color blue]static[/color] Child* first;
};

Child* Child::first = NULL;

[color blue]void[/color] main([color blue]void[/color])
{
[color red]// Create 4 kids and set their names![/color]
Child* a = [color blue]new[/color] Child;
a->SetName("Mike");
Child* b = [color blue]new[/color] Child;
b->SetName("Jenny");
Child* c = [color blue]new[/color] Child;
c->SetName("James");
Child* d = [color blue]new[/color] Child;
d->SetName("Kathy");

[color red]// create a loop to find James and change
// his name to "John"[/color]
Child* kid = Child::first;
while (kid != NULL)
{
if (strcmp(kid->name,"James")==0)
{
kid->SetName("John");
}
kid = kid->next;
}

[color red]// now create another loop to print out
// all the kids in out array![/color]
kid = Child::first;
while (kid != NULL)
{
printf("\n%s\n",kid->name);
kid = kid->next;
}
}[/tt]

Remember that this is a very basic linked list. You can add all kinds of other member functions to make your programming life easier. Suggested functions would be one that returns a reference count (eg. how many kids in our array) and so on.


FOOTNOTES

[sup]1[/sup] The size of the linked list is only limited by the amount of free RAM available to the program.

[sup]2[/sup] Strictly speaking, pointers are not variables!

[sup]3[/sup] The keywords [tt]class[/tt] and [tt]struct[/tt] are practically identical. In fact, [tt]class[/tt] is simply the newer word for a [tt]struct[/tt] but has one very small difference: a [tt]struct[/tt]'s members are declared 'public' by default so there is no need to add the [tt]public[/tt] keyword to a [tt]struct[/tt].

[sup]4[/sup] See footnote [sup]3[/sup] above: because we're using the [tt]class[/tt] keyword instead of a [tt]struct[/tt] we need to expicitly declare the members as being publicly accessible with the [tt]public[/tt] keyword.

[sup]5[/sup] C programmers may be unfamiliar with the concept of constructors. A constructor is a member function of the [tt]class[/tt] or [tt]struct[/tt] that initializes the members of the structure upon declaration. The constructor function name is the same as the name of structure.

[sup]6[/sup] The [tt]this[/tt] keyword is something that C programmers may not have seen before. Basically, when you refer to [tt]this[/tt] from within a structure, you are refering to that particular object.

[sup]7[/sup] The double colon [tt]::[/tt] is called the 'scope resolution operator' - it is kind of like saying "this function/variable belongs to this class/structure".