I wrote a C++ Linked List with Smart Pointers
Smart pointers seem nice. Maybe we should use more of those. Maybe even in Leetcode problems, like when implementing a linked list.
That seemed like a nice idea. So I wrote this little Node class.
struct Node
{
int val;
std::unique_ptr<Node> next;
Node(int val, std::unique_ptr<Node> next)
{
this->val = val;
this->next = std::move(next);
}
~Node()
{
std::cout << "Destructor called for node with value: " << val;
if (next != nullptr)
{
std::cout << "; next node has value: " << next->val;
}
else
{
std::cout << "; next node is null";
}
std::cout << std::endl;
}
};
Each Node owns its subsequent Node. This poses no problem during construction or usage. But the whole point of using smart pointers is for automatic cleanup at destruction time. There, you'll find a problem.
Total Destruction
Only the root node's unique_ptr lives on the stack. When it goes out of scope, the root node needs to be deleted. Its default destructor destroys its next Node before it can be destroyed. The next Node itself owns another Node, which must be destroyed first.
Each of these destruction operations occupies a memory instruction on a stack. You can think of this as a recursive call, where to destroy root, you first have to destroy its next Node, to delete which you first have to destroy its next Node, and so on. It's Nodes all the way down.
This works fine when you have a smaller number of nodes (the main code is at the bottom of this post):
$ g++ ll-with-smart-ptr.cpp && ./a.out 10
Last node has value: 10
Destructor called for node with value: 0; next node has value: 1
Destructor called for node with value: 1; next node has value: 2
Destructor called for node with value: 2; next node has value: 3
Destructor called for node with value: 3; next node has value: 4
Destructor called for node with value: 4; next node has value: 5
Destructor called for node with value: 5; next node has value: 6
Destructor called for node with value: 6; next node has value: 7
Destructor called for node with value: 7; next node has value: 8
Destructor called for node with value: 8; next node has value: 9
Destructor called for node with value: 9; next node has value: 10
Destructor called for node with value: 10; next node is null
When you have too many nodes, the number of deletion operations exceeds the capacity of the stack that holds all the instructions. This results in a segementation fault.
$ g++ ll-with-smart-ptr.cpp && ./a.out 60000
Last node has value: 60000
Destructor called for node with value: 0; next node has value: 1
Destructor called for node with value: 1; next node has value: 2
Destructor called for node with value: 2; next node has value: 3
Destructor called for node with value: 3; next node has value: 4
...
Destructor called for node with value: 52343; next node has value: 52344
Destructor called for node with value: 52344; next node has value: 52345
Destructor called for node with value: 52345; next node has value: 52346
Destructor called for node with value: 52346; next node has value: 52347
Destructor called for node with value: 52347; next node has value: 52348
Segmentation fault (core dumped)
The fix
The default behavior of the destructor is unsuitable for recursive data structures like linked lists. The workaround is to have a non-recursive, or iterative, deletion routine. This can be done by modifying the Node class's destructor as follows:
~Node()
{
auto cur = std::move(next); // (1)
if (cur != nullptr)
std::cout << "Current node value: " << val << "; cur contains node with value: " << cur->val << std::endl;
while (cur)
{
cur = std::move(cur->next); // (2)
if (cur != nullptr)
std::cout << "Current node value: " << val << "; cur contains node with value: " << cur->val << std::endl;
}
}
(1) This sets next to nullptr. next will not need to be deallocated once the destructor body ends.
(2) This goes through the linked list and invalidates all the next pointers. They are all moved into the cur variable, which is then overwritten. Overwriting a unique_ptr calls release() on the old pointer before assigning the new pointer. If you did not include this loop, all the next pointers would continue to hold heap-allocated objects, resulting in memory leaks.
$ g++ ll-with-smart-ptr.cpp && ./a.out 10
Last node has value: 10
Current node value: 0; cur contains node with value: 1
Current node value: 0; cur contains node with value: 2
Current node value: 0; cur contains node with value: 3
Current node value: 0; cur contains node with value: 4
Current node value: 0; cur contains node with value: 5
Current node value: 0; cur contains node with value: 6
Current node value: 0; cur contains node with value: 7
Current node value: 0; cur contains node with value: 8
Current node value: 0; cur contains node with value: 9
Current node value: 0; cur contains node with value: 10
Essentially, the root Node's destructor takes care of deleting all the Nodes of the linked list. The destructor is only called once.
Now the code runs without segmentation faults, even for larger lists.
$ g++ ll-with-smart-ptr.cpp && ./a.out 1000000
Last node has value: 1000000
Current node value: 0; cur contains node with value: 1
Current node value: 0; cur contains node with value: 2
...
Current node value: 0; cur contains node with value: 999998
Current node value: 0; cur contains node with value: 999999
Current node value: 0; cur contains node with value: 1000000
Complete code
#include <memory>
#include <iostream>
struct Node
{
int val;
std::unique_ptr<Node> next;
Node(int val, std::unique_ptr<Node> next)
{
this->val = val;
this->next = std::move(next);
}
#ifndef SOLVE_THE_PROBLEM
~Node()
{
std::cout << "Destructor called for node with value: " << val;
if (next != nullptr)
{
std::cout << "; next node has value: " << next->val;
}
else
{
std::cout << "; next node is null";
}
std::cout << std::endl;
}
#else // SOLVE_THE_PROBLEM
~Node()
{
auto cur = std::move(next); // (1)
if (cur != nullptr)
{
std::cout << "Current node value: " << val << "; cur contains node with value: " << cur->val << std::endl;
}
while (cur)
{
cur = std::move(cur->next); // (2)
if (cur != nullptr)
{
std::cout << "Current node value: " << val << "; cur contains node with value: " << cur->val << std::endl;
}
}
}
#endif
};
int main(int argc, char **argv)
{
int NUM_NODES;
if (argc == 2)
{
NUM_NODES = std::stoi(argv[1]);
}
else
{
throw std::runtime_error("Need one argument - number of nodes to create as an integer.");
}
auto root = std::make_unique<Node>(0, nullptr);
auto cur = root.get();
for (int i = 1; i <= NUM_NODES; ++i)
{
cur->next = std::make_unique<Node>(i, nullptr);
cur = cur->next.get();
}
for (auto cur = root.get(); cur != nullptr; cur = cur->next.get())
{
if (cur->next == nullptr)
{
std::cout << "Last node has value: " << cur->val << std::endl;
}
}
return 0;
}
// Build and run:
// $ g++ ll-with-smart-ptr.cpp && ./a.out 10000
// Output:
// Last node has value: 10000
// Destructor called for node with value: 0; next node has value: 1
// Destructor called for node with value: 1; next node has value: 2
// ...
// Destructor called for node with value: 9999; next node has value: 10000
// Destructor called for node with value: 10000; next node is null
// $ g++ -D SOLVE_THE_PROBLEM ll-with-smart-ptr.cpp && ./a.out 1000000
// Output:
// Last node has value: 1000000
// Current node value: 0; cur contains node with value: 1
// Current node value: 0; cur contains node with value: 2
// ...
// Current node value: 0; cur contains node with value: 999998
// Current node value: 0; cur contains node with value: 999999
// Current node value: 0; cur contains node with value: 1000000