List & Forward List

Introduction

In this tutorial, we will delve into two fundamental container types in the C++ Standard Template Library (STL): std::list and std::forward_list. These containers are part of the sequence container family and provide dynamic arrays that can grow or shrink as needed. The primary difference between them is their underlying data structure: std::list uses a doubly linked list, while std::forward_list uses a singly linked list. Understanding these differences will help you choose the right container for your specific needs.

Core Content

Doubly Linked List: std::list

A std::list is a sequence container that allows constant time insertions and deletions of elements. It provides bidirectional iterators, meaning you can traverse the list in both forward and backward directions. This makes it highly efficient for operations that require frequent modifications to the middle of the list.

Basic Operations

Here are some basic operations you can perform on a std::list:

• Insertion: You can insert elements at any position using iterators.
• Deletion: Elements can be removed from any position.
• Traversal: You can traverse the list in both directions using iterators.

1#include <iostream>
2#include <list>
3 
4int main() {
5  std::list<int> myList = {1, 2, 3};
6 
7  // Insert an element at the end
8  myList.push_back(4);
9 
10  // Insert an element at the beginning
11  myList.push_front(0);
12 
13  // Remove the last element
14  myList.pop_back();
15 
16  // Remove the first element
17  myList.pop_front();
18 
19  // Print all elements
20  for (int num : myList) {
21      std::cout << num << " ";
22  }
23 
24  return 0;
25}

1 2 3

Common Operations

• Splice: Transfers elements from one list to another.
• Sort: Sorts the elements in the list.
• Unique: Removes duplicate consecutive elements.

1#include <iostream>
2#include <list>
3#include <algorithm>
4 
5int main() {
6  std::list<int> myList1 = {3, 2, 1};
7  std::list<int> myList2 = {6, 5, 4};
8 
9  // Splice elements from myList1 to myList2
10  myList1.splice(myList1.begin(), myList2);
11 
12  // Sort the list
13  myList1.sort();
14 
15  // Remove duplicates
16  myList1.unique();
17 
18  // Print all elements
19  for (int num : myList1) {
20      std::cout << num << " ";
21  }
22 
23  return 0;
24}

1 2 3 4 5 6

Singly Linked List: std::forward_list

A std::forward_list is a sequence container that allows constant time insertions and deletions of elements. It provides only forward iterators, meaning you can traverse the list in one direction from beginning to end. This makes it more memory-efficient than std::list because each node contains only one pointer instead of two.

Basic Operations

Here are some basic operations you can perform on a std::forward_list:

• Insertion: You can insert elements at any position using iterators.
• Deletion: Elements can be removed from any position.
• Traversal: You can traverse the list in forward direction only.

1#include <iostream>
2#include <forward_list>
3 
4int main() {
5  std::forward_list<int> myList = {1, 2, 3};
6 
7  // Insert an element at the end
8  myList.push_front(4);
9 
10  // Insert an element at the beginning
11  myList.push_front(0);
12 
13  // Remove the first element
14  myList.pop_front();
15 
16  // Print all elements
17  for (int num : myList) {
18      std::cout << num << " ";
19  }
20 
21  return 0;
22}

1 2 3 4

Common Operations

• Splice: Transfers elements from one list to another.
• Sort: Sorts the elements in the list.
• Unique: Removes duplicate consecutive elements.

1#include <iostream>
2#include <forward_list>
3#include <algorithm>
4 
5int main() {
6  std::forward_list<int> myList1 = {3, 2, 1};
7  std::forward_list<int> myList2 = {6, 5, 4};
8 
9  // Splice elements from myList1 to myList2
10  myList1.splice_after(myList1.before_begin(), myList2);
11 
12  // Sort the list
13  myList1.sort();
14 
15  // Remove duplicates
16  myList1.unique();
17 
18  // Print all elements
19  for (int num : myList1) {
20      std::cout << num << " ";
21  }
22 
23  return 0;
24}

1 2 3 4 5 6

Differences Between std::list and std::forward_list

Practical Example

Let's create a practical example that demonstrates the use of both std::list and std::forward_list. We'll implement a simple program that merges two lists, sorts them, removes duplicates, and prints the results.

1#include <iostream>
2#include <list>
3#include <forward_list>
4#include <algorithm>
5 
6int main() {
7  std::list<int> list1 = {3, 2, 1};
8  std::list<int> list2 = {6, 5, 4};
9 
10  // Merge lists
11  list1.merge(list2);
12 
13  // Sort the list
14  list1.sort();
15 
16  // Remove duplicates
17  list1.unique();
18 
19  // Print all elements
20  std::cout << "Merged and sorted list: ";
21  for (int num : list1) {
22      std::cout << num << " ";
23  }
24  std::cout << std::endl;
25 
26  std::forward_list<int> forwardList1 = {3, 2, 1};
27  std::forward_list<int> forwardList2 = {6, 5, 4};
28 
29  // Merge lists
30  forwardList1.merge(forwardList2);
31 
32  // Sort the list
33  forwardList1.sort();
34 
35  // Remove duplicates
36  forwardList1.unique();
37 
38  // Print all elements
39  std::cout << "Merged and sorted forward list: ";
40  for (int num : forwardList1) {
41      std::cout << num << " ";
42  }
43  std::cout << std::endl;
44 
45  return 0;
46}

Merged and sorted list: 1 2 3 4 5 6 
Merged and sorted forward list: 1 2 3 4 5 6

Summary

• std::list is a doubly linked list that supports bidirectional traversal.
• std::forward_list is a singly linked list that supports only forward traversal.
• Both containers support constant time insertions and deletions.
• Use std::list when you need bidirectional access and frequent modifications to the middle of the list.
• Use std::forward_list when memory efficiency is critical and reverse traversal is not required.

What's Next?

In the next tutorial, we will explore another sequence container called std::deque, which stands for "double-ended queue." It provides dynamic arrays that can grow or shrink from both ends. This container is highly efficient for operations that require frequent insertions and deletions at both ends of the list.

Stay tuned for more advanced topics in C++ STL!