Singly Linked List in C++: Edge-Case Bugs, Cache Cost

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled its C++ code with Apple clang 21 on an Apple M1 Pro, once with -Wall -Wextra and once with -fsanitize=address,undefined -g. The main shown in the article runs fine, but the delete function crashes when you remove the head or a missing value, removes the only node even when the value does not match, and the class has no destructor, so nodes leak when the list goes out of scope. This version adds the fix, the output for each edge case, and a measured comparison of traversal speed against arrays.

This article is for developers implementing a linked list by hand for the first time, for a data structures course or interview practice, and for anyone who has heard that "linked lists are fast at insertion and deletion" and is about to use one in real code. Two conclusions up front. Almost every linked-list bug lives at one of four edges: the empty list, a single node, the head, and the tail. And in our measurement, walking a linked list was about 8 times slower than a vector when the nodes sat in order, and about 900 times slower when they were scattered.

Nodes and the singly linked list

A linked list is a chain of nodes joined by pointers. Each node holds a value and the address of the next node. The first node is the head, the last is the tail, and the tail's next is nullptr. Because each node only knows its successor, this is a singly linked list (SLL).

The 2021 article illustrated this with a diagram taken from third-party material. We removed it for copyright reasons. A -> B -> C -> NULL says the same thing.

The trade-offs against an array are clear:

The 2021 text said insertion and deletion are "easy". That is true only when you already hold the node, or the node before it. Removing by value still costs O(n) to find it.

Re-running the 2021 code with clang and ASan

We saved the full 2021 example (Node, SLL, appendNode, deleteNode, printNode) unchanged as sll2021.cpp. With -Wall -Wextra the compiler printed zero warnings. Only -Wconditional-uninitialized, which -Wall does not include, found something:

$ clang++ -std=c++20 -Wall -Wextra -Wconditional-uninitialized -c sll2021.cpp
sll2021.cpp:54:13: warning: variable 'prevNode' may be uninitialized when used here [-Wconditional-uninitialized]

The original main (append three colors, then delete them from the tail backwards) also ran cleanly under ASan and UBSan. That order is exactly why it never hit the bugs: it deletes tail, then middle, then the last remaining node. We wrote a small driver for the other cases using the same class:

SLL L;
L.appendNode("A"); L.appendNode("B"); L.appendNode("C");
L.deleteNode("A");                       // 1) remove the head of a 3-node list
// 2) remove a missing value:         L.deleteNode("X");
// 3) one node, different value:      L.appendNode("A"); L.deleteNode("X");

The three causes:

1. Removing the head. If the do-while breaks on its first pass, prevNode was never assigned, and the code runs prevNode->link = … anyway. There is also no line that moves Head to the next node, so in a plain build the program keeps using freed memory as its head without crashing. That silent version is the dangerous one.
2. A missing value. The loop ends with tempPoint == NULL, and the next line reads tempPoint->link.
3. A single node. The if (tempPoint->link == NULL) branch deletes without comparing the value.

On top of that, appendNode walks from the head to the tail every time, so adding n nodes is O(n²). On the same Mac with -O2, 10,000 appends took 62–64 ms and 50,000 took 1,444–1,460 ms; the fixed version with a tail pointer took 0.3 ms and 1.3–1.4 ms. One small text fix as well: the article mentions a function called createNode, but the code only has appendNode.

A note on tooling. ASan on macOS arm64 prints detect_leaks is not supported on this platform, so we checked leaks with the built-in macOS tool, leaks --atExit -- ./a.out. On Linux, ASan's leak checker reports them directly.

The fixed list: one code path for head, middle and tail

The fixed version keeps a tail pointer, and its remove walks the address of the link that points to the current node (Node**). When the match is the head, that link is &head_; otherwise it is &previous->next. Either way the fix is the same single assignment, so the special cases disappear.

#include <iostream>
#include <string>
#include <utility>

struct Node {
    std::string data;
    Node* next = nullptr;
};

class SLL {
    Node* head_ = nullptr;
    Node* tail_ = nullptr;
public:
    SLL() = default;
    SLL(const SLL&) = delete;             // no shallow copies of the node chain
    SLL& operator=(const SLL&) = delete;
    ~SLL() {
        while (head_) { Node* n = head_->next; delete head_; head_ = n; }
    }

    void push_front(std::string v) {
        head_ = new Node{std::move(v), head_};
        if (!tail_) tail_ = head_;          // list was empty
    }
    void push_back(std::string v) {         // O(1) because we keep tail_
        Node* n = new Node{std::move(v)};
        if (tail_) tail_->next = n; else head_ = n;
        tail_ = n;
    }
    bool insert_after(const std::string& key, std::string v) {
        for (Node* p = head_; p; p = p->next)
            if (p->data == key) {
                p->next = new Node{std::move(v), p->next};
                if (p == tail_) tail_ = p->next;
                return true;
            }
        return false;
    }
    bool remove(const std::string& key) {
        Node* prev = nullptr;
        for (Node** link = &head_; *link; link = &(*link)->next) {
            Node* cur = *link;
            if (cur->data == key) {
                *link = cur->next;              // head, middle or tail: one line
                if (cur == tail_) tail_ = prev; // removed the last node
                delete cur;
                return true;
            }
            prev = cur;
        }
        return false;                           // empty or not found: nothing happens
    }
    void print() const {
        for (Node* p = head_; p; p = p->next) std::cout << p->data << " -> ";
        std::cout << "NULL\n";
    }
};

