C++17 - Implementing a singly linked list with smart pointers
Posted on February 22, 2019 by Paul
In this tutorial, I will show you how to implement a singly linked list data structure in C++17 with smart pointers. This is also useful as an exercise in learning about how you can use smart pointers instead of raw pointers to manage the memory of the list elements.
A singly linked list is a collection of nodes (elements), in which every node contains a data field and a link to the next node. The first node of a singly linked list is usually named head or root. The last element of the list is usually named tail and his next field links to nothing.
An interesting property of the singly linked list is that, in order to visit a certain node, you will need to pass through all the previous list nodes until the searched one. For example, if you want to print the third element of a singly linked list, you will need to start at the list head and pass through the first and second nodes. In other words, you can’t have random access to the singly linked list elements, like you can for example with an array. If you want to read more about the linked lists theory check the books recommended at the end of the article.
For the purpose of this article, we are going to implement a few of the linked list possible operations: insertion, deletion and traversal.
Disclaimer: In C++, in almost all cases, you should consider using a std::vector instead of a list. If you really need a singly linked list, use std::forward_list.
For simplicity, we are going to store integers in the data field of our singly linked list:
1 #include <iostream>
2 #include <memory>
3
4 struct Node {
5 int data;
6 std::unique_ptr<Node> next;
7 Node(int data) : data{data}, next{nullptr} {}
8 };
9
10 // ...As mentioned in the article introduction, we are going to use smart pointers to manage the allocation/deallocation of a list node, see std::unique_ptr for a quick remainder.
Now, that we have the Node struct defined, let’s manually create a few nodes and link them one to another. It is interesting to observe how the smart pointer destroys a node once the smart pointer is out of the scope where it was created. For this, we will temporarily add a dummy destructor to Node that will be removed in the final code:
1 // ...
2
3 struct Node {
4 // ...
5 ~Node() {
6 std::cout << "Destroy node with data: " << data << '\n';
7 }
8 };
9
10 int main() {
11 auto n0{std::make_unique<Node>(0)};
12
13 auto n1{std::make_unique<Node>(1)};
14 n1->next = std::move(n0);
15
16 auto n2{std::make_unique<Node>(2)};
17 n2->next = std::move(n1);
18 }Please note the way in which we’ve manually linked the nodes: first we create node n0, next we create node n1 and link this to n0 and so on … For the remainder of the article, for simplicity, I will use the term node, technically n0 is a unique pointer to a Node object.
This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_00.cpp -o SLList
2 ~ $ ./SLList
3 Destroy node with data: 2
4 Destroy node with data: 1
5 Destroy node with data: 0
6 ~ $Basically, at the end of the main function the first node in the list, the head node, which in our manually assembled list is n2 goes out of scope, at which point the unique smart pointer that owns the node object calls his destructor. Because of the way the nodes are linked, when you manually delete or when the head node goes out of scope all the nodes in the list are recursively deleted! What do you think will happen if you create a large list of nodes, e.g. a few millions of nodes, and you delete the header or the header goes out of scope ? Because of the recursive destruction of the subsequent nodes there is a good chance that you will get a stack overflow error.
On Linux and macOS you can check the default stack size for an executable with:
1 ulimit -sThis is what I see on a macOS machine:
1 ~ $ ulimit -s
2 8192
3 ~ $which means that the default stack size for an executable on my machine is 8 MB.
Due to the above, we don’t want the user to be able to manually erase the head of the list. We will create a List struct that will safely manage the list nodes creation and destruction:
1 // ...
2
3 struct List {
4 List() : head{nullptr} {};
5
6 void push(int data) {/* ... */}
7 void pop() {/* ... */}
8 ~List() {/* ... */}
9
10 private:
11 std::unique_ptr<Node> head;
12 };
13
14 // ...Let’s implement first the push method. What we want is to create a new node object and push it to the head of the list. As a side note, in a singly linked list you really want to insert/remove elements to the head of the list for performance reasons, this is an O(1) operation. Technically, it is possible to insert a new node at some position in the list or at the end, but because of the way we traverse the list, by going through all previous elements, this is an O(n) operation that we usually want to avoid.
Here is a possible implementation for the push method:
1 // ...
2
3 struct List {
4 List() : head{nullptr} {};
5
6 void push(int data) {
7 auto temp{std::make_unique<Node>(data)};
8 if(head) {
9 temp->next = std::move(head);
10 head = std::move(temp);
11
12 } else {
13 head = std::move(temp);
14 }
15 }
16
17 // ...
18 };
19
20 // ...At this point, we can test the push method implementation:
1 #include <iostream>
2 #include <memory>
3
4 // ...
5
6 int main() {
7 List list;
8
9 list.push(0);
10 list.push(1);
11 list.push(2);
12 list.push(3);
13 }This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_01.cpp -o SLList
2 ~ $ ./SLList
3 Destroy node with data: 3
4 Destroy node with data: 2
5 Destroy node with data: 1
6 Destroy node with data: 0
7 ~ $If you feel adventurous, you can try to trigger a stack overflow due to the recursive nodes destruction. First, remove the dummy destructor from the Node struct, we don’t need a destructor function for this, and also we don’t want to print the Destroy node with data: x message every time a node is deleted. Try this main function:
1 // ...
2
3 int main() {
4 List list;
5
6 for(int i = 0; i < 10'000'000; ++i) {
7 list.push(i);
8 }
9
10 std::cout << "Last line of the program. After this, the list nodes will be recursively destroyed!\n";
11 }This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_02.cpp -o SLList
2 ~ $ ./SLList
3 Last line of the program. After this, the list nodes will be recursively destroyed!
4 Segmentation fault: 11
5 ~ $Obviously, this is a serious bug in our code. As a side note, if you reduce the numbers of elements to something like 10000 nodes, the program ends without a stack overflow.
Let’s remove the above limitations by creating a clean function member that when called will iteratively go through all the list nodes and remove them one by one:
1 // ...
2
3 struct List {
4 // ...
5
6 void clean() {
7 while(head) {
8 head = std::move(head->next);
9 }
10 }
11
12 ~List() {
13 clean();
14 }
15
16 private:
17 std::unique_ptr<Node> head;
18 };
19
20
21 int main() {
22 List list;
23
24 for(int i = 0; i < 10'000'000; ++i) {
25 list.push(i);
26 }
27
28 std::cout << "Last line of the program. After this, the list nodes will be iteratively destroyed!\n";
29 }Thanks to encyclopedist from Reddit for suggesting a great simplification for the clean function.
If you run the above code, with a 10 millions nodes list, the program should have a normal termination without overflowing the stack:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_03.cpp -o SLList
2 ~ $ ./SLList
3 Last line of the program. After this, the list nodes will be iteratively destroyed!
4 ~ $At this point, it may be useful to overload the ostream operator in order to be able to print the list elements. First we’ll make the operator function a friend of the List class and than we can implement the new function:
1 // ...
2
3 struct List {
4 // ...
5
6 friend std::ostream& operator<<(std::ostream &os, const List &list);
7
8 // ...
9 };
10
11 std::ostream& operator<<(std::ostream &os, const List &list) {
12 Node *head = list.head.get();
13 while(head) {
14 os << head->data << ' ';
15 head = head->next.get();
16 }
17 return os;
18 }
19
20 // ...Let’s try the new ostream operator for a list:
1 // ...
2
3 int main() {
4 List list;
5
6 std::cout << "The list is empty: " << list << '\n';
7
8 for(int i = 0; i < 10; ++i) {
9 list.push(i);
10 }
11
12 std::cout << "The list with 10 nodes: " << list << '\n';
13
14 list.clean();
15
16 std::cout << "The list after clean(): " << list << '\n';
17 }This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_04.cpp -o SLList
2 ~ $ ./SLList
3 The list is empty:
4 The list with 10 nodes: 9 8 7 6 5 4 3 2 1 0
5 The list after clean():
6 ~ $Now, we can implement the pop member function:
1 // ...
2
3 struct List {
4 List() : head{nullptr} {};
5
6 // ...
7
8 void pop() {
9 if(head == nullptr) {
10 return;
11 }
12
13 std::unique_ptr<Node> temp = std::move(head);
14 head = std::move(temp->next);
15 }
16
17 // ...
18 };
19
20 // ...Let’s do some extra tests:
1 // ...
2
3 int main() {
4 List list;
5
6 list.push(-10);
7 std::cout << list << '\n';
8
9 list.pop();
10 std::cout << list << '\n';
11
12 for(int i = 0; i < 10; ++i) {
13 list.push(i);
14 }
15 std::cout << list << '\n';
16
17 list.pop();
18 list.pop();
19 list.pop();
20 std::cout << list << '\n';
21
22 list.push(-20);
23 list.push(-30);
24 std::cout << list << '\n';
25
26 list.clean();
27 std::cout << list << '\n';
28
29 list.push(-1);
30 list.push(-2);
31 std::cout << list << '\n';
32 }This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_05.cpp -o SLList
2 ~ $ ./SLList
3 -10
4
5 9 8 7 6 5 4 3 2 1 0
6 6 5 4 3 2 1 0
7 -30 -20 6 5 4 3 2 1 0
8
9 -2 -1
10 ~ $At this point, I think it is instructive to compare the running time of our singly linked list implementation, for filling the list with numbers, with the std::forward_list from STL. I did a simple test: push 10 millions numbers, delete the list elements, push another 10 elements. For simplicity, I’ve used the shell time command to measure the running time for both implementations.
Here is the test for our singly linked list implementation:
1 // ...
2
3 int main() {
4 List list;
5
6 // Push 10 millions elements
7 for(int i = 0; i < 10'000'000; ++i) {
8 list.push(i);
9 }
10
11 // Clean the list
12 list.clean();
13
14 // Push another 10 elements
15 for(int i = 0; i < 10; ++i) {
16 list.push(i);
17 }
18 }and the complete code for the std::forward_list test:
1 #include <iostream>
2 #include <forward_list>
3
4 int main() {
5 std::forward_list<int> list;
6
7 // Push 10 millions elements
8 for(int i = 0; i < 10'000'000; ++i) {
9 list.emplace_front(i);
10 }
11
12 // Clean the list
13 list.clear();
14
15 // Push another 10 elements
16 for(int i = 0; i < 10; ++i) {
17 list.emplace_front(i);
18 }
19 }On my machine, the running time is comparable. Here is the result of running 5 tests (left is our implementation, right is the STL):
Please note that for both cases I’ve used the -O2 optimization option.
For completeness, after a suggestion from https://www.reddit.com/user/DoesNotLikeBroccoli, I’ve included code for copy and move constructors for the List struct:
1 // ...
2
3 struct List {
4 // ...
5
6 List(const List &list) {
7 Node *root = list.head.get();
8
9 std::unique_ptr<Node> new_head{nullptr};
10 Node *pnew_head{nullptr};
11 while(root) {
12 auto temp{std::make_unique<Node>(root->data)};
13 if(new_head == nullptr) {
14 new_head = std::move(temp);
15 pnew_head = new_head.get();
16 } else {
17 pnew_head->next = std::move(temp);
18 pnew_head = pnew_head->next.get();
19 }
20 root = root->next.get();
21 }
22 head = std::move(new_head);
23 }
24
25
26 List(List &&list) {
27 head = std::move(list.head);
28 }
29
30 ~List() {
31 clean();
32 }
33
34 // ...
35 };
36 // ...Let’s also add a reverse member function that will reverse the list:
1 // ...
2
3 struct List {
4 // ...
5
6 void reverse() {
7 List tmp;
8 Node *root = head.get();
9 while(root) {
10 tmp.push(root->data);
11 root = root->next.get();
12 }
13 clean();
14 head = std::move(tmp.head);
15 }
16
17
18 ~List() {
19 clean();
20 }
21
22 // ...
23 };
24 // ...Let’s try the new code:
1 // ...
2
3 int main() {
4 List list;
5
6 for(int i = 0; i < 10; ++i) {
7 list.push(i);
8 }
9 std::cout << list << '\n';
10
11 list.clean();
12 std::cout << list << '\n';
13
14 list.push(-1);
15 list.push(-2);
16 list.push(-3);
17 list.push(-4);
18 list.push(-5);
19 std::cout << list << '\n';
20
21 List list2 = list;
22 std::cout << list2 << '\n';
23
24 List list3 = std::move(list);
25 std::cout << list << '\n';
26 std::cout << list3 << '\n';
27
28 list3.reverse();
29 std::cout << list3 << '\n';
30 }This is what I see on my machine if I build and run the above code:
1 ~ $ clang++ -std=c++17 -Wall -pedantic -O2 SLList_06.cpp -o SLList
2 ~ $ ./SLList
3 9 8 7 6 5 4 3 2 1 0
4
5 -5 -4 -3 -2 -1
6 -5 -4 -3 -2 -1
7
8 -5 -4 -3 -2 -1
9 -1 -2 -3 -4 -5
10 ~ $You can find the complete source code on the GitHub repository for this article.
A good introduction to data structures and algorithms is A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow.
If you are interested to learn more about modern C++ I would recommend reading A tour of C++ by Bjarne Stroustrup.
