DSA · Linked Lists · Part 25 of 28

Pitfalls, Leaks & Memory Safety

July 2026 · 21 min read

Almost every failed linked-list implementation dies from one of the same ten bugs. They are not exotic. They come from the single hazard the whole series has warned about — overwriting or freeing a pointer while it is still the only path to a node — expressed ten slightly different ways. This post names each one, gives you the minimal broken snippet, the exact symptom it produces, the input that triggers it, and the fix. Then it shows you how to test a list so that these bugs cannot survive to code review: invariant checks, an allocation counter, the sanitizers, and a differential test against std::list.

Read the symptom column carefully. Half of debugging is mapping a behaviour — a crash on teardown, a hang, a double-free abort, slow memory growth — back to its cause. By the end you should be able to hear a symptom and name the bug.

Bug 1 — Recursive Destructor Stack Overflow

The most common crash in student list code, and the most seductive, because the destructor looks beautiful:

struct Node {
    int   val;
    Node* next;
    ~Node() { delete next; }   // deletes the whole tail... recursively
};

Symptom: a hard crash (SIGSEGV) the moment the head node is destroyed, with a backtrace that is thousands of identical ~Node frames deep.
Trigger: destroying any sufficiently long list — a few hundred thousand nodes.

Each ~Node() activation record holds this, the saved return address, and alignment padding — roughly 32–64 bytes at -O0. A default 8 MB stack therefore overflows somewhere between 130,000 and 260,000 nodes. The recursion depth equals the list length, which is exactly the length at which real workloads live. Tail-call optimisation will not save you: delete next is not in tail position because the destructor still has to run operator delete afterwards.

The fix is to make Node trivially destructible and tear the list down with a loop in the owning container. Time O(n), extra space O(1):

struct Node { int val; Node* next; };   // no user destructor

void clear(Node*& head) {
    while (head) {
        Node* nx = head->next;
        delete head;
        head = nx;
    }
}

The same trap hides inside unique_ptr. A list of struct Node { int val; std::unique_ptr<Node> next; }; destroys recursively too — destroying the head destroys its next, which destroys the next, and so on. You must still unlink iteratively: while (head) head = std::move(head->next);

Bug 2 — Use-After-Free While Iterating

You free a node and then read through it to advance:

for (Node* p = head; p; p = p->next) {   // p = p->next reads freed memory
    delete p;
}

Symptom: undefined behaviour — often a crash, sometimes silent corruption; AddressSanitizer reports heap-use-after-free precisely at the p = p->next update.
Trigger: any non-empty list. The loop update dereferences p after delete p.

The rule from Module 2 is absolute: save what you are about to lose before you lose it. Read next into a local, then free:

for (Node* p = head; p; ) {
    Node* nx = p->next;   // save first
    delete p;             // then free
    p = nx;               // advance through the saved copy
}

Bug 3 — The Lost Head

You walk the list by advancing the head pointer itself:

long sum = 0;
while (head) {            // head is the only reference to the list
    sum += head->val;
    head = head->next;   // ...and now it is gone, node by node
}
// head == nullptr; the caller's list is empty and every node is leaked

Symptom: a memory leak of the entire list plus a logically emptied container — the data structure "disappears" after one traversal.
Trigger: any read-only traversal written on the head instead of a cursor.

Never mutate the anchor you need to keep. Traverse with a throwaway cursor and leave head untouched:

long sum = 0;
for (Node* p = head; p; p = p->next) sum += p->val;

Bug 4 — Double Free From a Defaulted Copy

An owning list with a correct destructor but no copy control:

struct List {
    Node* head = nullptr;
    ~List() { clear(head); }
    // no copy constructor declared -> the compiler generates one
    // that copies the head POINTER, not the chain
};

List make();
List a = make();
List b = a;        // b.head == a.head  (shallow copy)
// two destructors both run clear() over the same nodes -> double free

Symptom: free(): double free detected or a heap-corruption abort, usually at scope exit; ASan reports attempting double-free.
Trigger: any copy — passing the list by value, returning it, or a plain =.

This is the Rule of Three/Five. A class that owns a resource and writes a destructor must also decide what copy and move mean. The cheapest correct answer is to forbid copying; the complete answer is a deep copy plus move operations that steal the pointer:

