std::forward_list - Create Linked Lists in C++

C++ programmers are always searching for ways to optimize data structures and boost performance. One powerful container that deserves attention is the linked list.

The C++ standard library provides a ready-made way for us to create linked lists, which it refers to as forward lists.

In this article, we'll explore the basics of the C++ std::forward_list container and discuss its key features, advantages, and use cases.

Whether you're a beginner or an experienced programmer, this guide will help you master the std::forward_list and take your C++ coding skills to the next level.

The theory of linked lists, how they work, and how they compare to arrays, is covered here:

Linked Lists vs Arrays

An introduction to linked lists, why we would want to use them, and how they compare to arrays

Creating Forward Lists

Forward lists are available by including <forward_list>

1#include <forward_list>
2

We can create a forward list by specifying the type of items it will contain:

1#include <forward_list>
2
3int main() {
4  std::forward_list<int> MyList;
5}
6

If we are providing items at the same time we are creating the list, we can omit the type and let the compiler deduce it. This is using class template argument deduction (CTAD):

1#include <forward_list>
2
3int main() {
4  std::forward_list MyList { 1, 2, 3, 4, 5 };
5}
6

The first element in a linked list can be accessed by calling front:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6
7  std::cout << MyList.front();
8}
9

11
2

Iterating Forward Lists

Forward lists support iterators, so we can traverse them using range-based for loops:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6
7  for (int x : MyList) {
8    std::cout << x << " ";
9  }
10}
11

11 2 3 4 5
2

Iterators and range-based for loops are covered in more detail here:

C++ Iterators and Range Based For Loops

Learn how to iterate over containers in C++ using code that can work regardless of the specific type of container

Adding Items to the Start of Forward Lists

Given the performance characteristics of forward lists, the most efficient way to add items to the list is at the front. std::forward_list provides two methods for doing this: push_front and emplace_front

The push_front method takes an existing object that has already been constructed, and moves or copies it to the front of our linked list:

1#include <iostream>
2#include <string>
3#include <forward_list>
4
5struct Character {
6  Character(std::string Name):
7    Name {Name}
8  {};
9  std::string Name;
10};
11
12int main() {
13  std::forward_list<Character> MyList;
14  Character Wizard { "Gandalf" };
15  MyList.push_front(Wizard);
16
17  std::cout << MyList.front().Name;
18}
19

1Gandalf
2

The emplace_front method constructs a new object in place. The arguments that are provided to emplace_front are forwarded to the constructor of that type:

1#include <iostream>
2#include <string>
3#include <forward_list>
4
5struct Character {
6  Character(std::string Name):
7    Name {Name}
8  {};
9  std::string Name;
10};
11
12int main() {
13  std::forward_list<Character> MyList;
14  MyList.emplace_front("Gandalf");
15
16  std::cout << MyList.front().Name;
17}
18

1Gandalf
2

Because emplace_front eliminates the need to copy or move an object, it is more performant, so should be preferred over push_front where possible.

Adding Items Anywhere in Forward Lists

It is possible to add items to any position in a forward list, using insert_after or emplace_after.

Similar to our previous section, insert_after will move or copy an existing object into our list, whilst emplace_after will construct it in place.

However, the first argument that these two methods require is a description of where in the list to insert our new object. Given we lack the ability to directly access random positions in the list, we need to traverse to the correct position first.

As such, the first argument to insert_after and emplace_after is an iterator, after which our new addition will be inserted or constructed.

We can replicate the behavior of insert_front and emplace_front by passing the iterator returned from before_begin():

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 0, 0, 0, 0, 0 };
6  MyList.emplace_after(MyList.before_begin(), 1);
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

11 0 0 0 0 0
2

We can insert an object into the second position by passing the iterator returned from begin():

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 0, 0, 0, 0, 0 };
6  MyList.emplace_after(MyList.begin(), 1);
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

10 1 0 0 0 0
2

We can traverse our list to get an iterator for any position using std::next, available by including <iterator>

std::next accepts two arguments - an iterator from which to begin traversal, and a number representing how many steps to traverse.

Here, we see how we can use std::next to get an iterator to the 3rd element, and then use emplace_after to construct a new object after that position:

1#include <iostream>
2#include <iterator>
3#include <forward_list>
4
5int main() {
6  std::forward_list MyList { 0, 0, 0, 0, 0 };
7  auto Iterator { std::next(MyList.before_begin(), 3) };
8  MyList.emplace_after(Iterator, 1);
9
10  for (int x : MyList) {
11    std::cout << x << " ";
12  }
13}
14

10 0 0 1 0 0
2

Removing and Filtering Items from Forward Lists

There are several ways we can remove items from our linked lists:

pop_front

We can remove the first element in a linked list using pop_front:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.pop_front();
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

12 3 4 5
2

remove

We can remove all elements that are equal to a provided object, using the remove method:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.remove(3);
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

11 2 4 5
2

Note, for this to work, the object type stored in our list must define what it means for two objects of its type to be equal. That means the type must implement the equality operator, ==

The built-in int type support the == operator, so our earlier example works as expected. But not every type implements ==. This is particularly likely of any custom types we create.

Refer to the following lesson for an introduction on how we can define operators for our own custom types:

C++ Operator Overloading

Learn how we can enhance our classes and structs by letting them define their our own operators.

remove_if

The remove_if method on linked list allows us to pass a predicate. Objects will be removed if that predicate returns true when passed the object:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  
7  auto isEven {
8    [](int Number) { return Number % 2 == 0; }
9  };
10  
11  MyList.remove_if(isEven);
12
13  for (int x : MyList) {
14    std::cout << x << " ";
15  }
16}
17

11 3 5
2

Prior to C++20, remove and remove_if do not return anything (ie, their return type is void)

Since C++20, they now return a number representing the quantity of elements that were removed from the list:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  
7  auto isEven {
8    [](int Number) { return Number % 2 == 0; }
9  };
10
11  std::cout << MyList.remove_if(isEven)
12            << " numbers were removed.";
13}
14

12 numbers were removed.
2

clear

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.clear();
7  MyList.emplace_front(7);
8  MyList.emplace_front(6);
9
10  for (int x : MyList) {
11    std::cout << x << " ";
12  }
13}
14

16 7
2

erase_after

Similar to emplace_after and insert_after, erase_after interacts with iterators, allowing us to remove elements from anywhere in the list.

Here, we remove the second element, by erasing the element after the begin() iterator:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.erase_after(MyList.begin());
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

11 3 4 5
2

Here, we use std::next to create an iterator for the 2nd element. We pass it to erase_after to remove the third element:

1#include <iostream>
2#include <iterator>
3#include <forward_list>
4
5int main() {
6  std::forward_list MyList { 1, 2, 3, 4, 5 };
7  auto Second = std::next(MyList.before_begin(), 2);
8  MyList.erase_after(Second);
9
10  for (int x : MyList) {
11    std::cout << x << " ";
12  }
13}
14

11 2 4 5
2

Finally, erase_after accepts a second argument. By passing an iterator here, we can specify a range of objects to remove. Here, we remove everything from the third element until the end:

1#include <iostream>
2#include <iterator>
3#include <forward_list>
4
5int main() {
6  std::forward_list MyList { 1, 2, 3, 4, 5 };
7  auto Second = std::next(MyList.before_begin(), 2);
8  MyList.erase_after(Second, MyList.end());
9
10  for (int x : MyList) {
11    std::cout << x << " ";
12  }
13}
14

11 2
2

Sorting Linked Lists

Linked lists can be sorted in-place using the sort method:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 3, 2, 5, 1, 4 };
6  MyList.sort();
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}
12

11 2 3 4 5
2

The data type in our list needs to define what it means to be sorted. This is done by implementing the < operator.

Alternatively, the sort method allows us to pass a function to it, to define the sorting behavior. This function will accept two objects from our list and will return true if the first object should come before the second object.

Here, we sort our Characters by level:

1#include <iostream>
2#include <forward_list>
3
4struct Character {
5    std::string Name;
6    int Level;
7};
8
9int main() {
10  std::forward_list MyList { 
11      Character { "Gandalf", 20 },
12      Character { "Frodo", 10 },
13      Character { "Legolas", 15 },
14  };
15  
16  auto ByLevel {
17      [](const Character& A, const Character& B){
18          return A.Level > B.Level;
19      }
20  };
21  
22  MyList.sort(ByLevel);
23
24  for (auto x : MyList) {
25    std::cout << x.Level << " - " << x.Name << "\n";
26  }
27}
28

120 - Gandalf
215 - Legolas
310 - Frodo
4