双方向連結リストをC++で：prev/next の更新順バグを ASan で検証

2026年11月改訂： この記事は2021年に韓国語で書いた双方向連結リストの講座を、日本語向けに書き直したものです。完全な例を Apple clang 21（Apple M1 Pro）で -Wall -Wextra と -fsanitize=address,undefined -g 付きでコンパイルし直しました。記事の main は動きますが、存在しない値を消すと NULL 参照で落ち、デストラクタがないためノードが残ったままリストが消えるとリークします。修正版に加えて、双方向リストでいちばん多いミスであるprev/next の更新順のバグを実際に再現した結果を載せました。

この記事は、単方向連結リストを書いたあとで双方向に進む人と、自作のリストが「たまに」おかしくなって原因を探している人に向けたものです。守るべきルールは実質1つです。ノードを挿入・削除するときは、4本のリンク（前のノードの next、後ろのノードの prev、自分の prev と next）が互いに一致しているか。この順序を間違えると、コンパイラは何も言わないまま無限ループや解放済みメモリの読み込みが起きます。

prev が増えると何が変わるか

双方向連結リスト（Doubly Linked List、DLL）のノードは、次のノードだけでなく前のノードも指します。リストは先頭（head）と末尾（tail）の両方を持ちます。2021年の記事の図2枚は他の資料から持ってきたものだったので外し、以下の図と表に置き換えました。

得られるもの：

• 末尾から先頭へ逆向きに走査できる
• ノードのポインタさえあれば O(1) で削除できる。単方向だと前のノードを探すのに先頭から歩く必要があるが、双方向なら n->prev がそのまま前のノード
• 末尾側の削除（pop_back）も O(1)

払うコストは、ポインタ1つ分のメモリと、書き換えるリンクが2倍になることです。メモリは実際に測りました。sizeof、macOS の malloc_size、そして要求サイズを記録するアロケータで std::list がノードごとに何バイト要求するかを確認しています。

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

4バイトの int を入れるのに双方向ノードは24バイトを要求し、macOS の malloc はそれを16バイト単位に切り上げて32バイトを確保します。std::list<int> もノードごとに24バイトを要求するので、実際の確保は同じ32バイトです。データの8倍です。さらに走査が遅い理由（キャッシュミス）は連結リストの記事で実測しています。

2021年のコードを動かし直す

記事の完全な例をそのまま dll2021.cpp に保存しました。なお、2021年の記事は完全な例を C++ ではなくプレーンテキストのブロックに入れており、本文の「11行目」「17行目」といった行番号は掲載したコード片と合っていませんでした。

• -Wall -Wextra：警告0件
• 記事の main（3色を入れて末尾から消す）：ASan/UBSan のエラーなし、2021年と同じ出力
• clang --analyze：Use of memory after it is freed [cplusplus.NewDelete] が2件

静的解析の警告は少し補足しておきます。経路を展開すると（-Xclang -analyzer-output=text）、解析器は「先頭ノードの PrevLink が NULL ではない」と仮定したところから出発していました。実際のリストではあり得ない経路で、下の修正版にも同じ警告が出ます。連結構造の不変条件は静的解析が追いにくいので、この種の警告は ASan 付きで実行して確かめるほうが早いです。

本物のバグは境界ケースで出ました。

DLL L;
L.appendNode("A"); L.appendNode("B");
L.deleteNode("X");                       // 存在しない値

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

探索ループが pNode == NULL で終わっても、56行目で pNode->PrevLink を読むためです。また、関数内で3ノードのリストを作って戻ると、leaks --atExit が 3 leaks for 144 total leaked bytes を報告しました。デストラクタがないからです（macOS arm64 の ASan はリーク検査に対応していないので leaks を使いました）。

公平のために書いておくと、2021年のコードの削除ロジックそのもの（前のノードがなければ先頭を、次のノードがなければ末尾を移す部分）は、先頭・途中・末尾・ノード1つのいずれでも ASan 下で正しく動きました。直すべきは「見つからない場合」と「デストラクタ」です。

prev/next の更新順バグ2つ

双方向連結リストの典型的なミスはリンクを書き換える順序です。2種類を実際に再現しました。

1. 挿入：p->next を早く上書きしすぎる

