C++: Linked Lists

Linked lists are another form of standard library "container" (much like vectors), and are standard data structures which focus on storing lists of content. Linked lists come in two main forms - single linked lists, and double linked lists.

Double Linked Lists

Double linked lists (often just referred to as 'lists') are a data structure in which various nodes are linked together. A double linked list has a pointer to the start node, and a pointer to the end node, and each node contains a piece of data (the piece of data), a pointer to the previous node in the list, and a pointer to the next node in the list.

The advantage of this system not being powered by arrays, is that elements can be very easily inserted into the list. Instead of the system present in vectors, where a whole array has the be copied over behind the scenes when inserting data into the middle of the vector, in a linked list a node can simply be created with the desired data and appropriate pointers for its place in the list, and then all that needs to be changed are the pointers around it in the previous and next node in the list - so the node before needs to update its pointer to the next node to point to the inserted node, and the node after needs to do the same with its pointer to the previous node. Similarly, nodes can be easily removed from the list. This can all be a little bit confusing to visualize, so I have created the diagram below which shows the basic structure of a double linked list (in this case, with four elements or "nodes"):

The clear disadvantage to this technique is that you cannot just jump to a given element. If you want to get to data in the middle of the list, you have to traverse the list from either the start or end pointer, riding the "next" or "prev" pointers to get to the desired location. This functionality makes lists much harder to work with than some other containers (e.g. vectors).

To actually utilize double linked lists in a project, you'll need to firstly #include <list>. From here, the syntax is the same as creating a vector, however the list keyword is used instead of the vector keyword. This is because these standard library containers are created using templates, something we'll learn about later in the course.

Just like vectors we can also initialize lists with some starting values by passing one or two optional parameters:

1
2
3

list<int> listOne; //{}
list<int> listTwo(5); //{0, 0, 0, 0, 0}
list<int> listThree{5, 3}; //{3, 3, 3, 3, 3}

Now is where things get a bit more complicated. Say we wanted to change the third "element" in a list (of index "2" if you like) to a different number. This wouldn't be a problem for a vector or array, however with lists things are a little bit more difficult for such a request. You traverse a double linked list by using an iterator of the right type of your list -- you can declare this iterator variable just like you would a normal variable, but with the data-type of list::iterator. We can then set this iterator to the beginning or end of our list to begin traversing using the begin or end member functions as appropriate. As such, we could create a basic list with iterator (initialized to the start of the list), as follows:

1
2

list<int> myList(5); //{0, 0, 0, 0, 0}
list<int>::iterator it = myList.begin();

To change the third element in the list, we can simply get our iterator to follow the pointers up two places, so it'll be at node three. We cannot simply say it += 3 however - we must instead increment or decrement the iterator to change the node it's looking at, or use the advance function which takes as its parameters the iterator name, and the number of places to advance. So to get our iterator, 'it', to target node three we could use the following:

1

advance(it, 2); //Move 2 places up to node 3 (index '2')

At this point, 'it' should point to the data we want to change, and as such we can use the dereference operator to set the actual value. So if we wanted to change the third element in the list to '5':

1

*it = 5;

Similarly, we could use the dereference operator in conjunction with a 'for' loop with some clever conditions to output the contents of our whole list. This functionality can be seen in the following code snippet:

1
2
3
4

for(it = myList.begin(); it != myList.end(); it++)
{
	cout << *it << " ";
}

If the above snippet is put below the process we used to set the third element to '5' earlier, the output should be: 0 0 5 0 0.

There is also an insert member function which can be performed upon double linked lists which inserts a new node with the specified data before the point specified. So to insert a '3' before our current '5' in 'myList', assuming 'it' is set to point at the third element in the list (the '5'), we could write myList.insert(it, 5); (this would make our list "{0, 0, 3, 5, 0, 0}").

Uses for a double linked list might not be immediately obvious, however they are useful in any situation in which data needs to be traversed backwards and forwards sequentially, and also situations where a variable size list is needed. They aren't very efficient at random lookup (since you have to ride through all the pointers to get to a location), however in a number of situations in which the sequence is very important, for example video playback or some sort of queue system, double linked lists are very useful.

Single Linked Lists

Single linked lists are essentially exactly the same as double linked lists, however you can only traverse the list in a forwards direction. This is because each node only has a "next" pointer, and doesn't have a pointer to the previous node. The advantages, disadvantages, use-cases, and complexities, are essentially the same as a double linked list, however these lists will be generally faster and smaller in memory consumption. When I say "faster", I am of course referring to situations in which the sequential movement from the beginning of the list is part of the process - an insert to a single node one from the end of a single linked list would be much faster in a double linked list where the list can be traversed from the end rather than the start.

Single linked lists aren't available as part of the standard library (although are in some STL distributions - don't worry too much about what that means, it's complicated), and as such many single linked list systems are created via custom code on a per-case basis. With the knowledge you have of how both double and single linked list systems work (and the diagram above), it shouldn't be totally alien to you as to how you would create such a system. People usually start with a "node" struct that looks something like the following:

1
2
3
4
5
6
7
8
9

struct node {
	int data;
	node* next;
	node() //Constructor
	{
		next = NULL;
		data = 0;
	}
};

From here, being able to use such a struct and control all the "next" pointers properly can become a bit complex, but if you feel like trying to accomplish it now, either just give it a go, or if you're feeling less confident, a simple Google search for "C++ linked list" will yield some good tutorials and implementation examples which could help you in your path.

As a challenge for this tutorial which you might want to try right now, I'd suggest creating a simple application for managing queues using double linked lists (use your creativity!). It might be worth creating a function which can do some of the traversing of the list for you.