循環連結リストをC++で：無限ループの罠とヨセフス問題

2026年11月改訂： この記事は2021年に韓国語で書いた循環連結リストの講座を、日本語向けに書き直したものです。Apple clang 21（Apple M1 Pro）でコンパイルし直しました。本文は「単方向の循環リストを扱う」としていましたが、掲載コードは双方向の循環リストで、本文のコード片は Node にない NextLink/PrevLink を使っていたためそのままではコンパイルできませんでした（エラー10件）。完全な例は動きますが、deleteNode はノードを解放しないのでリークし、存在しない値を消すと代わりに先頭が消え、最後のノードを消してから追加するとクラッシュします。修正した単方向の循環リスト、終了条件の罠、そして代表的な応用であるヨセフス問題を実際に動かした結果を加えました。

この記事は、循環連結リストを初めて実装する人と、ラウンドロビンやヨセフス問題のように「最後まで行ったら最初に戻る」処理を書いていて無限ループにはまった人に向けたものです。要点は2つです。循環リストには NULL がないので、終了条件を「出発点に戻ったか」に置き換えること。そしてその判定は1歩進んだあとに行うことです。

末尾が先頭を指す構造

循環連結リストは、最後のノードの next が nullptr ではなく最初のノードを指すリストです。2021年の記事の図は他の資料から持ってきたものだったので外し、自前の図に置き換えました。

単方向の循環リストで実務上いちばん使いやすいのは、先頭ではなく末尾のポインタだけを持つ形です。先頭は常に tail->next なので別に保存する必要がなく、そのおかげで先頭への追加も末尾への追加も O(1) になります。

• push_front(v)：新しいノードを tail->next の位置に差し込めば終わり
• push_back(v)：push_front してから tail を新しいノードへ1つ進めれば終わり
• ノードが1つなら、その next は自分自身。これが循環リストの「ノード1つ」の境界です

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

まず本文のコード片です。単方向版として示した Node には link しかないのに、すぐ下の appendNode は NextLink と PrevLink を使っています。そのままつなげると次のようになります。

csll_snippet.cpp:16:14: error: no member named 'NextLink' in 'Node'
csll_snippet.cpp:17:14: error: no member named 'PrevLink' in 'Node'
csll_snippet.cpp:20:28: error: no member named 'PrevLink' in 'Node'
csll_snippet.cpp:21:15: error: no member named 'NextLink' in 'Node'
…（エラー10件）

完全な例（CDLL クラス）は双方向の循環リストとして書かれており、-Wall -Wextra で警告なしにコンパイルでき、記事の main も ASan/UBSan のエラーなしで動きました。出力のアドレスは2021年には32ビット Windows の形式（007B9E90）でしたが、今の64ビット macOS では 0x604000000410 のような形になります。問題はその先です。

3つ目が循環リストならではのバグです。探索ループが while (pNode != Head) で終わると、「1周して見つからなかった」と「先頭で見つかった」が同じ状態（pNode == Head）になります。コードはこれを区別せずに先頭を消してしまいます。4つ目は、最後のノードを消すときに Head を nullptr にせず、リンクを NULL にしただけだからです。記事の main で最後の printNode() が「リストが空」と表示したのも、実際には空でない Head の NextLink がたまたま NULL だったからにすぎません。

終了条件と無限ループの罠

循環リストを回すループを3通りに書き、3ノードの輪で動かしました（無限ループは100万歩で強制的に止めています）。

for (N* p = head; p != nullptr; p = p->next)        // 1) 線形リスト用のループ
    if (++steps == 1'000'000) { /* 表示して break */ }

for (N* p = head; p != head; p = p->next) ++printed; // 2) 出発点を先に判定

N* p = head;                                          // 3) 1歩進んでから判定
do { ++printed; p = p->next; } while (p != head);

trap 1: still looping after 1000000 steps
trap 2: while (p != head) visited 0 nodes
do-while visited 3 nodes

