A Beginner's Guide to the Linked List

What is a linked list?

A linked list is basically a collection of objects, stored in a list form. In some ways, is can be likened to an array, but the method used to store the list are very different, and so the list has different advantages and disadvantages to those of the array. There is already a linked list programmed, available for you to use as part of the Microsoft Foundation Classes (or MFC). This is a very good implementation of the list, so I will cover how it should be used. Firstly, though, I will discuss the workings of a linked list, its advantages and its disadvantages.

How does it work?

A linked list works around the idea of pointers, so it is wise to already have a sound knowledge of this subject. The basic principle is that to each element that you want to store in the list, you attach either one or two additional variables. These point to the surrounding elements in the list, specifically the next one, and usually the previous one as well. Here is the shape of the list in a diagram form, showing elements with both a Next and a Previous pointer attached:

As this diagram shows, from each element in the list, we can obtain a pointer to the next, and the previous elements. We can also identify the start and the end of the list because either the pPrev or pNext element will be NULL (0).

By manipulating the pNext and pPrev values, elements can be added, removed, and traversed easily. This layout gives us the following advantages:

• The list can be traversed from start to end quickly
• Elements (or nodes, as they are often known) can be added at the beginning and end quickly.
• Elements can be inserted at any point quickly.

However, the main disadvantage is that because you can only get from one node to the next or previous nodes in the list, it can be time consuming to find a particular element, because this would consist of searching the whole list.

Now you know the basics of how a list works, I’ll show you how to use the built in list functionality that is found in MFC.

Using the CList class

The CList class provides an implementation of the linked list that is well suited for most tasks, and which can be customised should you need to. Unlike many of the classes in MFC, CList is a template class, which enables it work with anything you want to make a list of, including integers, strings, classes etc. Let’s make a list of integers:

CList<int, int> MyListOfNumbers;

Now, the <int, int> bit tells the compiler what we want to make a list of. The first template argument (the first int) tells the compiler that we want a list of ints, and the second tells the compiler that we want to pass the elements to the CList as ints. Generally these two parameters will be the same unless you wish to pass and receive references to your data. If we want to make a list of CStrings, we could use the following, which would avoid extraneous copying:

CList<CString, CString&> MyListOfStrings;

This would not make too much difference for a CString, but most other classes or types will benefit. The list class can also store pointers to objects, as in this example:

CList<CMyObject *, CMyObject *> MyListOfObjects;

All these examples set up the list, and prepare it for storing elements. So how do we start adding elements to the list? Throughout this article, I will use the example of a list of integers.

Adding elements

Adding elements is dead easy, and there are two ways of doing this: add an element to the start, and adding an element at the end. First, I’ll demonstrate how to place an element at the start of the list. To do this, we use the AddHead function, which takes one parameter: the element you want to add. As with all the functions in the CList class, you must use the same type of element as you specified when you created the list, OR if it’s a class, then anything derived from that class as well. Although it’s not recommended, you can store a list of absolutely anything using a list of void *’s, which can store pointers to any type of variable.

Anyway, lets say we have a number, 15, that we want to add to the start of our list of numbers:

ListOfNumbers.AddHead(15);

How easy was that? And, it’s nearly the same if you want to add the number 15 to the end of the list:

ListOfNumbers.AddTail(15);

Now that we have the data in our list, how do we traverse it, and retrieve the information? Read on.

Traversing the list

The best way to traverse a list is to use a while loop. The CList class uses a type of variable called a POSITION to store whereabouts you are in the list. It is not necessary to worry about the details of this variable, but just to know that it stores our position in the list at any time, and can also be used to bookmark certain points in the list. In actual fact, the POSITION variable is how MFC adds the pNext and pPrev variables to your data.

To get the position of the first element in the list, we use the function GetHeadPosition(). This can be used as follows:

POSITION pos = MyList.GetHeadPosition();

To get the position of the last element in the list, we use the function GetTailPosition(), as follows:

POSITION pos = MyList.GetTailPosition(); 

As you can see, both functions take no parameters and return a POSITION variable. Now that we have the position variable, we can pass it to the functions GetNext, and GetPrev. These each take a POSITION, return the element pointed at by it, and set the POSITION variable to either the next or the previous element. If you use the GetNext function and are at the end of the list, or use the GetPrev function and are at the beginning of the list, your POSITION variable will be set to NULL to let you know that you can’t traverse any further because you are at the end of the list. This is convenient because it means that we can say ‘while the POSITION is NOT NULL, continue to traverse the list’. In actual code, this can be done as follows:

