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¹ like a standard array. Consider this array of integers:

int   myArray[1000];

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 (struct or class) 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² 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:

int   myArray[1000];

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 class³.

class Child
{
public:⁴
    char           name[100];
    Child*         next;
    static Child*  first;
};

You can see that this Child structure holds a c-style string for the kid's name. We also have the Child* 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 Child object. We will do this through the use of a constructor⁵.

class Child
{
public:

    Child()  // the constructor⁵ member function
    {
        strcpy(name,"");
        next = NULL;
        if (first==NULL)
            first = this⁶;
        else
        {
            Child* last = GetLast();
            last->next = this;
        }
    }

    /* 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. */
    Child* GetLast(void)
    {
        Child* last = first;
        while (last->next != NULL)
            last = last->next;
        return last;
    }

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

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

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 Child. You'll see in the constructor function that if 'first' is NULL then we must be the very first Child so we set its value to this object. Otherwise, we must locate the very last Child in the list and set that Child's 'next' pointer to point to us!
In the constructor, the 'next' pointer is always NULL because we are always the last Child in the list upon creation/declaration.

Now back to that static 'first' pointer. Recall that a static variable is shared amongst all objects of that class/struct. It's value is therefore the same for the second Child as it is for the first and any other Child objects you may create in your program. You cannot initialize a static 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:

Child* Child::first = NULL;⁷

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:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

class Child
{
public:

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

    Child* GetLast(void)
    {
        Child* last = first;
        while (last->next != NULL)
            last = last->next;
        return last;
    }

    void SetName(const char* str)
    {
        strcpy(name,str);
    }

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

Child* Child::first = NULL;

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

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

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

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

¹ The size of the linked list is only limited by the amount of free RAM available to the program.

² Strictly speaking, pointers are not variables!

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

⁴ See footnote ³ above: because we're using the class keyword instead of a struct we need to expicitly declare the members as being publicly accessible with the public keyword.

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

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

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

Back to C++: Microsoft FAQ Index
Back to C++: Microsoft Forum
My FAQ Archive

Email This FAQ To A Friend

My Archive

My FAQ Archive