struct List {
    Node* head = nullptr;
    List() = default;
    List(const List&)            = delete;   // or deep-copy every node
    List& operator=(const List&) = delete;
    List(List&& o) noexcept : head(o.head) { o.head = nullptr; }   // steal
    List& operator=(List&& o) noexcept {
        if (this != &o) { clear(head); head = o.head; o.head = nullptr; }
        return *this;
    }
    ~List() { clear(head); }
};

Bug 5 — The Dangling Tail Pointer

A list that caches a tail for O(1) append must keep that cache honest. Erase the last node and forget, and tail becomes a pointer into freed memory:

void pop_back(List& L) {
    Node* p = L.head;
    while (p->next != L.tail) p = p->next;   // p is the new last node
    delete L.tail;                            // freed
    p->next = nullptr;
    // BUG: L.tail still points at the node we just deleted
}

void push_back(List& L, int v) {
    L.tail->next = new Node{v, nullptr};      // writes THROUGH freed memory
    L.tail = L.tail->next;
}

Symptom: use-after-free / heap corruption on the next append, far from the erase that caused it — a nasty action-at-a-distance bug.
Trigger: a pop_back immediately followed by a push_back.

Every structural edit must restore every invariant it can disturb. Here that means updating the cache: L.tail = p; after the delete (and setting both head and tail to nullptr when the list becomes empty).

Bug 6 — The Accidental Cycle

Split, partition, or reorder routines build new sublists by relinking existing nodes. If you stitch the pieces together but forget to null-terminate the final node, that node keeps whatever next it happened to hold in the original list — and if that target is a node now earlier in the chain, you have manufactured a cycle. Here is the classic partition (LeetCode 86) with the bug:

Node* partition(Node* head, int x) {
    Node less{0, nullptr}, ge{0, nullptr};
    Node* lt = &less;
    Node* gt = &ge;
    for (Node* p = head; p; p = p->next) {
        if (p->val < x) { lt->next = p; lt = p; }
        else            { gt->next = p; gt = p; }
    }
    lt->next = ge.next;
    // BUG: missing  gt->next = nullptr;
    return less.next;
}

Symptom: a hang or an out-of-memory kill, not a crash. A traversal loops forever; anything that allocates per node exhausts the heap.
Trigger: any input whose last-visited node is a "less" node. For 1 → 4 → 5 → 2 with x = 3, node 5 is appended last to the greater list, and its original next is node 2 — so 5 points back to 2.

Step through the animation: watch the intended list 1 → 2 → 4 → 5 form, watch the stray back-edge from 5 to 2 survive, and watch the traversal spin.

▶ A Partition That Forgot to Terminate

Partition 1 → 4 → 5 → 2 around x = 3. The green edges are the intended list; the red edge is the next pointer nobody reset. Step to watch a walker fall into the loop, then apply the one-line fix.

The fix is one line — gt->next = nullptr; before return — and the way to catch the whole class of bug in a test is Floyd's tortoise and hare, covered in Cycle Detection. Any invariant checker for lists should run it.

Bug 7 — Off-By-One Loop Conditions

Three loop conditions look interchangeable and are not. Each dereferences a different amount and breaks on a different input:

Condition	Safe to read inside	Breaks on
`while (p)`	`p->val`	`p->next->val` on the last node (null-deref).
`while (p->next)`	`p` and `p->next`	the empty list — `p` is `nullptr`, so the condition itself derefs null.
`while (p && p->next)`	`p` and `p->next`	nothing — short-circuit makes it total. The pair-processing workhorse.

A concrete casualty — "find the second-to-last node":

Node* secondLast(Node* head) {
    Node* p = head;
    while (p->next->next) p = p->next;   // derefs p and p->next unconditionally
    return p;
}

Symptom: a segfault on small inputs that "obviously" work on big ones.
Trigger: the empty list (p == nullptr) and the single-node list (p->next == nullptr) both crash the condition.

Guard the degenerate sizes explicitly before the loop:

Node* secondLast(Node* head) {
    if (!head || !head->next) return nullptr;   // 0 or 1 node: no answer
    Node* p = head;
    while (p->next->next) p = p->next;
    return p;
}

Bug 8 — The Self-Loop

A one-node cycle, node->next == node, usually born from a "move to front" or a swap that does not check whether the node is already where it is going:

void moveToFront(List& L, Node* node) {
    node->next = L.head;   // if node == L.head, this is node->next = node
    L.head = node;
}

Symptom: an instant infinite loop / hang on the next traversal — the walker never leaves the one node.
Trigger: calling with the node that is already the head, or splicing a node in after itself.

Guard the no-op case and always unlink before relinking:

void moveToFront(List& L, Node* prev, Node* node) {
    if (node == L.head) return;   // already at front
    prev->next = node->next;      // unlink from current position
    node->next = L.head;          // relink at front
    L.head = node;
}

Bug 9 — Null-Deref on the Empty List

The empty list is a real state, and every accessor that assumes head != nullptr is a latent crash:

int  front(List& L)     { return L.head->val; }        // UB when empty
void pop_front(List& L) {
    Node* nx = L.head->next;                            // UB when empty
    delete L.head;
    L.head = nx;
}

Symptom: a null-pointer dereference crash the first time the container is used while empty.
Trigger: front() or pop_front() on a freshly constructed or fully drained list.

Decide the contract and enforce it — return an optional, throw, or make emptiness impossible with a sentinel (see Sentinels, Dummy Heads & Tail Pointers). Whatever you choose, check first:

bool pop_front(List& L) {
    if (!L.head) return false;         // empty is not an error, just a no-op
    Node* nx = L.head->next;
    delete L.head;
    L.head = nx;
    if (!L.head) L.tail = nullptr;     // keep the tail cache honest
    return true;
}

Bug 10 — Leaked Nodes on Reassignment

The quiet one. You replace the head with a new chain and the old chain simply floats away:

void assign(List& L, Node* newHead) {
    L.head = newHead;     // the previous chain is now unreachable and leaked
}

// same bug, one line:
head = new Node{7, head};   // fine
head = new Node{7, nullptr};  // if this REPLACED a list, the old list leaked

Symptom: no crash — just steadily climbing memory. Valgrind reports "definitely lost" blocks at exit.
Trigger: any code path that overwrites the only pointer to a live chain without freeing it.

Free before you overwrite: clear(L.head); L.head = newHead;. The same discipline is why operator= in Bug 4 calls clear(head) before stealing the source pointer.

Symptom → Bug → Tool

Debugging is pattern-matching a behaviour back to a cause and then reaching for the tool that proves it. Keep this map in your head:

Symptom you observe	Likely bug	Tool that finds it
Crash on teardown; backtrace is thousands of identical frames	Recursive destructor overflow (1)	Debugger backtrace; the depth is the list length.
`heap-use-after-free` at a pointer advance or an append	Delete-then-deref (2); dangling tail (5)	AddressSanitizer.
Program hangs; memory climbs with no crash	Accidental cycle (6); self-loop (8)	Floyd check in an assert; a watchdog timeout. ASan will not catch it.
`double free detected` abort at scope exit	Defaulted copy of an owning list (4)	ASan; glibc malloc; Valgrind.
Slow, steady "definitely lost" growth	Lost head (3); leak on reassignment (10)	Valgrind `--leak-check=full`; LeakSanitizer.
Segfault only on empty / single-node input	Off-by-one (7); null-deref (9)	UBSan; a unit test that runs every function on sizes 0, 1, 2.

Testing a List So These Cannot Survive

You do not find these bugs by staring; you find them with cheap machinery that runs on every commit. Four layers, from weakest to strongest.

1. An invariant checker

Every mutating operation must leave the structure in a valid state. Encode "valid" once and assert it after every operation in tests. For a singly linked list with a cached size, valid means: the node count matches size, and there is no cycle (which the counting loop would otherwise spin inside forever, so cap it). Time O(n), space O(1):

bool no_cycle(Node* head) {                 // Floyd's tortoise and hare
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return false;      // they met: there is a cycle
    }
    return true;
}

bool check_invariants(const List& L) {
    if (!no_cycle(L.head)) return false;     // check this FIRST, or the count loops
    std::size_t n = 0;
    for (Node* p = L.head; p; p = p->next) ++n;
    return n == L.size;
}

For a doubly linked list add the back-pointer law — every forward hop must be undone by a backward hop:

bool links_consistent(DNode* head) {
    for (DNode* p = head; p && p->next; p = p->next)
        if (p->next->prev != p) return false;   // n->next->prev must equal n
    return true;
}

2. A scoped allocation counter

A leak is allocs != frees. Make the count observable by having every node bump a static counter on construction and drop it on destruction, then assert it is zero at the end of every test scope. This catches both leaks (Bugs 3, 10) and double-frees (Bug 4, which drives the count negative):

struct Node {
    int   val;
    Node* next;
    static inline long live = 0;             // C++17 inline static
    Node(int v, Node* n = nullptr) : val(v), next(n) { ++live; }
    ~Node() { --live; }
};

