Doubly Linked List in C++: prev/next Order Bugs

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled its full example with Apple clang 21 on an Apple M1 Pro, with -Wall -Wextra and with -fsanitize=address,undefined -g. The original main works, but deleting a value that is not in the list crashes on a NULL dereference, and with no destructor, nodes leak whenever a non-empty list goes out of scope. This version fixes both and adds real reproductions of the most common doubly-linked-list mistake: updating prev and next in the wrong order.

This article is for developers moving from a singly linked list to a doubly linked one, and for anyone whose hand-written list "sometimes" misbehaves. There is really one rule. Whenever you insert or remove a node, four links must agree with each other: the previous node's next, the following node's prev, and the node's own prev and next. Get the order wrong and you can end up with an infinite loop or a read of freed memory, and the compiler will not say a word.

What changes when nodes get a prev pointer

A doubly linked list (DLL) node points to the next node and to the previous one, and the list keeps both a head and a tail. The two diagrams in the 2021 article came from third-party material, so we removed them; the figures below are our own.

What you gain:

• You can walk backwards, from tail to head.
• You can remove a node in O(1) if you hold a pointer to it. A singly linked list has to walk from the head to find the predecessor; here it is simply n->prev.
• Removing at the tail (pop_back) is O(1) as well.

What you pay is one extra pointer per node and twice as many links to keep consistent. We measured the memory side with sizeof, macOS malloc_size, and a small counting allocator that records how many bytes std::list requests per node:

SNode<int>: sizeof 16, malloc_size 16
DNode<int>: sizeof 24, malloc_size 32
std::forward_list<int> node request: 16 bytes
std::list<int> node request: 24 bytes
std::vector<int> per element: 4 bytes

To store a 4-byte int, a doubly linked node requests 24 bytes, and macOS malloc rounds that up to a 16-byte step: 32 bytes. std::list<int> requests the same 24 bytes per node, so it gets the same 32. That is eight times the payload. Why traversal is slow on top of that (cache misses) is measured in the linked list article.

Re-running the 2021 code

We saved the full 2021 example unchanged as dll2021.cpp. Two small notes on the original text: the complete example was posted as a plain-text block instead of C++, and the line numbers it refers to ("line 11", "line 17") do not match the snippets shown.

• -Wall -Wextra: zero warnings.
• The original main (append three colors, delete them from the tail backwards): same output as in 2021, no ASan/UBSan reports.
• clang --analyze: two Use of memory after it is freed [cplusplus.NewDelete] warnings.

The analyzer warnings deserve a closer look. Expanding the path (-Xclang -analyzer-output=text) shows that it starts by assuming that the head node's PrevLink is not NULL. That cannot happen in a real list, and the same warning appeared on our fixed code below. Static analyzers struggle to track the invariants of linked structures, so for this kind of report, running the code under ASan is the faster way to settle it.

The real bug shows up at an edge:

DLL L;
L.appendNode("A"); L.appendNode("B");
L.deleteNode("X");                       // value not in the list

dll2021.cpp:56:31: runtime error: member access within null pointer of type 'Node'
==63919==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000020
    #0 … in DLL::deleteNode(…) dll2021.cpp:56

The search loop ends with pNode == NULL, and line 56 reads pNode->PrevLink anyway. Separately, building a three-node list inside a function and returning made leaks --atExit report 3 leaks for 144 total leaked bytes, because there is no destructor. (ASan on macOS arm64 does not support leak detection, so we used the leaks tool.)

To be fair to the original: its unlink logic itself (move the head if there is no previous node, move the tail if there is no next node) behaved correctly for the head, the middle, the tail and a single node. We tested all four under ASan. What needed fixing was the not-found case and the missing destructor.

Two prev/next order bugs

The classic doubly-linked-list mistake is the order in which you rewrite links. We reproduced two versions of it.

1. Insert: overwriting p->next too early

Suppose you insert B between A and C like this:

DNode* b = new DNode{"B"};
a->next = b;                 // too early
b->next = a->next;           // a->next is already b, so b->next = b
b->prev = a;
b->next->prev = b;           // b->prev = b

We printed a forward walk capped at eight steps:

A B B B B B B B ... (stopped after 8 steps)
C->prev is A

B now points at itself, a self-loop. C has fallen out of the list, yet C->prev still points at A. Without the cap, the print loop would never end. There is no compiler warning and no ASan report, because every memory access here is technically valid.

The rule: overwrite a link only after you have read everything you need from it. Fill in the new node's two links first (this is where p->next gets read), then fix the following node's prev, and change p->next last.

2. Erase: forgetting next->prev

Here we delete the head A, move head, but never fix C->prev:

head = a->next;              // forward link fixed
delete a;                    // c->prev still points at A
for (DNode* p = tail; p; p = p->prev) std::cout << p->data << ' ';

==66547==ERROR: AddressSanitizer: heap-use-after-free on address 0x604000000427
READ of size 1 at 0x604000000427 thread T0
0x604000000427 is located 23 bytes inside of 40-byte region [0x604000000410,0x604000000438)
freed by thread T0 here:
    #1 … in main dll_orderbug.cpp:24

ASan stops on the first read of the freed node and even reports the line that freed it. But a plain build printed C and exited normally. If your tests only walk forward, this bug never surfaces. That is why the fixed list below has a check() that verifies every link against its partner, and why its test prints the list in both directions.

The fixed doubly linked list, with edge cases

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

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

