C++ singly linked list with unique_ptr
Own each node with a unique_ptr, push at the front, reverse the list, and let destructors do the cleanup.
#include <iostream>
#include <memory>
#include <utility>
struct Node {
int value;
std::unique_ptr<Node> next;
Node(int v, std::unique_ptr<Node> n) : value(v), next(std::move(n)) {}
};
class List {
public:
void push_front(int value) { head_ = std::make_unique<Node>(value, std::move(head_)); }
void reverse() {
std::unique_ptr<Node> previous;
while (head_) {
std::unique_ptr<Node> next = std::move(head_->next);
head_->next = std::move(previous);
previous = std::move(head_);
head_ = std::move(next);
}
head_ = std::move(previous);
}
void print() const {
for (const Node* n = head_.get(); n != nullptr; n = n->next.get()) {
std::cout << n->value << (n->next ? " -> " : "\n");
}
}
private:
std::unique_ptr<Node> head_;
};
int main() {
List list;
for (int v = 4; v >= 1; --v) {
list.push_front(v);
}
list.print();
list.reverse();
list.print();
}1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1
Explanation
A linked list in modern C++ can avoid manual new and delete. Each node owns the next node through a std::unique_ptr, so the whole chain is destroyed automatically when the head goes out of scope. push_front creates a node whose next is the old head, using std::move to transfer ownership.
Reversing walks the list once and relinks each node to its predecessor. With unique_ptr you must move ownership carefully: take the next pointer before overwriting it. Destroying a very long list recursively (each destructor destroys the next) can overflow the stack, so a robust class destroys it in a loop.
Explore the dry run
#include <iostream>#include <memory>#include <utility> struct Node { int value; std::unique_ptr<Node> next; Node(int v, std::unique_ptr<Node> n) : value(v), next(std::move(n)) {}}; class List { public: void push_front(int value) { head_ = std::make_unique<Node>(value, std::move(head_)); } void reverse() { std::unique_ptr<Node> previous; while (head_) { std::unique_ptr<Node> next = std::move(head_->next); head_->next = std::move(previous); previous = std::move(head_); head_ = std::move(next); } head_ = std::move(previous); } void print() const { for (const Node* n = head_.get(); n != nullptr; n = n->next.get()) { std::cout << n->value << (n->next ? " -> " : "\n"); } } private: std::unique_ptr<Node> head_;}; int main() { List list; for (int v = 4; v >= 1; --v) { list.push_front(v); } list.print(); list.reverse(); list.print();}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The new node takes ownership of the old chain, then becomes the head. | — | — | |
| Save the rest of the list before changing the link. | — | — | |
| Point the current node backwards. | — | — | |
| At the end previous owns the new first node. | — | — | |
| Pushing 4, 3, 2, 1 at the front gives 1 -> 2 -> 3 -> 4. | — | 1 -> 2 -> 3 -> 4 | |
| The same nodes are relinked in the opposite order. | — | 1 -> 2 -> 3 -> 4 | |
| After reversal the list reads 4 -> 3 -> 2 -> 1. | — | 1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1 |
Cost and common mistakes
push_front O(1); reverse O(n); print O(n).
- After std::move the source unique_ptr is null. Read anything you need from it before moving.
- A list of a million nodes can overflow the stack when the chain of destructors runs. Write a destructor that unlinks nodes in a loop for production code.
- std::list and std::forward_list already provide linked lists. A hand-written one is for learning.
Try it yourself
Why does print use raw pointers?
Reveal answer and reasoning
It only reads the list and does not take ownership, so non-owning raw pointers (from get()) are the right tool.