C++UCS301
Linear Data StructuresC++17

Circular Linked List

The last node links back to the first, making circular lists natural for repeated cyclic processing and round-robin scheduling.

What to understand

  • No null terminator
  • Tail-based representation
  • Circular traversal
  • Josephus and scheduling applications

Remember this

  1. 1Stop when you return to the start
  2. 2A tail pointer gives O(1) front and rear access
  3. 3Avoid accidental infinite loops

Detailed notes

A circular list replaces the final null link with a link to the first node. A tail-based representation is compact because tail->next provides the head while tail itself provides the rear.

Traversal cannot test for null. It must remember the starting node and stop after returning to it, commonly with a do-while loop so a one-node list is processed once.

How it works

  1. 1For the first node, point next back to itself.
  2. 2Insert after tail and advance tail for push-back.
  3. 3Stop traversal when current equals the starting pointer.
  4. 4Handle deletion of the only node by setting tail to null.

Where it is used

  • Round-robin CPU scheduling
  • Turn-based games and playlists
  • Josephus-style elimination

Common mistakes

  • Using a null-based traversal and looping forever
  • Breaking the ring while inserting the first node
  • Leaving tail pointing to freed memory

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(n)O(n)O(n)O(1)
Insert after tailO(1)O(1)O(1)O(1)
Delete after known nodeO(1)O(1)O(1)O(1)

C++ implementation

C++17 reference
main.cpp

Circular list insertion using a tail

tail->next is always the head, including when the list has one node.

struct Node { int value; Node* next; };

void pushBack(Node*& tail, int value) {
    Node* node = new Node{value, nullptr};
    if (!tail) {
        tail = node;
        node->next = node;
        return;
    }
    node->next = tail->next; // new node points to head
    tail->next = node;
    tail = node;
}

void print(Node* tail) {
    if (!tail) return;
    Node* current = tail->next;
    do {
        cout << current->value << ' ';
        current = current->next;
    } while (current != tail->next);
}
22 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.