C++ linked list: write one, then use std::list

A C++ linked list is a chain of nodes: each node holds a value and a pointer, the next node’s address, and the list keeps a pointer to the first. Write one with a Node struct, or use the standard library’s std::list or std::forward_list. Adding or removing where you stand is cheap; reaching the tenth node means walking past nine.

The simplest example, three nodes holding 3, 7 and 9, in a whole program:

#include <iostream>

struct Node {
    int value;
    Node* next;
};

int main() {
    Node* head = new Node{9, nullptr};  // 9
    head = new Node{7, head};           // 7 -> 9
    head = new Node{3, head};           // 3 -> 7 -> 9

    for (Node* n = head; n != nullptr; n = n->next) {
        std::cout << n->value << " -> ";
    }
    std::cout << "nullptr\n";           // 3 -> 7 -> 9 -> nullptr

    while (head != nullptr) {           // free every node
        Node* next = head->next;
        delete head;
        head = next;
    }
}

It printed:

3 -> 7 -> 9 -> nullptr

new creates a node and returns its address, and nullptr, the null pointer, marks the end of the chain. Each new node points at the old first one, so the list is built back to front. Every new needs a delete, and the last loop gives each node its own.

The samples are C++17 (Since When’s C++17 table gives the first GCC, Clang and MSVC releases of its features), built with MSVC 19.44, Clang 19.1 (MSVC STL), GCC 16.2 and Clang 23.1 (libc++). Every sample that runs printed the same on all four.

How do you write a singly linked list in C++?

Put the head pointer in a class: a LinkedList keeps head_, a pointer to the first node, and its member functions add a node at the front, then print and count the nodes by walking the chain. Singly linked means each node points one way only, to the next.

struct Node {
    int value;
    Node* next;
};

class LinkedList {
public:
    // ...
    void push_front(int value) {
        head_ = new Node{value, head_};
    }

    void print() const {
        for (const Node* n = head_; n != nullptr; n = n->next) {
            std::cout << n->value << " -> ";
        }
        std::cout << "nullptr\n";
    }

    std::size_t size() const {
        std::size_t count = 0;
        for (const Node* n = head_; n != nullptr; n = n->next) {
            ++count;
        }
        return count;
    }

private:
    Node* head_ = nullptr;
};

int main() {
    LinkedList numbers;
    numbers.push_front(9);
    numbers.push_front(7);
    numbers.push_front(3);
    numbers.print();                        // 3 -> 7 -> 9 -> nullptr
    std::cout << numbers.size() << '\n';    // 3
}

All four printed 3 -> 7 -> 9 -> nullptr, then 3. push_front is one line: the new node points at the old head, then becomes the head, and no other node moves. The // ... stands for the destructor and the copy rules, shown in the section on freeing the list.

How do you insert and delete a node?

Change one or two pointers once you stand on the node before the spot. Inserting after a node sets the new node’s next and redirects the old node’s, as the drawing of 5 going in after 3 shows; deleting the node after it redirects one pointer and frees the node. Getting to that node is the walk, here find:

Node* find(int value) {             // the walk
    for (Node* n = head_; n != nullptr; n = n->next) {
        if (n->value == value) {
            return n;
        }
    }
    return nullptr;
}

void insert_after(Node* position, int value) {
    position->next = new Node{value, position->next};
}

bool remove(int value) {
    if (head_ == nullptr) {
        return false;
    }
    if (head_->value == value) {    // the first node
        Node* old = head_;
        head_ = head_->next;
        delete old;
        return true;
    }
    for (Node* n = head_; n->next != nullptr; n = n->next) {
        if (n->next->value == value) {
            Node* old = n->next;
            n->next = old->next;    // step over it
            delete old;
            return true;
        }
    }
    return false;
}
// ...
numbers.insert_after(numbers.find(3), 5);
numbers.print();            // 3 -> 5 -> 7 -> 9 -> nullptr

numbers.remove(7);
numbers.print();            // 3 -> 5 -> 9 -> nullptr

All four printed what the comments show. remove looks one node ahead because the node before is the one whose pointer changes. The sample then calls remove(3), which takes the first-node branch, moves head_ itself and printed 5 -> 9 -> nullptr; remove(42) finds nothing and returns false. insert_after assumes a real node, and find returns nullptr for a missing value, so check what it returns first.

How do you free a linked list without leaking memory?

Give the class a destructor, the member function that runs when the object is destroyed, and have it walk the list and delete each node; a node made with new and never deleted is a leak. Deleting the copy constructor and the copy assignment with = delete means a LinkedList cannot be copied, so no two lists hold the same nodes:

class LinkedList {
public:
    LinkedList() = default;
    LinkedList(const LinkedList&) = delete;             // no copies
    LinkedList& operator=(const LinkedList&) = delete;

    ~LinkedList() {                     // delete every node
        while (head_ != nullptr) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
    }
    // ...
};