A と C の間に B を入れようとして、次のように書いたとします。

DNode* b = new DNode{"B"};
a->next = b;                 // 早すぎる
b->next = a->next;           // a->next はもう b → b->next = b
b->prev = a;
b->next->prev = b;           // b->prev = b

前方向に8歩までに制限して表示しました。

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

B が自分自身を指す自己ループになり、C はリストから外れたのに C->prev はまだ A を指しています。制限がなければ表示ループは終わりません。コンパイラの警告も ASan のエラーもありません。メモリアクセス自体はすべて有効だからです。

ルールは「まだ読む必要があるリンクは最後に上書きする」です。新しいノード n の2本のリンクを先に設定し（ここで p->next を読む）、後ろのノードの prev を直し、p->next は最後に書き換えます。

2. 削除：next->prev の更新を忘れる

先頭の A を消すときに head だけ移して、C->prev を直さなかった場合です。

head = a->next;              // 前方向のリンクは直した
delete a;                    // c->prev はまだ 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 は解放済みの A を読んだ瞬間に止まり、どの行で解放したかまで教えてくれます。ところが通常ビルドでは C とだけ表示して正常終了しました。前方向の走査しかテストしていなければ、絶対に見つからないバグです。そこで修正版には前後のリンクが一致しているかを調べる check() を入れ、テストでは前後両方向に表示します。

修正版の双方向連結リストと境界ケース

#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. 新ノードの両方向リンクから
        p->next->prev = n;                               // 2. 後ろのノードが n を振り返る
        p->next = n;                                     // 3. p->next は最後
        return n;
    }
    void erase(DNode* n) {                               // ノードを持っていれば O(1)
        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;                            // 2021年版はここで落ちた
        erase(n);
        return true;
    }
    bool check() const {                                 // すべてのリンクが相方と一致するか
        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';
    }
};

erase の2行が双方向連結リストの核心です。前のノードがなければ（先頭）head_ を、次のノードがなければ（末尾）tail_ を移します。ノードが1つだけなら両方の条件が成り立ち、head_ と tail_ がそろって nullptr になります。

int main() {
    DLL l;
    std::cout << "remove on empty: " << l.remove("x") << '\n';
    l.push_back("B"); l.remove("B");     // ノード1つ -> 空
    l.print();
    DNode* b = l.push_back("B");
    l.push_front("A");
    l.push_back("D");
    l.insert_after(b, "C");              // 途中
    l.print();
    l.remove("A"); l.print();            // 先頭
    l.remove("C"); l.print();            // 途中
    l.remove("D"); l.print();            // 末尾
    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

警告0件、ASan/UBSan のエラー0件、leaks --atExit は 0 leaks for 0 total leaked bytes でした。

std::list と C# LinkedList

実務では自作せず標準の実装を使います。どちらも双方向連結リストです。

C++ std::list<T>：insert(pos, v) は pos の前に挿入し、erase(it) は次のイテレータを返します。ほかのノードのイテレータは挿入・削除のあとも有効です。splice はノードをコピーせずに別のリストへ移し、移したノードを指していたイテレータもそのまま使えます。

std::list<std::string> l{"A", "B", "D"};
auto b = std::next(l.begin());
l.insert(std::next(b), "C");            // D の前に
l.push_front("0"); l.push_back("E");
auto it = l.erase(b);                   // it -> C
l.remove("0");                          // 値で削除
std::list<std::string> other{"X", "Y"};
auto x = other.begin();
l.splice(l.begin(), other, x);          // ノードを1つ移動

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>（.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.

C# ではノードがどのリストに属しているかをランタイムが覚えているので、別のリストのノードを追加すると例外になります。上で再現した「リンクが食い違う」状態を API のレベルで防いでいるわけです。空のリストで RemoveFirst() を呼ぶと InvalidOperationException: The LinkedList is empty. になります。

双方向連結リストは両端で O(1) の出し入れができるので、連結キューやスタックの土台にもなります。単方向の基本操作と走査速度の実測は連結リスト、末尾が先頭につながる構造は循環連結リストで扱います。

検証環境：Apple clang 21.0.0（-std=c++20）、.NET SDK 10.0.403 / ランタイム 10.0.14、macOS、Apple M1 Pro。