POSITION pos = MyIntList.GetHeadPosition();

while (pos)
{
	int Number = MyIntList.GetNext(pos);
	// do something with the number
}

// end of the list has been reached, so control continues to here.

So, continuing our theme on numbers, we could add all of the elements of the linked list together as follows:

POSITION pos = MyIntList.GetHeadPosition();
int Total;

while (pos)
{
	int Number = MyIntList.GetNext(pos);
	Total = Total + Number;
}

// use the CString class to make a string using the number, a bit like printf:
CString Str;
Str.Format(“Total of the numbers = %d”, Total);
AfxMessageBox(Str);

We can also get the head, and tail, of a list using the GetHead and GetTail functions. These return the actual elements at the head or tail of the list rather than a POSITION that represents them, and are used as shown here:

FirstNumber = MyIntList.GetHead();
LastNumber = MyIntList.GetTail();

FirstNumber = MyIntList.GetHead();
LastNumber = MyIntList.GetTail();

One final way that we can obtain an element is to use the GetAt function. This is similar to the GetNext and GetPrev functions, but get the item at the position specified without altering the POSITION variable passed to it. It is used to obtain an element at a given position with moving the position either forwards or backwards, in other words. It can be used as follows:

// MyBookmark is a POSITION variable kept from earilier:
int Number = MyIntList.GetAt(MyBookmark);

Finding Positions

Sometimes you need the POSITION variable from an item in the list. We can reverse the process, and find the POSITION of an item given the element itself using the Find function. This function takes an element, and a POSITION to start with, and will return the POSITION of the element that you passed in to it. The POSITION that you pass to the function (the startAfter variable) is used to tell the list where to start searching for the element, so if there are more than one you can tell the list to start a certain distance into the list. This means you can skip several elements, and get just the one that you wanted. If you just wanted to start searching from the start of the list, you can set the startAfter value to NULL, or just not passing it at all.

Here’s an example of the Find function:

POSITION MyBookmark = MyIntList.Find(15);

Now let’s say you wanted to find the second occurrence of the number 15 in the list. You can pass the MyBookmark position to the Find function as the startAfter value, as follows:

POSITION SecondFifteen = MyIntList.Find(15, MyBookmark);

This will return the second occurrence of the value 15 in the list. This system works very well, but what would you do if you wanted to find the fifth element in the list, not knowing its POSITION or value? The simple solution is to use the FindIndex function. This returns the POSITION of an element from its index. It is important to note, however, that this index is zero-based, which means the computer counts the first element in the list as being element number 0, not 1. Therefore, if you wanted to find the tenth element in the list, you would have to pass 9 as the index to the FindIndex function.

Here’s an example of how to use the FindIndex function:

POSITION pos = MyIntList.FindIndex(3);

This finds the fourth element in the list – the zero-based index coming into play again.

Inserting Elements

Elements can be inserted at any given position in the list. There are two functions that the CList class provides to do this; the InsertBefore function and the InsertAfter functions. These take a POSITION as an argument, and an element to add before or after that position. This can be useful if you are trying to keep the list in sorted order, but you must be careful that you pass your new element to the correct function.

Both functions take the POSITION of the element that already exists, followed by the element you wish to add, as parameters. The POSITION value can come from any of the GetHeadPosition, GetTailPosition, GetNext, GetPrev, Find, or FindIndex functions. Going back to our number list example, let’s say you wanted to add a new number (15) into the list as the third element. Here’s how you would do it:

MyIntList.InsertBefore(MyIntList.FindIndex(2), 15);
// ~ OR ~
MyIntList.InsertAfter(MyIntList.FindIndex(1), 15);

Don’t forget the zero based index in the FindIndex function – this is why we have to refer to element number 3 as element 2, and element number 2 as element 1 when calling this function.

Removing Elements

Once we have the elements in the list, it may be necessary to remove them at a later point in the program. This is particularly necessary if you have a list of pointers, because they will need to be deleted before the program ends. The CList class facilitates this extremely adequately, providing four functions which aid in the removed of elements from the list.

The most obvious of the removal functions are the RemoveHead and RemoveTail. These do exactly what they say; they remove the head or tail node from the list. What can be useful about these functions is that they actually return the element, so you can obtain the element from the list at the same time as removing it from the list should you wish to do so. Here is example which will free all the memory occupied by a list of pointers:

while (!MyPointerList.IsEmpty())
	delete MyPointerList.RemoveHead();

Obviously you can just remove the head or tail without actually receiving the element that was removed as follows:

MyList.RemoveTail();

This would be the same were we to use the RemoveHead function instead.