1つ目は線形リストのコードをそのまま持ってきたときの無限ループです。2つ目はそれを直そうとして起きる逆の失敗で、出発点がそのまま到着点なので1回も回りません。 正解は3つ目の do-while ですが、これはリストが空でないときにしか安全ではありません。そこで修正版の走査はすべて「空かどうかを先に確認 → do-while で1周」の形にそろえています。

削除のように「探して止まる」ループには、もう1つルールがあります。2021年のコードのように、ループが終わった位置で「見つかったか」を判断してはいけません。見つけたその場で処理してすぐ return する。そうすれば「1周して終わった」は「見つからなかった」だけを意味するようになります。

修正版の単方向循環リスト

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

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

// 単方向の循環リスト。tail_ だけを持ち、先頭は tail_->next。
class CSLL {
    CNode* tail_ = nullptr;
public:
    CSLL() = default;
    CSLL(const CSLL&) = delete;
    CSLL& operator=(const CSLL&) = delete;
    ~CSLL() {
        if (!tail_) return;
        CNode* p = tail_->next;
        tail_->next = nullptr;              // 先に輪を切り、線形リストとして解放
        while (p) { CNode* n = p->next; delete p; p = n; }
    }
    bool empty() const { return tail_ == nullptr; }
    CNode* head() const { return tail_ ? tail_->next : nullptr; }

    void push_front(std::string v) {
        CNode* n = new CNode{std::move(v)};
        if (!tail_) { n->next = n; tail_ = n; }   // ノード1つは自分自身を指す
        else { n->next = tail_->next; tail_->next = n; }
    }
    void push_back(std::string v) {                // O(1): push_front して tail_ を進める
        push_front(std::move(v));
        tail_ = tail_->next;
    }
    bool remove(const std::string& key) {
        if (!tail_) return false;
        CNode* prev = tail_;
        do {
            CNode* cur = prev->next;
            if (cur->data == key) {
                if (cur == prev) tail_ = nullptr;          // 唯一のノードだった
                else {
                    prev->next = cur->next;
                    if (cur == tail_) tail_ = prev;        // 末尾を消した
                }
                delete cur;
                return true;
            }
            prev = cur;
        } while (prev != tail_);                           // ちょうど1周で終了
        return false;
    }
    void print() const {
        if (!tail_) { std::cout << "(empty)\n"; return; }
        CNode* p = tail_->next;
        do { std::cout << p->data << " -> "; p = p->next; } while (p != tail_->next);
        std::cout << "(back to " << tail_->next->data << ")\n";
    }
};

デストラクタのコツは先に輪を切ることです。切らずに while (p) で解放すると、解放済みの先頭に戻ってきてもう一度解放してしまいます。境界ケースのテストと結果です。

int main() {
    CSLL l;
    l.print();
    std::cout << "remove on empty: " << l.remove("x") << '\n';
    l.push_back("A"); l.print();             // ノード1つは自分自身を指す
    l.remove("A"); l.print();
    l.push_back("B");                          // 空にしてから再利用（2021年版は落ちた）
    l.push_front("A"); l.push_back("C"); l.push_back("D");
    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';
    l.print();
}

(empty)
remove on empty: 0
A -> (back to A)
(empty)
A -> B -> C -> D -> (back to A)
B -> C -> D -> (back to B)
B -> D -> (back to B)
B -> (back to B)
remove missing: 0
B -> (back to B)

存在しない値を消しても B がそのまま残るのが、2021年版との違いです。警告0件、ASan/UBSan のエラー0件、leaks --atExit は 0 leaks for 0 total leaked bytes でした。

応用：ヨセフス問題を実際に動かす

ヨセフス問題は、n人が輪になって座り、k番目の人を順に抜いていったときに最後に残る人を求める問題です。「最後が最初につながる」性質から、循環リストの教科書的な応用です。今のノードの1つ前（prev）を持ち歩けば、k−1歩進んでから prev->next を O(1) で外せます。

struct JNode { int id; JNode* next; };