void test_push_pop() {
    long before = Node::live;
    {
        List L;
        for (int i = 0; i < 1000; ++i) L.push_front(i);
        while (L.pop_front()) {}
    }                                         // L destroyed here
    assert(Node::live == before);             // every alloc was matched by a free
}

3. The sanitizers and Valgrind

The sanitizers are not optional for pointer-heavy code — they turn undefined behaviour into a loud, located error instead of a Heisenbug. Build the test binary with both and a debug info flag:

# AddressSanitizer + UndefinedBehaviorSanitizer, with line numbers
g++ -std=c++17 -fsanitize=address,undefined -fno-omit-frame-pointer -g \
    list_tests.cpp -o list_tests
./list_tests

# Valgrind for leaks the sanitizers' allocator might mask
valgrind --leak-check=full --show-leak-kinds=all ./list_tests

ASan pinpoints use-after-free and double-free (Bugs 2, 4, 5); UBSan flags null-derefs (Bugs 7, 9); Valgrind and LeakSanitizer catch leaks (Bugs 3, 10). The one class no memory tool catches is the accidental cycle (Bug 6): it is not a memory error, it is a logic error, so it must be caught by your no_cycle invariant plus a test timeout.

4. Differential testing against `std::list`

The strongest test writes no assertions about specific values at all. You run a long random sequence of operations against both your list and a trusted oracle — std::list — and assert after every single step that they still agree and that your invariants hold. Any divergence is a bug, and the operation that caused it is the last one applied:

#include <list>
#include <random>
#include <cassert>

void differential_test() {
    std::mt19937 rng(12345);          // fixed seed => reproducible failures
    List mine;
    std::list<int> oracle;

    for (int step = 0; step < 100000; ++step) {
        int op = rng() % 4;
        if (op == 0) {                              // push_front
            int v = rng() % 100;
            mine.push_front(v);
            oracle.push_front(v);
        } else if (op == 1 && !oracle.empty()) {     // pop_front
            mine.pop_front();
            oracle.pop_front();
        } else if (op == 2) {                       // push_back
            int v = rng() % 100;
            mine.push_back(v);
            oracle.push_back(v);
        } else if (op == 3) {                       // reverse
            mine.reverse();
            oracle.reverse();
        }

        // 1. same length
        assert(mine.size == oracle.size());
        // 2. same contents, element by element
        auto it = oracle.begin();
        for (Node* p = mine.head; p; p = p->next, ++it)
            assert(p->val == *it);
        // 3. structure still valid
        assert(check_invariants(mine));
    }

    mine.clear();
    assert(Node::live == 0);           // no leak across 100k operations
    std::puts("differential test passed");
}

Why a fixed seed matters. When the oracle and your list diverge at step 40,132, you want that exact sequence again to debug it. A fixed seed makes every failure reproducible; a random seed makes it a ghost. Log the seed on failure and you can replay any crash a CI machine finds.

Check Yourself

You are given the symptom a program exhibits. Name the bug that produces it.

Practice

LeetCode 707 — Design Linked List asan implement it, then run your tests under -fsanitize=address,undefined and fix everything it reports.
LeetCode 86 — Partition List cycle write it with the two-sublist method and deliberately omit the null-terminate; confirm your no_cycle check catches Bug 6.
LeetCode 141 — Linked List Cycle floyd turn tortoise-and-hare into the reusable invariant checker used above.
LeetCode 138 — Copy List with Random Pointer ownership a shallow copy double-frees; make the deep copy correct and leak-free.
LeetCode 148 — Sort List differential test your merge sort against std::list::sort with a random operation sequence.

Pitfalls, Leaks & Memory Safety

Bug 1 — Recursive Destructor Stack Overflow

Bug 2 — Use-After-Free While Iterating

Bug 3 — The Lost Head

Bug 4 — Double Free From a Defaulted Copy

Bug 5 — The Dangling Tail Pointer

Bug 6 — The Accidental Cycle

▶ A Partition That Forgot to Terminate

Bug 7 — Off-By-One Loop Conditions

Bug 8 — The Self-Loop

Bug 9 — Null-Deref on the Empty List

Bug 10 — Leaked Nodes on Reassignment

Symptom → Bug → Tool

Testing a List So These Cannot Survive

1. An invariant checker

2. A scoped allocation counter

3. The sanitizers and Valgrind

4. Differential testing against std::list

Check Yourself

Practice

4. Differential testing against `std::list`