Singly Linked List From Scratch

July 2026 · 24 min read

A singly linked list is the smallest data structure that still forces you to think like a systems programmer. There is exactly one struct, exactly one owning pointer, and exactly one rule — never overwrite the only reference to a node before you are done with it. Everything in this post is a variation on that rule. We will build every operation from first principles, then assemble them into a class that manages its own memory correctly, moves cheaply, and works with a range-for loop.

The Node and the Head Pointer

A singly linked list is a chain of nodes, each holding a payload and a pointer to the next node. The last node points at nullptr. The entire list is named by a single head pointer — the sole entry point. Lose head without saving it and the whole list leaks; every node after it becomes unreachable.

struct Node {
    int   val;
    Node* next;
    explicit Node(int v) : val(v), next(nullptr) {}
};

// The whole list is just this one pointer.
Node* head = nullptr;   // an empty list

That is the entire contract. head == nullptr means empty. head non-null means the first node lives at *head, and you reach the rest by following next until you hit nullptr. There is no size field, no back pointer, no random access — all of which we will add or deliberately refuse later. The minimalism is the point: with one pointer of state you can already build a stack, a queue skeleton, and an adjacency list.

Traversal: The Loop You Will Write a Thousand Times

Every read-only operation — print, search, count — is the same walk. Start a cursor at head and hop along next until it falls off the end:

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

The loop condition cur != nullptr is doing real work: it is both the empty-list check and the end-of-list check at once, which is why null-termination is such a convenient convention. This walk is O(n) time, O(1) extra space, and it is the reason a singly linked list has no cheap random access — reaching index i costs i hops because the address of each node is stored only inside its predecessor.

Inserting: Front, After a Node, At an Index

Push front is the list's superpower — genuine O(1). Point the new node at the old first node, then move the head. Order matters: save the tail before you overwrite the head.

void push_front(Node*& head, int v) {
    Node* n = new Node(v);
    n->next = head;   // 1. new node points at the current first node
    head    = n;      // 2. new node becomes the first node
}

Push back without a tail pointer is O(n) — you have to walk the whole chain to find the last node. This is the operation that motivates the tail pointer of the next post. Note the empty-list special case: with no nodes there is nothing whose next to set, so you must update head directly.

void push_back(Node*& head, int v) {
    Node* n = new Node(v);
    if (head == nullptr) { head = n; return; }   // empty-list case
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next; // walk to the last node
    cur->next = n;
}

Insert after a known node is O(1) and is the primitive the others reduce to. Save the successor first, then splice:

void insert_after(Node* p, int v) {
    Node* n = new Node(v);
    n->next = p->next;   // 1. new node inherits p's successor
    p->next = n;         // 2. p now points at the new node
}

Insert at an index is a walk followed by an insert_after. To place a value at position idx, you must stand on the node at idx - 1. Position 0 (or an empty list) is the head case, which changes head and therefore needs the reference:

void insert_at(Node*& head, int idx, int v) {
    if (idx <= 0 || head == nullptr) { push_front(head, v); return; }
    Node* prev = head;
    for (int i = 0; i + 1 < idx && prev->next != nullptr; ++i)
        prev = prev->next;                        // stop on node idx-1 (or last)
    insert_after(prev, v);
}

Walking to the position is O(n); the splice itself is O(1). That asymmetry is the whole story of linked lists: the mutation is cheap, but finding where to mutate is not.

Deleting: Head, By Value, At an Index

Deletion is where beginners lose nodes. The trap is that to unlink a node you must modify its predecessor's next, but a singly linked node has no back pointer — so you must arrive already holding the predecessor. That is the prev-pointer dance.

Delete the head is the easy case and O(1): move head forward, then free the old node. Free last, never first — deleting before you have moved head would leave it dangling.

void pop_front(Node*& head) {
    if (head == nullptr) return;   // empty: nothing to do
    Node* old = head;
    head = head->next;             // unlink first
    delete old;                    // free last
}

Delete by value walks two cursors in lockstep — cur looking for the match and prev trailing one node behind so it can perform the bypass. The subtlety is the head case: when the match is the first node, prev is still nullptr, so you update head instead of prev->next.

bool remove(Node*& head, int v) {
    Node* prev = nullptr;
    Node* cur  = head;
    while (cur != nullptr && cur->val != v) {
        prev = cur;
        cur  = cur->next;
    }
    if (cur == nullptr) return false;        // value not present
    if (prev == nullptr) head = cur->next;   // deleting the head
    else prev->next = cur->next;             // bypass cur
    delete cur;
    return true;
}

Delete at an index is the same dance driven by a counter instead of a comparison. Index 0 delegates to pop_front; otherwise walk to idx - 1 and unlink its successor, guarding against an index that runs past the end.

bool erase_at(Node*& head, int idx) {
    if (idx < 0 || head == nullptr) return false;
    if (idx == 0) { pop_front(head); return true; }
    Node* prev = head;
    for (int i = 0; i + 1 < idx && prev->next != nullptr; ++i)
        prev = prev->next;
    if (prev->next == nullptr) return false;  // idx past the end
    Node* victim = prev->next;
    prev->next = victim->next;                // bypass
    delete victim;                           // free
    return true;
}

Dry Run: remove(value) Step by Step

Take the list head → 7 → 3 → 9 → 5 and call remove(head, 9). Watch prev and cur advance until the match, then the single bypass write:

Now the head-is-the-target case — remove(head, 7) on the same original list. The loop never advances, so prev stays null and the head branch fires:

The two tables are the same algorithm; only the prev == null branch differs. That branch is exactly the edge case a dummy head node exists to erase.

