連結リストをC++で実装：削除処理のバグとキャッシュの実測

2026年11月改訂： この記事は2021年に韓国語で書いた単方向連結リストの講座を、日本語向けに書き直したものです。C++ のコードを Apple clang 21（Apple M1 Pro）で -Wall -Wextra、さらに -fsanitize=address,undefined -g 付きでコンパイルし直しました。記事にあった main は問題なく動きますが、先頭ノードや存在しない値を消すと落ち、ノードが1つのときは値が違っても消え、デストラクタがないのでリストがスコープを抜けるとノードがリークします。 修正版のコード、境界ケースごとの実行結果、配列との走査速度の実測を加えました。

この記事は、データ構造の授業や就職のコーディング試験対策で連結リストを初めて自分で実装する人と、「連結リストは挿入・削除が速い」と聞いて実務で使おうとしている人に向けたものです。先に結論を書くと、連結リストのバグはほぼすべて空のリスト・ノード1つ・先頭・末尾の4つの境界で起きます。そして走査速度は、配列に比べてノードが順に並んでいれば約8倍、散らばっていれば約900倍遅いという結果でした。

ノードと単方向連結リスト

連結リストは、ノードをポインタでつないだデータ構造です。ノード1つがデータと次のノードのアドレスを持ちます。最初のノードを先頭（head）、最後を末尾（tail）と呼び、末尾の next は nullptr です。次のノードしか指さないので単方向連結リスト（Singly Linked List、SLL）と呼びます。

2021年の記事では他の資料から持ってきた図を使っていましたが、著作権の問題があるため今回は外しました。構造は A -> B -> C -> NULL の1行で十分に表せます。

配列と比べた得意・不得意は次のとおりです。

2021年の記事は「挿入・削除が簡単」とだけ書いていましたが、それは消したいノード（またはその1つ前）をすでに持っているときの話です。値で探して消すなら、探すのに O(n) かかります。

2021年のコードを clang と ASan で動かし直す

記事の完全な例（Node、SLL、appendNode、deleteNode、printNode）をそのまま sll2021.cpp に保存してコンパイルしました。-Wall -Wextra では警告0件です。-Wall に含まれない -Wconditional-uninitialized を付けて、ようやく1件出ます。

$ 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]

記事の main（3つの色を入れて末尾から消す）は ASan/UBSan を付けても正常に終わりました。この main は末尾 → 途中 → 最後の1つの順にしか消さないので、バグを避けて通っていたのです。同じクラスで境界ケースを試しました。

SLL L;
L.appendNode("A"); L.appendNode("B"); L.appendNode("C");
L.deleteNode("A");                       // 1) ノード3つで先頭を削除
// 2) 存在しない値を削除:           L.deleteNode("X");
// 3) ノード1つで別の値を削除:     L.appendNode("A"); L.deleteNode("X");

原因は3つです。

1. 先頭の削除： do-while の1周目ですぐ break すると、prevNode に一度も代入されないまま prevNode->link = … を実行します。さらに Head を次のノードに移すコードがないので、通常ビルドでは落ちずに解放済みメモリを先頭として使い続けます。 いちばん危ないパターンです。
2. 存在しない値： ループが tempPoint == NULL で終わっても、そのまま tempPoint->link を読みます。
3. ノード1つ： if (tempPoint->link == NULL) の分岐が値を比べずに消しています。

ほかにも、appendNode は毎回先頭から末尾まで歩くので、n個入れると O(n²) です。同じ Mac で -O2 で測ると、1万個で62〜64ms、5万個で1,444〜1,460ms。末尾ポインタを持つ修正版はそれぞれ0.3ms、1.3〜1.4msでした。また本文に出てくる「createNode」という関数はコードになく、正しくは appendNode です。

ツールについての注意です。macOS arm64 の ASan は detect_leaks is not supported on this platform と表示し、リーク検査をしません。そこでリークは macOS 標準の leaks --atExit -- ./a.out で確認しました。Linux なら ASan がリークも報告します。

修正版：先頭・途中・末尾を同じコードで

修正版は末尾ポインタを持ち、削除では「今のノードを指しているリンク」のアドレス（Node**）をたどります。先頭を消すときは &head_ を、途中や末尾なら &前のノード->next を書き換えることになり、場合分けがなくなります。

#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;             // ノード列の浅いコピーを禁止
    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_;          // 空だったら末尾もこのノード
    }
    void push_back(std::string v) {         // tail_ があるので O(1)
        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;              // 先頭・途中・末尾すべてこの1行
                if (cur == tail_) tail_ = prev; // 末尾を消したら末尾を移す
                delete cur;
                return true;
            }
            prev = cur;
        }
        return false;                           // 空、または見つからない: 何もしない
    }
    void print() const {
        for (Node* p = head_; p; p = p->next) std::cout << p->data << " -> ";
        std::cout << "NULL\n";
    }
};

