Linked Lists using std::forward_list

This lesson provides an in-depth exploration of std::forward_list, covering creation, management, and advanced list operations
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
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated

Similar to arrays like std::vector and std::array, a linked list lets us store a sequential collection of objects.

Unlike arrays, linked lists store their objects in a more free-form memory layout, that causes them to have different performance characteristics. We covered these characteristics, and their implications, in more detail in the previous lesson:

The std::forward_list Type

The C++ standard library provides a ready-made way for us to create and manage linked lists, using the std::forward_list type.

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

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 node in the linked list had a link (or pointer) to 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. Below, we create a forward list that stores int objects:

#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 };
}

Forward List Size

Unlike many other containers, std::forward_list does not keep track of its size - that is, how many objects it currently contains. To determine its size, we need to traverse the entire list and keep track of how many links we had to follow.

The std::distance() function can do this for us. We pass it the iterators returned from the begin() and end() methods respectively:

#include <forward_list>
#include <iostream>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };
  std::cout << "Size: " << std::distance(
    MyList.begin(), MyList.end());
}
Size: 5

Accessing Elements in a Linked List

The first element in a linked list can be accessed by calling the front() method:

#include <forward_list>
#include <iostream>

int main() {
  std::forward_list MyList{1, 2, 3, 4, 5};
  std::cout << "Front: " << MyList.front();
}
Front: 1

To access elements in arbitrary positions, we need to traverse the links to that position.

We can do this using iterators and std::next(). Below, we generate an iterator to the third position by traversing two steps from the begin() iterator:

#include <forward_list>
#include <iostream>

int main() {
  std::forward_list MyList{1, 2, 3, 4, 5};
  auto Third{std::next(MyList.begin(), 2)};
  std::cout << "Third: " << *Third;
}
Third: 3

As we covered in our earlier lessons, linked lists are not designed to support this access pattern. If we require fast access to our objects by index, we should likely be using an array instead of a linked list.

Backward Traversal

As we covered in the introduction, std::forward_list is a singly linked list. Each node only includes a link to the next node. As such, it only supports traversal in one direction direction. An implication of this is that we cannot pass a negative offset to std::next().

Below, we attempt to access the last element in our std::forward_list by traversing backward from the end() iterator:

#include <forward_list>

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

With containers that support bidirectional traversal, this would work. But, std::forward_list doesn’t. If we compile our project in debug mode, we’ll likely get run-time checks that alert us of the error:

error: negative advance of non-bidirectional iterator
example.exe (process 39308) exited with code 3.

If we require backward traversal, we can use a doubly linked list, such as std::list.

Range-Based For Loops

The std::forward_list, container supports the range-based for-loop syntax, letting us easily iterate over the entire collection:

#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,

Adding Items to Forward Lists

The std::forward_list provides two methods for adding objects to the start of our list: 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 {/*...*/} int main() { std::forward_list<Character> MyList; Character Wizard { "Roderick" }; MyList.push_front(Wizard); std::cout << "Front: " << MyList.front().Name; }
Front: Roderick

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 {/*...*/} int main() { std::forward_list<Character> MyList; MyList.emplace_front("Roderick"); std::cout << "Front: " << MyList.front().Name; }
Front: Roderick

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 at any position using Iterators

Given the performance characteristics of forward lists, the most efficient way to add items to the list is at the front. Inserting an object at any other position requires us to traverse the list to find that position.

However, if we’ve already traversed the list and generated an iterator to the position we want to use, we can insert or emplace an object there 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.

insert_after()

The first argument to insert_after() is an iterator pointing at the node we want our new object to be inserted after.

The second argument is the value to insert. Below, we generate an iterator to the third element using std::next(), and then insert a new object after it (that is, in the fourth position):

#include <iostream>
#include <forward_list>

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

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

emplace_after()

As before, if we can construct our object directly into the linked list, that will be more performant than constructing it outside, and then moving it in.

The emplace_after() method lets us do this. We pass an iterator as the first argument.

Any additional arguments we provide will be forwarded to an appropriate constructor of the underlying type our list is storing:

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

struct Character {/*...*/} int main() { std::forward_list<Character> MyList; MyList.emplace_front("Roderick", 50); MyList.emplace_after( MyList.begin(), "Anna", 45); for (Character& C : MyList) { std::cout << std::format( "{}, Level {}\n", C.Name, C.Level); } }
Roderick, Level 50
Anna, Level 45

Removing and Filtering Items from Forward Lists

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

Removing the First Object 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,

Removing Objects by Value using remove()

We can remove all elements that are equal to a provided value, 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,

Algorithm Requirements

When using algorithms on containers of a certain type, some of those algorithms may have additional requirements of that type.

