Circular Linked List in C++: Loop Traps, Josephus

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled it with Apple clang 21 on an Apple M1 Pro. The text said it would cover a singly linked circular list, but the code was a doubly linked circular list, and the snippets used NextLink and PrevLink on a Node that only had link, so they did not compile as shown (10 errors). The full example does run, but deleteNode never frees a node, deleting a missing value removes the head instead, and adding a node after deleting the last one crashes. This version adds a fixed singly linked circular list, the loop-termination traps, and the Josephus problem, run and timed.

This article is for developers implementing a circular linked list for the first time, and for anyone who hit an infinite loop while writing "wrap back to the start" logic such as round-robin scheduling or the Josephus problem. Two ideas carry the whole topic. A ring has no NULL, so the stop condition becomes "am I back where I started?", and that check must come after the first step, not before it.

A tail that points back to the head

In a circular linked list, the last node's next points to the first node instead of nullptr. The 2021 article's diagram came from third-party material, so we replaced it with our own.

The most practical form of a singly linked circular list keeps only a tail pointer, not a head pointer. The head is always tail->next, so there is nothing else to store, and both ends become O(1):

• push_front(v): splice the new node in at tail->next. Done.
• push_back(v): do a push_front, then advance tail one step to the new node. Done.
• With a single node, its next is itself. That is the "one node" edge case of a ring.

Re-running the 2021 code

First, the snippets in the text. The Node shown for the singly linked version has only link, while the appendNode snippet right below it uses NextLink and PrevLink. Put together as written, they give:

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 errors)

The full example (a CDLL class) is a doubly linked circular list. It compiles with no warnings under -Wall -Wextra, and its main ran without ASan/UBSan reports. The addresses in the output looked like 007B9E90 in 2021 (32-bit Windows) and look like 0x604000000410 now (64-bit macOS). The trouble starts at the edges:

The third row is a bug that only a ring can produce. When the search loop ends on while (pNode != Head), "went all the way round without a match" and "matched at the head" leave the loop in the same state (pNode == Head). The code does not tell them apart and deletes the head. The fourth row happens because deleting the last node sets its links to NULL but never sets Head to nullptr. In the original main, the final printNode() printed "the list is empty" only because that zombie head's NextLink happened to be NULL.

Stop conditions and the infinite-loop trap

We wrote the traversal three ways and ran each over a three-node ring (the infinite one was cut off at one million steps):

for (N* p = head; p != nullptr; p = p->next)        // 1) the linear-list loop
    if (++steps == 1'000'000) { /* print, then break */ }

for (N* p = head; p != head; p = p->next) ++printed; // 2) test before the first step

N* p = head;                                          // 3) step first, then test
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

Loop 1 is what you get by pasting linear-list code onto a ring: it never ends. Loop 2 is the overcorrection: the start is also the finish, so it never runs at all. Loop 3, the do-while, is right, but it is only safe on a non-empty list. Every traversal in the fixed code therefore follows one pattern: check for empty, then walk one lap with do-while.

Loops that search and stop, such as delete, need one more rule. Do not decide "was it found?" from where the loop ended, as the 2021 code did. Handle the match where you find it and return immediately. Then finishing a full lap can only mean "not found".

The fixed singly linked circular list

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

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

// Singly linked circular list. We store only tail_; the head is 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;              // break the ring first, then free it like a line
        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; }   // one node points at itself
        else { n->next = tail_->next; tail_->next = n; }
    }
    void push_back(std::string v) {                // O(1): push_front, then move 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;          // it was the only node
                else {
                    prev->next = cur->next;
                    if (cur == tail_) tail_ = prev;        // removed the tail
                }
                delete cur;
                return true;
            }
            prev = cur;
        } while (prev != tail_);                           // stop after one full lap
        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";
    }
};

The trick in the destructor is to break the ring first. A plain while (p) loop over an unbroken ring would come back around to the already-freed head and free it again. Here is the edge-case test and its output:

int main() {
    CSLL l;
    l.print();
    std::cout << "remove on empty: " << l.remove("x") << '\n';
    l.push_back("A"); l.print();             // single node points at itself
    l.remove("A"); l.print();
    l.push_back("B");                          // reuse after emptying (the 2021 code crashed)
    l.push_front("A"); l.push_back("C"); l.push_back("D");
    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';
    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)

Removing a missing value leaves B in place, which is exactly where the 2021 code went wrong. Zero warnings, zero ASan/UBSan reports, and 0 leaks for 0 total leaked bytes from leaks --atExit.

Application: running the Josephus problem

In the Josephus problem, n people sit in a circle and every k-th person is removed until one remains. "The end connects back to the start" is exactly what a ring models, which makes this the textbook application of a circular list. If you carry the node before the current one (prev), you move k−1 steps and then unlink prev->next in 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) {                   // build 1..n, tail->next is person 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) {                     // more than one person left
        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);                       // the survivor is last
    delete prev;
    return order;
}

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

Note the stop condition, ring-style again: prev->next != prev, meaning "a node that points at itself is the last one left". Output:

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

With 7 people and k = 3, they leave in the order 3, 6, 2, 7, 5, 1 and person 4 survives. With 41 people it is person 31. For every combination of n = 1–300 and k = 1–12, the list simulation and the recurrence agreed. ASan/UBSan reported nothing and there were no leaks.

We also timed both (-O2, two runs):

The list is O(n·k), so it slows down as k grows; the recurrence is O(n) and does not care about k. The rule of thumb: use the recurrence if you only need the survivor, and the circular list if you need the elimination order.

When you need a ring in C# or C++

Neither standard library ships a public circular list. The interesting part is that C# LinkedList<T> is circular inside. On .NET 10.0.14 we read the private next field with reflection:

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

Internally the last node links back to the first, but the public Next property returns null at the end. To go round, you wrap by hand. Josephus in 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!;      // Next is null at the end: wrap by hand
        var next = cur.Next ?? ring.First;      // read before Remove clears the links
        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

In a Release build, n = 1,000,000 with k = 3 took 68–76 ms over three runs. If you drop ?? ring.First! and write only cur = cur.Next;, the build reports warning CS8602: Dereference of a possibly null reference. and the program dies with System.NullReferenceException. The nullable warning flags the missing wrap before you ever run it. Also note that after Remove, a node's Next becomes null, so you must read the next node before removing.

In C++ with std::list, wrap with if (++it == l.end()) it = l.begin();. If the number of elements is fixed, as in round-robin scheduling, a std::vector with an (i + 1) % n index is simpler, and walking it is much faster, as the traversal benchmark in the linked list article shows.

If you need a doubly linked ring, apply the link-update order from the doubly linked list article. Building a queue from the same nodes is covered in linked queue, and a stack in stack.

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.