std::vector<int> josephus_list(int n, int k, bool keep_order) {
    std::vector<int> order;
    if (n <= 0 || k <= 0) return order;
    JNode* tail = nullptr;
    for (int i = 1; i <= n; ++i) {                   // 1..n を作る。tail->next が1番
        JNode* node = new JNode{i, nullptr};
        if (!tail) node->next = node;
        else { node->next = tail->next; tail->next = node; }
        tail = node;
    }
    JNode* prev = tail;
    while (prev->next != prev) {                     // 2人以上残っている間
        for (int s = 1; s < k; ++s) prev = prev->next;
        JNode* out = prev->next;
        prev->next = out->next;
        if (keep_order) order.push_back(out->id);
        delete out;
    }
    order.push_back(prev->id);                       // 最後の生存者
    delete prev;
    return order;
}

int josephus_formula(int n, int k) {                 // J(1)=0, J(i)=(J(i-1)+k) mod i
    int j = 0;
    for (int i = 2; i <= n; ++i) j = (j + k) % i;
    return j + 1;
}

ここでも終了条件は循環リストらしく prev->next != prev、つまり「ノードが自分自身を指したら残りは1人」です。実行結果です。

n=7, k=3 order: 3 6 2 7 5 1 4  survivor=4 formula=4
n=41, k=3 survivor=31 formula=31
n=1..300, k=1..12: list and formula agree

7人で k=3 なら 3、6、2、7、5、1 の順に抜けて4番が残ります。41人なら31番です。n=1〜300、k=1〜12 のすべての組み合わせで、リストのシミュレーションと漸化式が同じ答えになりました。ASan/UBSan のエラーもリークもありません。

速度も比べました（-O2、2回実行）。

リストは O(n·k) なので k が大きくなるほど遅くなり、漸化式は O(n) で k に関係ありません。生存者だけなら漸化式、脱落の順番が必要なら循環リストが判断の基準です。

C# と C++ で輪が必要なとき

どちらの標準ライブラリにも、公開された循環リストはありません。面白いのは、C# の LinkedList<T> が内部では循環していることです。.NET 10.0.14 でリフレクションを使い、非公開フィールド next を読んでみました。

Last.Next is null: True
private next of Last == First: True

内部のリンクは最後のノードから最初のノードにつながっていますが、公開プロパティ Next は末尾で null を返します。輪として回すには自分で巻き戻す必要があります。ヨセフス問題を C# で書くとこうなります。

static List<int> Josephus(int n, int k)
{
    var ring = new LinkedList<int>(Enumerable.Range(1, n));
    var order = new List<int>(n);
    var cur = ring.First!;
    while (ring.Count > 0)
    {
        for (int i = 1; i < k; i++)
            cur = cur.Next ?? ring.First!;      // 末尾で null になるので自分で巻き戻す
        var next = cur.Next ?? ring.First;      // Remove の前に次のノードを読んでおく
        order.Add(cur.Value);
        ring.Remove(cur);
        if (ring.Count > 0) cur = next!;
    }
    return order;
}

3 6 2 7 5 1 4
n=41, k=3 survivor=31
n=1,000,000, k=3 survivor=637798 in 73.5 ms

Release ビルドで n=1,000,000、k=3 は68〜76ms（3回）でした。?? ring.First! を外して cur = cur.Next; とだけ書くと、ビルド時に warning CS8602（Dereference of a possibly null reference）が出て、実行すると System.NullReferenceException で落ちます。nullable の警告が、巻き戻し忘れを実行前に教えてくれるわけです。また Remove のあとはノードの Next が null になるので、次のノードは必ず消す前に読んでおきます。

C++ の std::list で同じことをするなら、if (++it == l.end()) it = l.begin(); のように巻き戻します。ラウンドロビンのスケジューリングのように要素数が固定なら、std::vector と (i + 1) % n の添字のほうが単純で、走査もずっと速くなります。理由は連結リストの記事の走査速度の実測を見てください。

双方向の輪が必要なら、双方向連結リストのリンク更新順をそのまま当てはめます。同じノードでキューを作る方法は連結キュー、スタックはスタックで扱っています。

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