Introduction
In the previous tutorial, we implemented some of the common functions that can be executed on a linked list. This is a great exercise to gain a deeper understanding of what is really going on. This is because lists are extremely common and a basic building block used in most programs.
Standard implementations of lists exist, so it is not necessary to create your own (but it is very important to know how they work). In this tutorial, we are going to go over the STL (Standard Template Library), which provides the most common list implementation.
Code
The STL provides an implementation of a linked list much like we have been talking about for the past two tutorials, and it is called the forward_list:
#include <iostream>
#include <forward_list>
using namespace std;
void print(forward_list<int> list)
{
for(forward_list<int>::iterator itr = list.begin(); itr != list.end(); itr++)
{
cout << *itr << endl;
}
}
int main()
{
forward_list<int> list;
list.push_front(2);
list.push_front(1);
print(list);
return 0;
}
So, there are quite a few new things in that code sample. Let’s start at the top. The forward_list<int> statement declares a variable, and it tells the computer a couple of things. First, that the class that it would like to create is the forward_list class. The second is that the type of variable that we would like to store within the list is an int. This is great because it means that we can create a list of any type that we want – for example int, double, or any class or struct that we create ourselves.
The next new concept is the idea of an iterator. Iterators are designed to kinda look like pointers, but they help you navigate through a list. The iterator has two main operations that can be performed on it: accessing the value that it is pointing to (*) and advancing to the next element (++). So, in this way it looks like a pointer, since both of those operations would achieve the same goal with a pointer.
Another interesting detail is that there is no add an element to the end of the list (a push_back function). This is an optimization. The forward_list class is designed to be as light-weight as possible and adding support for adding an element at the end doesn’t fit this goal.
This is also a great place to mention the possibility of using the auto keyword for the itr variable:
for(auto itr = list.begin(); itr != list.end(); itr++)
This saves us having to write out the iterator class name, which is fairly complicated (and easy to get incorrect).
The forward_list is an optimization of the more common list:
#include <iostream>
#include <list>
using namespace std;
void print(list<int> list)
{
for(auto itr = list.begin(); itr != list.end(); itr++)
{
cout << *itr << endl;
}
}
int main()
{
list<int> list;
list.push_front(1);
list.push_back(2);
print(list);
return 0;
}
The list class lets you add to the beginning or to the end of the list. It does this because every entry in the linked list contains a pointer to the element after it and to the element before it. This is called a doubly linked list. The forward_list only contains a pointer to the element after it, so it is called a singly linked list. This means that with a list, you can go from the first element to the last one or from the last element to the first one (forwards and backwards).
While on the topic of lists, we should also mention the vector class:
void print(vector<int> vector)
{
for(auto itr = vector.begin(); itr != vector.end(); itr++)
{
cout << *itr << endl;
}
}
int main()
{
vector<int> vector;
vector.push_back(1);
vector.push_back(2);
print(vector);
return 0;
}
Vectors work by storing the data in a dynamic array, rather than a linked list. This class works by having an underlying array that is used to store the data. This array does not have to be the same size as the number of values stored in the vector! The class tracks how many values are in the vector and how large the underlying array is. If a new item is added to the list, one of two things happens. First, if there is enough room in the underlying array to hold the new value, then the new entry is stored in the array. Alternatively, if the underlying array is not large enough, then the array size is doubled and then new element is stored in the now larger array. Vectors have the added benefit of being able to randomly access any element in the array:
void print(vector<int> vector)
{
for(int i = 0; i < vector.size(); i++)
{
cout << vector[i] << endl;
}
}
This makes it look and feel more like an array. Generally, I like this look and feel much better, so I tend to use a vector rather than a list.
Summary
In this tutorial, we went over the forward_list, list and vector classes, which are ways to store data when you do not know how many elements you will have in the list until you are done. Along with these classes, we also talked about iterators which are a way to interact with the elements that they store.
In the next tutorial, we will be going over templates. Templates are way to write a function or a class that works on any data type. It is mechanism that allows the <int> part of the list<int> to work.
If you have any questions or comments about what was covered here, post them to the comments. I watch them closely and will respond and try to help you out.