境界ケースをすべて通るテストです。大事なのは末尾を消したあとの push_back です。tail_ を更新し忘れると、ここで解放済みのノードに書き込みます。

int main() {
    SLL list;
    std::cout << "remove on empty: " << list.remove("x") << '\n';
    list.push_back("B");                    // ノード1つ: head == tail
    list.remove("B");                       // 空に戻る
    list.push_back("B");                    // tail_ がリセットされたか確認
    list.push_front("A");
    list.push_back("D");
    list.insert_after("B", "C");            // 途中に挿入
    list.print();
    list.remove("A");                       // 先頭
    list.remove("C");                       // 途中
    list.remove("D");                       // 末尾
    list.push_back("E");                    // ここで tail_ は B のはず
    list.print();
    std::cout << "remove missing: " << list.remove("zzz") << '\n';
}                                           // デストラクタが B と E を解放

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

-Wall -Wextra -Wconditional-uninitialized で警告0件、ASan/UBSan のエラー0件、leaks --atExit は 0 leaks for 0 total leaked bytes でした。コピーコンストラクタを delete しているのは、既定のコピーを許すと2つのオブジェクトが同じノード列を指し、デストラクタで二重解放になるからです。

走査速度の実測：配列と連結リスト

「連結リストは遅い」は本当か。long（8バイト）1,000万個の合計にかかる時間を測りました。各方式を5回動かして最短値を取り、それを3回繰り返しています。

• std::vector<long>：連続メモリ
• std::list<long>（順に確保）：push_back で作り、ノードのアドレスがほぼ昇順に並んだ状態
• std::list<long>（散らばる）：シャッフルした値で作ってから sort()。sort はノードを動かさずリンクだけを付け替えるので、順にたどるとアドレスがランダムに飛ぶ
• 自作 SLL（シャッフル）：ノードを new で作ってから、ポインタの配列をシャッフルしてつなぐ
• C#：List<long> と LinkedList<long>、.NET 10.0.14 の Release ビルド、ウォームアップ後に Stopwatch で計測

long s = 0; for (long v : vec) s += v;                          // vector も list も同じループ
long s = 0; for (Node* p = head; p; p = p->next) s += p->value; // 自作 SLL

差が出る理由は計算量ではなく、メモリの読み方です。

• vector： 64バイトのキャッシュライン1本に long が8個入り、次のアドレスが予測できるのでハードウェアのプリフェッチが先読みします。clang はこのループを SIMD でベクトル化もします。-fno-vectorize -fno-slp-vectorize でベクトル化を止めると vector は約4.0msになり、順に確保した list（11ms）との差は2.8倍まで縮みました。
• 順に確保された list： p = p->next は、今のノードを読み終えるまで次のアドレスがわからない依存ロードです。それでもノードがメモリ上に順に並んでいればプリフェッチが当たり、1ノード約1.2nsで済みます。
• 散らばった list： 次のノードの場所が予測できないため、ノードごとにメインメモリ（DRAM）を待ちます。1,244ms ÷ 1,000万 ≈ 1ノード124nsで、DRAM のレイテンシそのものです。

サイズによっても変わります。1万個（すべてキャッシュに収まる）では散らばった list でも vector の約56倍、100万個では約950〜1,000倍でした。実際のプログラムでは挿入・削除を繰り返すうちにノードは散らばっていくので、「散らばった場合」のほうが現実に近いと考えておくのが安全です。C# も同じ傾向で、ノードが GC ヒープ上に確保順に並んでいるときだけ13ms程度に収まりました。

現代の選択肢：std::forward_list、std::list、C# LinkedList

自作は仕組みを学ぶためのもので、実務では標準ライブラリを使います。

• C++ std::forward_list<T>：単方向連結リスト。insert_after、erase_after、先頭の1つ前を指す before_begin() があり、上の「前のリンクを書き換える」発想がそのまま API になっています。size() はありません。
• C++ std::list<T>：双方向連結リスト。erase は次の有効なイテレータを返し、splice でノードをコピーせずに別のリストへ移せます。
• C# LinkedList<T>：双方向連結リスト。AddFirst、AddLast、AddAfter(node, value)、Remove(node) が O(1)。Remove(value) は見つからなければ例外ではなく false を返します。

std::forward_list<std::string> f{"B", "D"};
f.push_front("A");                                  // 先頭
f.insert_after(std::next(f.begin()), "C");         // B の後ろ（途中）
f.erase_after(f.before_begin());                    // before_begin() で先頭を削除
// 出力: 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

使い分けの目安です。

同じノードを使って作るデータ構造にスタックと連結キューがあります。双方向のリンクと更新順のバグは双方向連結リストで、末尾が先頭に戻る構造とヨセフス問題は循環連結リストで扱います。

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