Watch It Happen

Step through a push_front, an insert_after, and a remove on one list. Follow the prev and cur labels as they walk to the target, and note that the actual unlink is a single pointer rewrite drawn as the green bypass arc.

Search, Size, and Clear

find returns the node so callers can splice at it; contains is a thin wrapper. Both are the traversal loop with an early exit.

Node* find(Node* head, int v) {
    for (Node* cur = head; cur != nullptr; cur = cur->next)
        if (cur->val == v) return cur;
    return nullptr;
}
bool contains(Node* head, int v) { return find(head, v) != nullptr; }

size is O(n) precisely because we chose not to store a count — a deliberate trade you will revisit when we cache a length or reach for std::list::size, which is O(1) since C++11. clear is the iterative teardown every owning list needs: save the successor before deleting, or you read freed memory.

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

void clear(Node*& head) {
    while (head != nullptr) {
        Node* nx = head->next;   // save next BEFORE delete
        delete head;
        head = nx;
    }
}

Complexity, Operation by Operation

The pattern is stark: anything you can do at a node you already hold is O(1); anything that must find a position is O(n). A singly linked list buys cheap structural edits at the cost of cheap lookup.

A Complete SinglyList Class

Free functions teach the mechanics; a real container has to own its nodes and clean up after itself. That means the rule of five: because we manage a raw resource, the compiler-generated copy operations would shallow-copy the head_ pointer and cause a double-free, so we must define copy, move, and destruction deliberately. Here we implement a deep copy (an equally valid choice is to = delete the copy operations and make the list move-only).

#include <cstddef>
#include <utility>

class SinglyList {
    struct Node {
        int   val;
        Node* next;
        explicit Node(int v) : val(v), next(nullptr) {}
    };
    Node* head_ = nullptr;

    // Deep-copy the chain starting at src; return the new head.
    static Node* copy_chain(const Node* src) {
        Node*  newHead = nullptr;
        Node** tail    = &newHead;     // pointer to the slot we fill next
        for (const Node* p = src; p != nullptr; p = p->next) {
            *tail = new Node(p->val);
            tail  = &(*tail)->next;
        }
        return newHead;
    }

public:
    SinglyList() = default;

    // --- Rule of five --------------------------------------------------
    SinglyList(const SinglyList& other)              // copy ctor: deep copy
        : head_(copy_chain(other.head_)) {}

    SinglyList& operator=(const SinglyList& other) {  // copy assign
        if (this != &other) {
            Node* fresh = copy_chain(other.head_);   // build first (strong guarantee)
            clear();                                 // then release the old chain
            head_ = fresh;
        }
        return *this;
    }

    SinglyList(SinglyList&& other) noexcept           // move ctor: steal the head
        : head_(other.head_) { other.head_ = nullptr; }

    SinglyList& operator=(SinglyList&& other) noexcept {  // move assign
        if (this != &other) {
            clear();
            head_       = other.head_;
            other.head_ = nullptr;
        }
        return *this;
    }

    ~SinglyList() { clear(); }                        // iterative teardown

    // --- Core operations (methods over head_) --------------------------
    void push_front(int v) {
        Node* n = new Node(v);
        n->next = head_;
        head_   = n;
    }

    bool remove(int v) {
        Node* prev = nullptr;
        Node* cur  = head_;
        while (cur != nullptr && cur->val != v) { prev = cur; cur = cur->next; }
        if (cur == nullptr) return false;
        if (prev == nullptr) head_ = cur->next;
        else                 prev->next = cur->next;
        delete cur;
        return true;
    }

    void clear() {
        while (head_ != nullptr) {
            Node* nx = head_->next;
            delete head_;
            head_ = nx;
        }
    }

    // --- A minimal forward iterator so range-for works -----------------
    struct iterator {
        Node* p;
        explicit iterator(Node* n) : p(n) {}
        int&      operator*()  const { return p->val; }
        iterator& operator++()       { p = p->next; return *this; }
        bool operator!=(const iterator& o) const { return p != o.p; }
        bool operator==(const iterator& o) const { return p == o.p; }
    };
    iterator begin() { return iterator(head_); }
    iterator end()   { return iterator(nullptr); }
};

With begin/end and an iterator that defines operator*, operator++, and operator!=, the language's range-for desugars onto our list directly:

SinglyList lst;
lst.push_front(3);
lst.push_front(2);
lst.push_front(1);
for (int& x : lst) x *= 10;   // uses begin(), ++, *, and != under the hood
// lst is now 10 -> 20 -> 30

Three things make this class correct rather than merely compiling. The copy assignment builds the fresh chain before releasing the old one, so a throwing new leaves the target unchanged (the strong exception guarantee). The move operations leave the source empty (head_ = nullptr), so the moved-from object's destructor is a harmless no-op. And the destructor is iterative, so a list of any depth tears down in constant stack space. Miss any one and you get a double-free, a use-after-move, or a stack overflow respectively.

Check Yourself

Each item gives you a situation; pick the statement that is actually true for a singly linked list.

Practice

• LeetCode 707 — Design Linked List core implement every operation in this post behind the required API.
• LeetCode 203 — Remove Linked List Elements remove the prev-pointer dance, repeated until no match remains.
• LeetCode 237 — Delete Node in a Linked List trick you are given only the node — copy the successor's value and delete it instead.
• LeetCode 83 — Remove Duplicates from Sorted List traverse one pass, bypass equal neighbours.
• LeetCode 876 — Middle of the Linked List walk count length or foreshadow fast/slow pointers.
• LeetCode 19 — Remove Nth Node From End of List index convert “from the end” into a head-relative delete.