Copy constructors and the rest are in C++ constructors: default, parameterized, copy and move. A version of these samples whose nodes count every construction and destruction printed matching totals on all four compilers, for this class and for the std::unique_ptr one below.

Let std::unique_ptr own the nodes

The other way is to make each next a std::unique_ptr, a smart pointer that owns one object and deletes it when it is destroyed itself. Each node then frees the one after it, and no delete is written:

struct Node {
    int value;
    std::unique_ptr<Node> next;         // owns the next node
};

class LinkedList {
public:
    ~LinkedList() {
        // one node at a time; the default would recurse down the chain
        while (head_) {
            auto next = std::move(head_->next);  // take the rest
            head_ = std::move(next);  // the old first node is freed
        }
    }

    void push_front(int value) {
        auto node = std::make_unique<Node>();
        node->value = value;
        node->next = std::move(head_);  // the old first node
        head_ = std::move(node);        // the new node is first
    }

    void print() const {
        for (const Node* n = head_.get(); n != nullptr;
             n = n->next.get()) {
            std::cout << n->value << " -> ";
        }
        std::cout << "nullptr\n";
    }

private:
    std::unique_ptr<Node> head_;
};

It printed 3 -> 7 -> 9 -> nullptr. std::move hands the old first node to the new node’s next, and .get() reads the plain pointer for the walk. The destructor still frees the nodes in a loop, one per pass: it takes the rest of the chain out of the first node, then frees that node alone. Left to the default, each node would destroy the next one recursively, which cppreference’s std::unique_ptr page warns causes a stack overflow for a long enough list.

What are std::list and std::forward_list?

They are the standard library’s own linked lists. std::list, from <list>, can be walked both ways and is usually built as a doubly linked list, each node pointing back as well as forward:

#include <algorithm>
#include <iostream>
#include <list>

void print(const std::list<int>& numbers) {
    std::cout << '{';
    for (int n : numbers) {
        std::cout << ' ' << n;
    }
    std::cout << " }\n";
}
// ...
std::list<int> numbers;
numbers.push_back(7);
numbers.push_back(9);
numbers.push_front(3);
print(numbers);                     // { 3 7 9 }

auto seven = std::find(numbers.begin(), numbers.end(), 7);
numbers.insert(seven, 5);           // before 7
print(numbers);                     // { 3 5 7 9 }

numbers.erase(seven);     // removes 7; seven is now invalid
print(numbers);                     // { 3 5 9 }

std::cout << numbers.size() << '\n';    // 3

All four printed what the comments show. std::find returns an iterator, an object that marks one element’s position, and insert adds 5 before it. Adding or removing elements leaves iterators to the other elements valid, so seven still points at 7 after the insert. erase(seven) then removes 7 and leaves seven invalid: an erase breaks only the iterators to the erased element.

std::forward_list, in the library since C++11, is singly linked like the class above and takes less memory than a std::list. Its node knows only the next one, so it inserts after a position:

#include <forward_list>
// ...
std::forward_list<int> numbers;
numbers.push_front(9);
numbers.push_front(7);
numbers.push_front(3);              // 3 7 9

numbers.insert_after(numbers.begin(), 5);   // after 3

std::cout << '{';
for (int n : numbers) {
    std::cout << ' ' << n;
}
std::cout << " }\n";                // { 3 5 7 9 }

It printed { 3 5 7 9 }. A std::forward_list has no size(): count its elements by walking it.

Neither list has [], the index operator, so reaching an element means walking to it. On a std::list<int> named numbers, this does not compile:

int second = numbers[1];    // error: std::list has no []

Clang said:

error: type 'std::list<int>' does not provide a subscript operator

GCC reports no match for 'operator[]', and MSVC error C2676.

What is the time complexity of a linked list?

Reaching the nth element is O(n), linear: the time grows with n, because you walk past every node before it. Inserting or erasing at a position you already hold is O(1), constant: the same few pointer changes at any length. A std::vector swaps those costs, except at the end:

Amortized means on average over many calls. The class above keeps no pointer to its last node, so adding at its end means walking there first: O(n).

Linked list or vector: which should you use?

A std::vector, by default. The C++ Core Guidelines say so in SL.con.2, and add that even where a list gives “efficient insertion in the middle, a vector will usually still perform better for containers up to a few KB in size”. The reason it gives: a vector’s elements sit side by side in one block of memory. Use a linked list when you insert and erase in the middle often and keep iterators or pointers to elements, which a std::list leaves valid until that element is erased.

If you write one by hand:

• End the chain with nullptr, and start an empty list’s head as nullptr.
• Give every new a delete: a destructor that walks the list and frees each node.
• Delete copying with = delete, or let std::unique_ptr own each node and free them in a loop.
• Check what find returns before you insert after it.

The other containers are in Standard library.