Building Data Structures: Linked Lists, Stacks and Queues
Implement a singly linked list, a stack and a queue from scratch with pointers, smart pointers and templates
std::vector, std::list, std::stack and std::queue. Building them yourself once is how you truly learn how data is stored and accessed, and why each container has the performance it does. In this topic you assemble three classic structures out of a single building block - a node - and see exactly where each one is the right tool.
- build a singly linked list from nodes joined by
std::unique_ptr, - implement a stack (last-in, first-out) and a queue (first-in, first-out) on top of that list,
- make each structure generic with a class template so it holds any type,
- reason about the trade-offs and pick the right structure for a job.
This builds on earlier topics in this course: Smart Pointers, Function and Class Templates, Move Semantics and the Rule of Five. You do not need those in front of you, but we will lean on them.
The node: one link in a chain
A node is a small struct that stores one value plus a pointer to the next node. A whole list is just nodes chained together; the last node points at nothing (nullptr), which marks the end.
The classic C way is a raw Node*. In modern C++ we let each node own the next one with a std::unique_ptr. Ownership is exclusive - each node owns exactly the tail behind it - and when the head is destroyed the destructors run down the chain and free every node automatically. No manual delete, no leaks.
#include <memory>
struct Node {
int value; // the payload
std::unique_ptr<Node> next; // owns the rest of the chain
Node(int v) : value(v), next(nullptr) {}
};Because next is a unique_ptr, the node is move-only: you cannot copy a chain by accident, and there is exactly one owner of each link. That is precisely the guarantee a list wants.