class DLL {
    DNode* head_ = nullptr;
    DNode* tail_ = nullptr;
public:
    DLL() = default;
    DLL(const DLL&) = delete;
    DLL& operator=(const DLL&) = delete;
    ~DLL() { while (head_) { DNode* n = head_->next; delete head_; head_ = n; } }

    DNode* find(const std::string& key) const {
        for (DNode* p = head_; p; p = p->next) if (p->data == key) return p;
        return nullptr;
    }
    DNode* push_front(std::string v) {
        DNode* n = new DNode{std::move(v), nullptr, head_};
        if (head_) head_->prev = n; else tail_ = n;
        return head_ = n;
    }
    DNode* push_back(std::string v) {
        DNode* n = new DNode{std::move(v), tail_, nullptr};
        if (tail_) tail_->next = n; else head_ = n;
        return tail_ = n;
    }
    DNode* insert_after(DNode* p, std::string v) {
        if (p == tail_) return push_back(std::move(v));
        DNode* n = new DNode{std::move(v), p, p->next}; // 1. new node points both ways first
        p->next->prev = n;                               // 2. old successor looks back at n
        p->next = n;                                     // 3. only now overwrite p->next
        return n;
    }
    void erase(DNode* n) {                               // O(1) once you hold the node
        if (n->prev) n->prev->next = n->next; else head_ = n->next;
        if (n->next) n->next->prev = n->prev; else tail_ = n->prev;
        delete n;
    }
    bool remove(const std::string& key) {
        DNode* n = find(key);
        if (!n) return false;                            // the 2021 code crashed here
        erase(n);
        return true;
    }
    bool check() const {                                 // every link must agree with its partner
        if (head_ && head_->prev) return false;
        if (tail_ && tail_->next) return false;
        for (DNode* p = head_; p; p = p->next)
            if (p->next ? p->next->prev != p : p != tail_) return false;
        return true;
    }
    void print() const {
        std::cout << "fwd: ";
        for (DNode* p = head_; p; p = p->next) std::cout << p->data << ' ';
        std::cout << "| back: ";
        for (DNode* p = tail_; p; p = p->prev) std::cout << p->data << ' ';
        std::cout << "| ok=" << check() << '\n';
    }
};

The two lines in erase are the heart of a doubly linked list. No previous node means it is the head, so move head_; no next node means it is the tail, so move tail_. For a single node both conditions hold, and head_ and tail_ both become nullptr.

int main() {
    DLL l;
    std::cout << "remove on empty: " << l.remove("x") << '\n';
    l.push_back("B"); l.remove("B");     // single node -> empty
    l.print();
    DNode* b = l.push_back("B");
    l.push_front("A");
    l.push_back("D");
    l.insert_after(b, "C");              // middle
    l.print();
    l.remove("A"); l.print();            // head
    l.remove("C"); l.print();            // middle
    l.remove("D"); l.print();            // tail
    std::cout << "remove missing: " << l.remove("zzz") << '\n';
}

remove on empty: 0
fwd: | back: | ok=1
fwd: A B C D | back: D C B A | ok=1
fwd: B C D | back: D C B | ok=1
fwd: B D | back: D B | ok=1
fwd: B | back: B | ok=1
remove missing: 0

Zero warnings, zero ASan/UBSan reports, and 0 leaks for 0 total leaked bytes from leaks --atExit.

std::list and C# LinkedList

In production code you would use the standard implementations. Both are doubly linked lists.

C++ std::list<T>: insert(pos, v) inserts before pos, and erase(it) returns the next iterator. Iterators to other nodes stay valid across inserts and erases. splice moves nodes into another list without copying, and iterators to the moved nodes remain usable.

std::list<std::string> l{"A", "B", "D"};
auto b = std::next(l.begin());
l.insert(std::next(b), "C");            // before D
l.push_front("0"); l.push_back("E");
auto it = l.erase(b);                   // it -> C
l.remove("0");                          // remove by value
std::list<std::string> other{"X", "Y"};
auto x = other.begin();
l.splice(l.begin(), other, x);          // move one node

list: 0 A B C D E
after erase(B), it -> C
last via prev(end): E
after splice, x still -> X
list: X A C D E
other: Y

C# LinkedList<T>, run on .NET 10.0.14:

var l = new LinkedList<string>();
Console.WriteLine($"Remove on empty: {l.Remove("x")}");
var b = l.AddLast("B");
l.AddFirst("A"); l.AddLast("D"); l.AddAfter(b, "C");
Console.WriteLine(string.Join(" <-> ", l));
l.RemoveFirst(); l.RemoveLast(); l.Remove(b);
Console.WriteLine($"{string.Join(" <-> ", l)}  Count={l.Count}  First==Last: {l.First == l.Last}");
Console.WriteLine($"Last.Next is null: {l.Last!.Next is null}");
var other = new LinkedList<string>();
try { other.AddLast(l.First!); }
catch (InvalidOperationException e) { Console.WriteLine($"{e.GetType().Name}: {e.Message}"); }

Remove on empty: False
A <-> B <-> C <-> D
C  Count=1  First==Last: True
Last.Next is null: True
InvalidOperationException: The LinkedList node already belongs to a LinkedList.

In C#, every node remembers which list owns it, so adding a node that belongs to another list throws. In effect, the API prevents the "links that disagree" state we reproduced above. Calling RemoveFirst() on an empty list throws InvalidOperationException: The LinkedList is empty.

Because a doubly linked list adds and removes at both ends in O(1), it is a natural base for a linked queue or a stack. The basic singly linked operations and the traversal benchmark are in the linked list article; a tail that links back to the head is covered in circular linked list.

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.