The third function provided by the CList class is the RemoveAt function. This removes the element at a given position in the list. This function is useful if you want to remove a specific element. It can be used in combination with the Find and FindIndex functions to help you in removing specific elements. It simply takes a POSITION as its parameter, removes the element, and returns it to you. It can be used as follows:

MyIntList.RemoveAt(MyBookmarkedPosition);

If you wanted to remove the first occurrence of the number 15 in the list, you would use the following:

MyIntList.RemoveAt(MyIntList.Find(15));

There are many possibilities for this function. Don’t forget, however, that if you have a list of pointers, you must free the memory that they are holding when you have done with them as the Remove functions don’t free the memory for you.

The final method of removing elements is the most brutal; the RemoveAll function. It takes no parameters, and is used to remove all the elements from the list. This function is not suitable for lists of pointers because you will no longer have a method to free the memory allocated to the elements that were previously in the list. Instead, use the method for freeing the memory in the list that I have outlined above.

The SetAt function

This function can be extremely useful – it is used to replace an element at a given position. It takes two parameters, the POSITION to replace, and a new element to insert there. It works as follows:

MyIntList.SetAt(MyBookmarkedPosition, 23);

This would replace whatever value was stored at the position held by the variable MyBookmarkedPosition with the number 23. The example below, again based on the list of numbers, demonstrates how all occurrences of the number 15 could be replaced with the number 25:

POSITION pos = NULL;
while (pos = MyIntList.Find(15))
	MyIntList.SetAt(pos, 25);

Status information:

Once you have your list prepared and ready, you may, at a later date, want to know how many items are in the list. There are two ‘status’ functions that are designed to help. The first, IsEmpty, tells us whether the list contains any information. It returns either TRUE or FALSE. It can be used in many situations, one of which is to determine if you have finished freeing the information stored in the list. For example:

while (!MyObjectPointerList.IsEmpty())
{
	CMyObject *head = MyObjectPointerList.RemoveHead();
	delete head;	// free the memory allocated to the element in the list
}

This can be written in a more shorthand form as:

while (!MyObjectPointersList.IsEmpty())
	delete MyObjectPointerList.RemoveHead();

The second function that gives us status information about the list is the GetCount function. This will return a value describing how many items are in the list at any time. Returning once again to our integer list, assuming that it is sorted, we can use this function to find the median of the numbers stored in the list. The median is the mathematical term for the middle number in a series, or, if the series has an odd number of elements, the mean of the middle two numbers. Here is some code that will do this for our list:

int nItems = MyIntList.GetCount();
int nMedian = 0;

if (nItems % 2 == 1) // if there is an odd number of items in the list
{
	nItems = (nItems + 1) / 2; // get the central item
	nMedian = MyIntList.GetAt(MyIntList.FindIndex(nItems));
}
else
{
	nItems = nItems / 2;

	// get the middle two items:
	nMedian = MyIntList.GetAt(MyIntList.FindIndex(nItems));
	nMedian = nMedian + MyIntList.GetAt(MyIntList.FindIndex(nItems + 1));

	// now average the two:
	nMedian = nMedian / 2;
}

That makes for some interesting code, so you might want to have a look at it yourself, perhaps in the debugger.

Summary

Here is an outline of what was covered in the article:

1. A linked list is used to store collections of items (elements) that are arbitrary in number in one place.
2. A linked list provides fast insertion and removal capabilities, but is slow for random access.
3. The MFC CList class is a linked list system that has already been written for you.
4. In the CList class, we can use the AddHead and AddTail functions to add elements at the start and end of the list.
5. A POSITION variable is used to store a place in a linked list.
6. The GetNext and GetPrev functions allow us to traverse the list.
7. The GetAt function returns the element at a given POSITION in the list.
8. The InsertBefore and InsertAfter functions can be used to insert an element at any given place in the list.
9. The Find and FindIndex functions can be used to get the POSITION of an element given its ZERO-BASED index in the list or the element itself.
10. The RemoveHead and RemoveTail functions are used to remove the first or last element from the list.
11. The RemoveAt function is used to remove the element at any given position.
12. The RemoveAll function is used to remove all elements from a list.
13. The IsEmpty and GetCount functions are used to determine how many items are in the list.
14. The SetAt function replaces elements at a given POSITION.

The demonstration program uses a console based app that supports MFC. I have done this so that the complexities of handling windows messages and so forth does not obstruct your understanding of the basic code fundamentals. It is written without many of the features of C++ in order to put the emphasis on the linked list, and the CList class.

That’s it for the linked list!