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

Learn how to use the C++ std::forward_list container to create linked lists.
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

DreamShaper_v7_fantasy_female_pirate_Sidecut_hair_swords_black_1.jpg
Ryan McCombe
Ryan McCombe
Posted

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:

Forward Lists, Singly Linked Lists, Doubly Linked Lists

There are several different implementations of linked lists, with different capabilities. The most basic form of a linked list is what we described in the previous lesson. In that example, each item in the linked list had a link to only the next item in the list.

This is sometimes referred to as a singly linked list, or a forward list, as the list can only be traversed in one direction - forward.

We could expand this concept such that each item in the list also includes a link to the previous item. This would create a doubly linked list, where we can traverse the list in either direction - forward or back.

The C++ standard library also includes an implementation of doubly linked lists, which it calls std::list. This lesson focuses on the singly linked list, std::forward_list, but everything we cover also applies to std::list.

Creating Forward Lists

Forward lists are available by including <forward_list>

#include <forward_list>

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

#include <forward_list>

int main() {
  std::forward_list<int> MyList;
}

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):

#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
}

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

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };

  std::cout << MyList.front();
}
1

Iterating Forward Lists

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

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 2 3 4 5

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

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:

#include <iostream>
#include <string>
#include <forward_list>

struct Character {
  Character(std::string Name):
    Name {Name}
  {};
  std::string Name;
};

int main() {
  std::forward_list<Character> MyList;
  Character Wizard { "Gandalf" };
  MyList.push_front(Wizard);

  std::cout << MyList.front().Name;
}
Gandalf

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:

#include <iostream>
#include <string>
#include <forward_list>

struct Character {
  Character(std::string Name):
    Name {Name}
  {};
  std::string Name;
};

int main() {
  std::forward_list<Character> MyList;
  MyList.emplace_front("Gandalf");

  std::cout << MyList.front().Name;
}
Gandalf

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():

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 0, 0, 0, 0, 0 };
  MyList.emplace_after(MyList.before_begin(), 1);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 0 0 0 0 0

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

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 0, 0, 0, 0, 0 };
  MyList.emplace_after(MyList.begin(), 1);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
0 1 0 0 0 0

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:

#include <iostream>
#include <iterator>
#include <forward_list>

int main() {
  std::forward_list MyList { 0, 0, 0, 0, 0 };
  auto Iterator { std::next(MyList.before_begin(), 3) };
  MyList.emplace_after(Iterator, 1);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
0 0 0 1 0 0

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:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  MyList.pop_front();

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
2 3 4 5

remove

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

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  MyList.remove(3);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 2 4 5

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:

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:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  
  auto isEven {
    [](int Number) { return Number % 2 == 0; }
  };
  
  MyList.remove_if(isEven);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 3 5

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:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  
  auto isEven {
    [](int Number) { return Number % 2 == 0; }
  };

  std::cout << MyList.remove_if(isEven)
            << " numbers were removed.";
}
2 numbers were removed.

clear

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  MyList.clear();
  MyList.emplace_front(7);
  MyList.emplace_front(6);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
6 7

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:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  MyList.erase_after(MyList.begin());

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 3 4 5

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

#include <iostream>
#include <iterator>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  auto Second = std::next(MyList.before_begin(), 2);
  MyList.erase_after(Second);

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 2 4 5

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:

#include <iostream>
#include <iterator>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  auto Second = std::next(MyList.before_begin(), 2);
  MyList.erase_after(Second, MyList.end());

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 2

Sorting Linked Lists

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

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 3, 2, 5, 1, 4 };
  MyList.sort();

  for (int x : MyList) {
    std::cout << x << " ";
  }
}
1 2 3 4 5

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:

#include <iostream>
#include <forward_list>

struct Character {
    std::string Name;
    int Level;
};

int main() {
  std::forward_list MyList { 
      Character { "Gandalf", 20 },
      Character { "Frodo", 10 },
      Character { "Legolas", 15 },
  };
  
  auto ByLevel {
      [](const Character& A, const Character& B){
          return A.Level > B.Level;
      }
  };
  
  MyList.sort(ByLevel);

  for (auto x : MyList) {
    std::cout << x.Level << " - " << x.Name << "\n";
  }
}
20 - Gandalf
15 - Legolas
10 - Frodo

Was this lesson useful?

Ryan McCombe
Ryan McCombe
Posted
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Arrays and Linked Lists
7a.jpg
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access!

This course includes:

  • 106 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

Optional Values, std::optional and Monadic Operations

A guide to handling optional data in C++ using the std::optional container
3D Concept Art
Contact|Privacy Policy|Terms of Use
Copyright © 2023 - All Rights Reserved