For example, the remove() algorithm removes any objects that pass an equality check. Therefore, the type we’re storing in our container must support that action.

Specifically, the type must support the equality operator, ==, where the right operand is an object of that same type.

The built-in int type supports the == operator, so our earlier example works as expected.

For more details on the requirements of any algorithm, we should check the documentation. Standard library references are available from many online sources, such as cppreference.com

We introduced how to implement capabilities like == to our custom types in our introductory lesson on operator overloading:

Removing objects based on a predicate using remove_if()

The remove_if() method on the linked list allows us to pass a predicate - a function that receives an object and returns a boolean. The remove_if() algorithm will pass every object in our collection to our predicate one at a time, and remove any for which our predicate returns true:

Below, we use this to remove all the negative numbers from our linked list:

#include <iostream>
#include <forward_list>

bool isNegative(int x) { return x < 0; }

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

  MyList.remove_if(isNegative);

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

Before 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 number of elements that were removed from the list:

#include <forward_list>
#include <iostream>

bool isNegative(int x) { return x < 0; }

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

  std::cout << "Removed "
    << MyList.remove_if(isNegative)
    << " Objects";
}
Removed 2 Objects

Removing all objects using clear()

The clear() method simply removes all the objects from the linked list:

#include <forward_list>
#include <iostream>

int main() {
  std::forward_list MyList{1, 2, 3, 4, 5};
  std::cout << "Size: " << std::distance(
    MyList.begin(), MyList.end());

  MyList.clear();

  std::cout << "\nNew Size: " << std::distance(
    MyList.begin(), MyList.end());
}
Size: 5
New Size: 0

Removing objects using iterators with erase_after()

Similar to emplace_after() and insert_after(), the erase_after() method 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,

Erasing Multiple Objects using Iterators

The erase_after() accepts a second argument. By passing an iterator here, we can specify a range of objects to remove. Objects from the first iterator until the second iterator will be erased, excluding those objects.

Below, we remove everything after the first element until the end of the container, leaving us with only one object. Remember. end() is a "past-the-end" iterator, meaning the last element of the collection is included in this range:

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

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

  std::cout << "List Contents: ";
  for (int x : MyList) {
    std::cout << x << ", ";
  }
}
List Contents: 1,

Below, we erase everything from position 2 to position 5, excluding those objects:

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

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

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

Sorting a std::forward_list

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

This is another example of an algorithm that has underlying requirements. Specifically, the data type in our list needs to define what it means for their objects to be sorted. This is done by implementing the < operator.

Customizing the Sort Behaviour

The sort() method allows us to pass a function to it, to customize how our objects are sorted. This function will receive two objects from our list and will return true if the first object should come before the second object.

Using this overload of the sort() method also means the algorithm no longer needs to use the < operator, meaning it is compatible with types that don’t implement it.

Here, we sort our Characters by level:

#include <iostream>
#include <forward_list>

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

bool isHigherLevel(
  const Character& A, const Character& B) {
    return A.Level > B.Level;
}

int main() {
  std::forward_list MyList {
      Character { "Anna", 20 },
      Character { "Roderick", 10 },
      Character { "Bruce", 15 },
  };

  MyList.sort(isHigherLevel);

  for (auto x : MyList) {
    std::cout
      << x.Level << " - " << x.Name << '\n';
  }
}
20 - Anna
15 - Bruce
10 - Roderick

Summary

In this lesson, we have explored std::forward_list, learning how to create, manage, and manipulate singly-linked lists. The key topics we learned included:

  • The differences between arrays (like std::vector and std::array) and linked lists (std::forward_list), especially in terms of memory layout.
  • Creating forward lists using the <forward_list> header.
  • Using std::distance() to determine the size of a std::forward_list, as it does not track its size natively.
  • Accessing the first element with front() and arbitrary elements using iterators and std::next().
  • Limitations of std::forward_list in backward traversal and the inability to use negative offsets with std::next().
  • Implementing range-based for loops to iterate over std::forward_list.
  • Adding elements to a forward list using push_front() and emplace_front().
  • Inserting and emplacing elements at specific positions with insert_after() and emplace_after().
  • Various methods of removing items from the list, including pop_front(), remove(), remove_if(), clear(), and erase_after().
  • Sorting std::forward_list using the sort() method and customizing the sort behavior with a comparison function.

Was this lesson useful?

Next Lesson

Hashing and std::hash

This lesson provides an in-depth look at hashing in C++, including std::hash, collision strategies, and usage in hash-based containers.
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated
A computer programmer
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
Arrays and Linked Lists
Next Lesson

Hashing and std::hash

This lesson provides an in-depth look at hashing in C++, including std::hash, collision strategies, and usage in hash-based containers.
Abstract art representing computer programming
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved