Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Circular Linked Lists Operations

Explore how to perform traversal, insertion, and deletion operations on circular linked lists in C++. Understand the unique considerations for preserving the circular link and handling edge cases like single-node lists.

We'll cover the following...

At this stage, the difference between a circular linked list and a standard singly linked list is established. Instead of the last node pointing to NULL, it points back to the head node, forming a loop. As a result, the list has no natural termination point, and traversal requires explicit stopping conditions.

Now, let’s focus on the operations that can be performed on circular linked lists. While many of these operations are conceptually similar to those used in singly linked lists, there is an important difference: the circular connection must always be preserved.

Because the list forms a loop, operations such as traversal, insertion, and deletion must be implemented carefully. In particular:

  • Traversal cannot rely on reaching NULL to stop.

  • Insertions must ensure that the circular link remains intact.

  • Deletions must reconnect neighboring nodes so that the loop structure is maintained.

Traversal in a circular linked list

Traversal in a circular linked list is slightly different from traversal in a standard singly linked list. In a regular linked list, traversal stops when the current node becomes NULL. In a circular linked list, this stopping condition does not exist because the last node points back to the head.

Instead, traversal must stop when it returns to the starting node. Typically, the traversal steps are:

  1. Start traversal from the head node.

  2. Print the value stored in the current node.

  3. Move to the next node using current->next.

  4. Stop the traversal when the pointer reaches the head node again.

Let’s look at the following interactive visualizer for circular linked list traversal.

C++ implementation of traversal in a circular linked list

The following code creates a simple circular linked list and traverses it once, stopping when the traversal returns to the head node.

C++ 17
#include <iostream>
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int value) : val(value), next(nullptr) {}
};
class CircularLinkedList {
public:
    ListNode* head;
    CircularLinkedList() : head(nullptr) {}
    void traverse() {
        if (head == nullptr) {
            std::cout << "The list is empty." << std::endl;
            return;
        }
        ListNode* current = head;   // Start from the head node
        while (true) {
            std::cout << current->val << " -> ";   // Process current node
            current = current->next;               // Move to the next node
            if (current == head) {                 // Stop when traversal returns to head
                break;
            }
        }
        std::cout << current->val << " (back to head)" << std::endl;
    }
};
// Create a circular linked list manually: 10 -> 20 -> 30 -> back to 10
int main() {
    CircularLinkedList sampleList;
    ListNode* first = new ListNode(10);
    ListNode* second = new ListNode(20);
    ListNode* third = new ListNode(30);
    sampleList.head = first;
    first->next = second;
    second->next = third;
    third->next = first;   // Make the list circular
    // Traverse the circular linked list
    std::cout << "Traversal of circular linked list: ";
    sampleList.traverse();
    // Clean up
    delete first;
    delete second;
    delete third;
    return 0;
}
Doubly linked list traversal

  • Time complexity: O(n)O(n) because each node is visited once.

  • Space complexity: O(1)O(1) as traversal only uses a single pointer variable.

Insertion in a circular linked list

Insertion in a circular linked list is similar to the insertion in a singly linked list, but there is one extra requirement: the circular connection must ...