The test below goes through every edge. The important line is the push_back after removing the tail: if tail_ were not updated, it would write into a freed node.

int main() {
    SLL list;
    std::cout << "remove on empty: " << list.remove("x") << '\n';
    list.push_back("B");                    // single node: head == tail
    list.remove("B");                       // back to empty
    list.push_back("B");                    // must still work: tail_ was reset
    list.push_front("A");
    list.push_back("D");
    list.insert_after("B", "C");            // middle
    list.print();
    list.remove("A");                       // head
    list.remove("C");                       // middle
    list.remove("D");                       // tail
    list.push_back("E");                    // tail_ must point at B now
    list.print();
    std::cout << "remove missing: " << list.remove("zzz") << '\n';
}                                           // destructor frees B and E

remove on empty: 0
A -> B -> C -> D -> NULL
B -> E -> NULL
remove missing: 0

Result: zero warnings with -Wall -Wextra -Wconditional-uninitialized, zero ASan/UBSan reports, and 0 leaks for 0 total leaked bytes from leaks --atExit. The copy constructor is deleted on purpose. With the default copy, two lists would share one chain of nodes and both destructors would free it, which is a double free.

Measured: traversing an array vs a linked list

Is a linked list really slow to walk? We summed 10 million long values (8 bytes each). Each variant ran 5 times and we kept the fastest; we repeated that whole run 3 times.

• std::vector<long>: contiguous memory.
• std::list<long>, in order: built with push_back, so the nodes end up at roughly increasing addresses.
• std::list<long>, scattered: built from shuffled values, then sort()ed. sort relinks nodes without moving them, so walking the list in order jumps around memory at random.
• Hand-written SLL, shuffled: nodes created with new, then linked in a shuffled order.
• C#: List<long> and LinkedList<long>, .NET 10.0.14, Release build, timed with Stopwatch after a warm-up call.

long s = 0; for (long v : vec) s += v;                          // same loop for vector and list
long s = 0; for (Node* p = head; p; p = p->next) s += p->value; // hand-written SLL

The gap does not come from the arithmetic. It comes from how the CPU reads memory.

• Vector. One 64-byte cache line holds eight long values, and since the next address is predictable, the hardware prefetcher fetches ahead. Clang also vectorizes this loop with SIMD. With -fno-vectorize -fno-slp-vectorize the vector took about 4.0 ms, and the gap to the in-order list (11 ms) shrank to 2.8×.
• List allocated in order. p = p->next is a dependent load: the CPU cannot start loading the next node until the current one arrives. When the nodes happen to lie in order, the prefetcher still guesses right and each step costs about 1.2 ns.
• Scattered list. The next address is unpredictable, so every node waits on main memory. 1,244 ms ÷ 10 million ≈ 124 ns per node, which is simply DRAM latency.

Size matters too. With 10,000 elements (everything fits in cache) the scattered list was about 56× slower than the vector; with 1 million it was about 950–1,000× slower. In a real program, repeated inserts and deletes scatter nodes over time, so the scattered case is the realistic one. C# behaved the same way: LinkedList<T> stayed near 13 ms only while its nodes sat in allocation order on the GC heap.

Modern equivalents: std::forward_list, std::list, C# LinkedList

Writing your own list teaches the mechanics. In production code, use the standard library:

• C++ std::forward_list<T> is a singly linked list. It offers insert_after, erase_after and before_begin(), an iterator to the position before the head, which is the "fix the previous link" idea from above turned into an API. It has no size().
• C++ std::list<T> is doubly linked. erase returns the next valid iterator, and splice moves nodes into another list without copying.
• C# LinkedList<T> is doubly linked. AddFirst, AddLast, AddAfter(node, value) and Remove(node) are O(1). Remove(value) returns false instead of throwing when the value is missing.

std::forward_list<std::string> f{"B", "D"};
f.push_front("A");                                  // head
f.insert_after(std::next(f.begin()), "C");         // after B (middle)
f.erase_after(f.before_begin());                    // remove the head via before_begin()
// prints: forward_list: B C D

var l = new LinkedList<string>();
Console.WriteLine($"Remove on empty: {l.Remove("x")}");   // False
var b = l.AddLast("B");
l.AddFirst("A"); l.AddLast("D"); l.AddAfter(b, "C");
Console.WriteLine(string.Join(" <-> ", l));               // A <-> B <-> C <-> D

A rough guide to choosing:

The stack and the linked queue are built from these same nodes. Two-way links and the pointer-order bugs they invite are covered in the doubly linked list article, and a tail that wraps back to the head, plus the Josephus problem, in the circular linked list article.

Tested with Apple clang 21.0.0 (-std=c++20), .NET SDK 10.0.403 / runtime 10.0.14, macOS on an Apple M1 Pro.