C++ Lists

A list is a type of sequence container, along with STL arrays, vectors and deques, which is provided as part of the Standard Template Library (STL).

A list can hold multiple values of the same type, similarly to arrays, vectors and deques. There are additional similarities with vectors and deques in their flexibility of adding and removing values. They also allow items to be easily added and removed from the front, as well as the back as with deques, and the number of values to be stored in a list doesn’t need to be specified when it is defined either. The size can dynamically grow and shrink as required.

Lists allow constant time insert and erase operations anywhere within the sequence. The elements within can be stored in different and unrelated locations in memory. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

Compared with the other sequence containers, arrays, vectors and deques, lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained, and therefore also in algorithms that make intensive use of these, like sorting algorithms. The drawback however, relative to these other sequence containers is that they lack direct access to the elements within by their position.

The example below creates a list of strings called names, adds four names using the ‘push_back’ and ‘push_front’ methods, then, with a range based ‘for’ loop, displays the names in the console. The ‘push_back’ method adds values to the back of the list, whilst the ‘push_front’ method adds values to the front. In order to make use of lists, the ‘list’ header file needs to be included.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

for (auto name: names)
{
    cout << name << endl;
}

The output from this will be as follows.

Alan
Fred
Bob
George

Notice the order of the names, as the ‘push_front’ method was used for adding ‘Fred’ and ‘Alan’, they are at the front of the list and not the back.

An ordinary ‘for’ loop can also be used in conjunction with an iterator to loop through a list, in a similar way as with STL arrays.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Iterator declaration.
list<string>::iterator i;

// Loop through the list with the iterator.
for (i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

Here, the ‘begin’ and ‘end’ methods are used to denote the start and end of the list. The ‘end’ method does not point to the last item in the list, but instead points to just after the last item, which is why ‘not equal to’ is used in the loop, rather than ‘less than or equal to’. Notice that when displaying the values in the list, within the loop, an asterisk precedes the iterator, in order to refer to the actual values within the list. This example will display the names on a separate line as before.

It isn’t absolutely necessary to declare the iterator prior to the loop, it can be done as part of the loop.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the list with the iterator.
for (list<string>::iterator i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

To further simplify this, the ‘auto’ keyword can be used, which forces the compiler to determine that an iterator is to be used.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the list with the iterator.
for (auto i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

To ensure that the values within the list are not altered within the loop, the ‘begin’ and ‘end’ methods can be replaced by ‘cbegin’ and ‘cend’.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the list with the iterator.
for (auto i = names.cbegin(); i != names.cend(); ++i)
{
    cout << *i << endl;
}

If required, it is also possible to loop through the list in reverse by replacing the ‘begin’ and ‘end’ methods with ‘rbegin’ and ‘rend’.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the list with the iterator.
for (auto i = names.rbegin(); i != names.rend(); ++i)
{
    cout << *i << endl;
}

In order to remove a value from a list, there are a couple of different ways, depending on which value needs to be deleted. If the first or last value in the list needs to be removed, then the ‘pop_front’ and ‘pop_back’ methods can be used respectively.

names.pop_front();
names.pop_back();

If a specific value needs to be removed, the ‘remove’ method can be utilised.

names.remove("George");

In order to return the first and last items in the list, without removing them, the 'front' and 'back' methods can be used.

list<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

cout << names.front() << endl;
cout << names.back() << endl;

This will display the following in the console.

Alan
George

If it is necessary to have the items in the list in order, the 'sort' method can be used to achieve this.

names.sort();