Circular Linked List Data Structure

Jul 22, 2026knoxiboy

Introduction to Circular Linked List

A Circular LinkedList is a variation of a linked list where the last node points back to the first node instead of null (or None in Python). This structure allows for a circular traversal where one can start from any node and eventually return to the same node. Circular linked lists can be either singly or doubly linked.

alt text

Video Explanation

Watch "Circular Linked Lists: Operations in C Language" on YouTube

Circular Linked Lists: Operations in C Language - YouTube thumbnail

Circular LinkedList Operations

A Circular LinkedList typically supports the following operations:

Insertion Operations : Insertion at the beginning or end involves adjusting the next pointers to maintain the circular nature, and potentially updating the head pointer.

At the Beginning
At the End
After a Given Node

Deletion Operations : Deletion of nodes, whether from the beginning, end, or a specific node, requires properly updating the references of adjacent nodes so that the circular structure is maintained.

Delete from the Beginning
Delete from the End
Delete by Key

Search Operation : The search operation traverses the list until it either finds the required node or returns to the head.
Traversal Operation : Traversal begins from the head and continues until the node just before the head is encountered again.

Pseudocode

Basic Operations

Insert at the Beginning:

Function insert_at_beginning(data):
 Create new_node with data
 If head is NULL:
     head = new_node
     new_node.next = head   # Points to itself
 Else:
     Set temp = head
     While temp.next != head:
         Move temp to temp.next  # Traverse to last node
     Set new_node.next = head
     Set temp.next = new_node   # Last node points to new_node
     Set head = new_node  # Update the head to the new node
 End Function

Insert at the End:

Function insert_at_end(data):
 Create new_node with data
 If head is NULL:
     head = new_node
     new_node.next = head   # Points to itself
 Else:
     Set temp = head
     While temp.next != head:
         Move temp to temp.next  # Traverse to last node
     Set temp.next = new_node
     Set new_node.next = head  # New node points to head
 End Function

Delete Node by Value:

Function insert_after(prev_data, data):
 Create new_node with data
 If head is NULL:
     Exit Function  # List is empty
 Else:
     Set temp = head
     While temp.data != prev_data:
         Move temp to temp.next
         If temp == head:
             Print "Node not found"
             Exit Function
     Set new_node.next = temp.next  # Link new_node to temp's next node
     Set temp.next = new_node  # Link temp to new_node
 End Function

Search for a Node:

Function delete_beginning():
 If head is NULL:
     Exit Function  # List is empty
 If head.next == head:  # Only one node
     head = NULL
 Else:
     Set temp = head
     While temp.next != head:
         Move temp to temp.next  # Traverse to last node
     Set temp.next = head.next  # Last node points to second node
     Set head = head.next  # Update head to the second node
 End Function

Traverse and Print the List:

Function delete_end():
 If head is NULL:
     Exit Function  # List is empty
 If head.next == head:  # Only one node
     head = NULL
 Else:
     Set temp = head
     Set prev = NULL
     While temp.next != head:
         Set prev = temp  # Keep track of second last node
         Move temp to temp.next
     Set prev.next = head  # Second last node points to head
 End Function

Deletion of a Specific Node

Function delete_node(key):
 If head is NULL:
     Exit Function  # List is empty
 If head.data == key AND head.next == head:  # Only one node
     head = NULL
 Else If head.data == key:
     Set temp = head
     While temp.next != head:
         Move temp to temp.next  # Traverse to last node
     Set temp.next = head.next  # Last node points to second node
     Set head = head.next  # Update head to the second node
 Else:
     Set temp = head
     Set prev = NULL
     While temp.data != key:
         Set prev = temp  # Keep track of previous node
         Move temp to temp.next
         If temp == head:
             Print "Node not found"
             Exit Function
     Set prev.next = temp.next  # Remove the node by linking prev to temp.next
 End Function

Traversal (Displaying the List)

Function display():
If head is NULL:
    Print "List is empty"
Else:
    Set temp = head
    Do:
        Print temp.data
        Move temp to temp.next
    While temp != head
End Function

Search for a Node

Function search(key):
If head is NULL:
    Return False  # List is empty
Set temp = head
Do:
    If temp.data == key:
        Return True  # Node found
    Move temp to temp.next
While temp != head
Return False  # Node not found
End Function

Implementation in Python, C++, and Java

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert_beginning(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            new_node.next = self.head
            temp.next = new_node
            self.head = new_node

    def insert_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def insert_after_node(self, target, data):
        if not self.head:
            print("List is empty")
            return
        new_node = Node(data)
        temp = self.head
        while True:
            if temp.data == target:
                new_node.next = temp.next
                temp.next = new_node
                return
            temp = temp.next
            if temp == self.head:
                break
        print(f"Node with data {target} not found.")

    def delete_by_key(self, key):
        if not self.head:
            print("List is empty")
            return
        current = self.head
        prev = None
        while True:
            if current.data == key:
                if prev:
                    prev.next = current.next
                else:
                    # Deleting head
                    if current.next == self.head:
                        self.head = None
                    else:
                        temp = self.head
                        while temp.next != self.head:
                            temp = temp.next
                        self.head = current.next
                        temp.next = self.head
                return
            prev = current
            current = current.next
            if current == self.head:
                break
        print(f"Key {key} not found.")

    def search(self, key):
        if not self.head:
            return False
        temp = self.head
        while True:
            if temp.data == key:
                return True
            temp = temp.next
            if temp == self.head:
                break
        return False

    def display(self):
        nodes = []
        if self.head:
            temp = self.head
            while True:
                nodes.append(temp.data)
                temp = temp.next
                if temp == self.head:
                    break
        print(" -> ".join(map(str, nodes)))

# Example Usage
cll = CircularLinkedList()
cll.insert_end(1)
    cll.insert_end(2)
    cll.insert_end(3)
    cll.display()  # Output: 1 -> 2 -> 3

    cll.insert_beginning(0)
    cll.display()  # Output: 0 -> 1 -> 2 -> 3

    cll.insert_after_node(2, 2.5)
    cll.display()  # Output: 0 -> 1 -> 2 -> 2.5 -> 3

    cll.delete_by_key(2)
    cll.display()  # Output: 0 -> 1 -> 2.5 -> 3

    print("Search for 2:", cll.search(2))    # Output: False
    print("Search for 2.5:", cll.search(2.5))  # Output: True

C++ Implementation

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class CircularLinkedList {
public:
    Node* head;

    CircularLinkedList() {
        head = nullptr;
    }

    void append(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    void insertBeginning(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head)
                temp = temp->next;
            newNode->next = head;
            temp->next = newNode;
            head = newNode;
        }
    }

    void insertEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head)
                temp = temp->next;
            temp->next = newNode;
            newNode->next = head;
        }
    }

    void insertAfterNode(int target, int data) {
        if (head == nullptr) {
            cout << "List is empty" << endl;
            return;
        }
        Node* temp = head;
        do {
            if (temp->data == target) {
                Node* newNode = new Node(data);
                newNode->next = temp->next;
                temp->next = newNode;
                return;
            }
            temp = temp->next;
        } while (temp != head);
        cout << "Node with data " << target << " not found." << endl;
    }

    void deleteByKey(int key) {
        if (head == nullptr) {
            cout << "List is empty" << endl;
            return;
        }
        Node* current = head;
        Node* prev = nullptr;
        do {
            if (current->data == key) {
                if (prev != nullptr) {
                    prev->next = current->next;
                } else {
                    // Deleting head
                    if (current->next == head) {
                        head = nullptr;
                    } else {
                        Node* temp = head;
                        while (temp->next != head)
                            temp = temp->next;
                        head = current->next;
                        temp->next = head;
                    }
                }
                delete current;
                return;
            }
            prev = current;
            current = current->next;
        } while (current != head);
        cout << "Key " << key << " not found." << endl;
    }

    bool search(int key) {
        if (head == nullptr)
            return false;
        Node* temp = head;
        do {
            if (temp->data == key)
                return true;
            temp = temp->next;
        } while (temp != head);
        return false;
    }

    void display() {
        if (head != nullptr) {
            Node* temp = head;
            do {
                cout << temp->data << " -> ";
                temp = temp->next;
            } while (temp != head);
            cout << endl;
        }
    }
};

// Example Usage
int main() {
    CircularLinkedList cll;
    cll.insertEnd(1);
    cll.insertEnd(2);
    cll.insertEnd(3);
    cll.display(); // Output: 1 -> 2 -> 3 ->

    cll.insertBeginning(0);
    cll.display(); // Output: 0 -> 1 -> 2 -> 3 ->

    cll.insertAfterNode(2, 2.5);
    cll.display(); // Output: 0 -> 1 -> 2 -> 2.5 -> 3 ->

    cll.deleteByKey(2);
    cll.display(); // Output: 0 -> 1 -> 2.5 -> 3 ->

    cout << "Search for 2: " << (cll.search(2) ? "Found" : "Not Found") << endl;    // Output: Not Found
    cout << "Search for 2.5: " << (cll.search(2.5) ? "Found" : "Not Found") << endl; // Output: Found

    return 0;
}

Java Implementation

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CircularLinkedList {
    Node head;

    public CircularLinkedList() {
        head = null;
    }

     public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            newNode.next = head;
            temp.next = newNode;
            head = newNode;
        }
    }

    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }

    public void insertAfter(int prevData, int data) {
        Node temp = head;
        Node newNode = new Node(data);
        if (head == null) {
            return;
        }
        do {
            if (temp.data == prevData) {
                newNode.next = temp.next;
                temp.next = newNode;
                return;
            }
            temp = temp.next;
        } while (temp != head);
    }

    public void deleteNode(int key) {
        if (head == null) {
            return;
        }
        if (head.data == key && head.next == head) {
            head = null;
        } else if (head.data == key) {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = head.next;
            head = head.next;
        } else {
            Node temp = head;
            Node prev = null;
            do {
                if (temp.data == key) {
                    prev.next = temp.next;
                    return;
                }
                prev = temp;
                temp = temp.next;
            } while (temp != head);
        }
    }

    public void display() {
        if (head != null) {
            Node temp = head;
            do {
                System.out.print(temp.data + " -> ");
                temp = temp.next;
            } while (temp != head);
            System.out.println();
        }
    }

    public boolean search(int key) {
        Node temp = head;
        do {
            if (temp.data == key) {
                return true;
            }
            temp = temp.next;
        } while (temp != head);
        return false;
    }

// Example usage
    public static void main(String[] args) {
        CircularLinkedList cll = new cll.insertEnd(1);
        cll.insertEnd(2);
        cll.insertEnd(3);
        cll.display(); // Output: 1 -> 2 -> 3 ->

        cll.insertBeginning(0);
        cll.display(); // Output: 0 -> 1 -> 2 -> 3 ->

        cll.insertAfter(2, 2.5);
        cll.display(); // Output: 0 -> 1 -> 2 -> 2.5 -> 3 ->

        cll.deleteByKey(2);
        cll.display(); // Output: 0 -> 1 -> 2.5 -> 3 ->

        System.out.println("Search for 2: " + cll.search(2));    // Output: false
        System.out.println("Search for 2.5: " + cll.search(2.5)); // Output: true
    }
}

Complexity Cheat Sheet

Operation	Best Case	Average Case	Worst Case	Space Complexity
Insertion (Beginning)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Insertion (End)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Insertion (After Node)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Deletion (Beginning / End)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Deletion (By Key)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Search (By Value)	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Cyclic Traversal	$O(n)$	$O(n)$	$O(n)$	$O(1)$
Overall Storage	-	-	-	$O(n)$

Conclusion

Circular Linked Lists are versatile data structures that allow for efficient cyclic traversals. While most operations have a time complexity of O(n) due to the need to traverse the list, they offer the advantage of not having a null reference at the end, which can be beneficial in certain applications like implementing round-robin schedulers or circular queues.

Track Your Progress

Done with this topic? Mark it as complete to track your progress.

💬 Discuss this page

Have a question or spot something confusing in "Circular Linked List Data Structure"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.

Introduction to Circular Linked List​

Video Explanation​

Circular LinkedList Operations​

Pseudocode​

Basic Operations​

Implementation in Python, C++, and Java​

Python Implementation​

C++ Implementation​

Java Implementation​

Complexity Cheat Sheet​

Conclusion​