Circular Linked Lists in Data Structures

Circular Linked Lists in Data Structures

06 Jun 2024
Intermediate
5.62K Views
69 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

Circular Linked Lists in Data Structures: An Overview

We know that in a linked list the last node pointer points to NULL. Whereas in a circular linked list, all nodes are connected to form a circle. In this DSA tutorial, we will see the circular linked list data structure in detail i.e. its features, working, implementation, etc.To further enhance your understanding and application of linked list concepts, consider enrolling in the best Data Structures and Algorithms Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

Before moving forward make sure you are up to date with the concepts of Linked Lists and Doubly Linked Lists

What is a Circular Linked List in Data Structures?

A
circular linked list is a variation of linked lists where the pointer of the last node instead of pointing to NULL points to the first or the head node. This connects the first node with the last node resulting in a circle of interconnected nodes. There is no NULL at the end. We can traverse a circular linked list until we reach the same node where we started as there is no beginning and no ending.

Representation of a Circular Linked List in Data Structures

Representation of a Circular Linked List in Data Structures

You can see that a circular linked list is represented similarly to the
Linked Lists, with one additional care to connect the last node to the first Node.

If you are still not good at pointers, please refer to the Pointers in C++ tutorial and come back.

Types of Circular Linked Lists in Data Structures

There are two types of circular linked Lists in Data Structures:
  1. Circular Singly Linked List: Here, each node has only one pointer i.e. next pointer. The next pointer of the last node of the list points to the first node of the list creating a circular structure. We can transverse only in one direction in a circular manner in this.

  2. Circular Singly Linked Lists in Data Structures
  3. Doubly Circular Linked List: We saw there are two pointers, prev and next in the doubly linked lists in data structures. In this type also each node has two pointers, prevpoints to the previous node, and the next points to the next node. Here, in addition to the last node's next pointer storing the address of the first node, even the first node's prev pointer will store the address of the last node thus forming a circular structure.

    Doubly Circular Linked List

Read More - Data Structure Interview Questions for Experienced

How to declare/create a Circular Linked List in Data Structures?

Syntax to Declare a Circular Linked List in Different Languages


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

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

struct node
{
  int data;
  struct node *next;
};
    

Example of Creating a Circular Linked List in Data Structures


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

# Initialize nodes
last = None
one = Node(10)
two = Node(20)
three = Node(30)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save address of third node in last
last = three
    

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

# Initialize nodes
last = None
one = Node(10)
two = Node(20)
three = Node(30)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save address of third node in last
last = three
    

#include 

// Define the node structure
struct Node {
    int data;
    Node* next;
};

int main() {
    // Initialize nodes
    Node *last;
    Node *one = nullptr;
    Node *two = nullptr;
    Node *three = nullptr;

    // Allocate memory
    one = new Node;
    two = new Node;
    three = new Node;

    // Assign data values
    one->data = 10;
    two->data = 20;
    three->data = 30;

    // Connect nodes
    one->next = two;
    two->next = three;
    three->next = one;

    // Save address of third node in last
    last = three;

  // clean up memory
    delete one;
    delete two;
    delete three;

    return 0;
}
    
In the above code,
one, two, and three are the nodes with data items 10, 20, and 30 respectively.
  • For node one, the pointer next stores the address of two.
  • For node two, the pointer next stores the address of three.
  • For node three, the next points to node one.

Standard Operations on Circular Linked Lists in Data Structures

  1. Insertion

Circular Linked Lists in Data Structures

Adding a node to a circular linked list is similar to adding a node to a linked list. The only extra work is to connect the last node with the first node. In the above given circular linked list, Insertion can be done in three ways:
  1. Insertion at the beginning: Let us understand this with an illustration. Suppose we want to insert a node with the value 6 at the beginning of the given circular linked list. The following three steps to accomplish this operation:
    1. Create a new node
      • allocate memory for new Node
      • assign the data to the new Node.

    2. New Node
    3. store the address of the current first node in the new Node (i.e. pointing the new Node to the current first node)
    4. point the last node to new Node (i.e making new Node as head)
    5. Insertion at the beginning

    Example of Insertion at the beginning of a Circular Linked List

    
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class CircularLinkedList:
        def __init__(self):
            self.last = None  # Pointer to the last Node of the Circular Linked List.
    
        def add_begin(self, data):
            if self.last is None:
                return self.add_to_empty(data)
    
            new_node = Node(data)
            new_node.next = self.last.next
            self.last.next = new_node
    
            return self.last
    
        def add_to_empty(self, data):
            if self.last is not None:
                return self.last  # The list is not empty
    
            new_node = Node(data)
            self.last = new_node
            self.last.next = self.last  # Linking back to itself in a circular manner
            return self.last
    
        def display_list(self, message="Circular Linked List"):
            if self.last is None:
                print("The list is empty")
                return
    
            print(message + ": ", end="")
            current_node = self.last.next
            while True:
                print(current_node.data, end=" ")
                current_node = current_node.next
                if current_node == self.last.next:
                    break
            print()
    
    
    circular_linked_list = CircularLinkedList()
    
    # Creating a circular linked list with data 1, 2, and 3
    circular_linked_list.add_to_empty(3)
    circular_linked_list.add_begin(2)
    circular_linked_list.add_begin(1)
    
    # Display the circular linked list before addition
    circular_linked_list.display_list("Before Insertion")
    
    # Adding a node with data 6 to the beginning
    circular_linked_list.add_begin(6)
    
    # Display the circular linked list after addition
    circular_linked_list.display_list("After Insertion")
        
    
    class Node {
        int data;
        Node next;
    
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    class CircularLinkedList {
        Node last;
    
        public CircularLinkedList() {
            last = null;
        }
    
        public Node addBegin(int data) {
            if (last == null) {
                return addToEmpty(data);
            }
    
            Node newNode = new Node(data);
            newNode.next = last.next;
            last.next = newNode;
    
            return last;
        }
    
        public Node addToEmpty(int data) {
            if (last != null) {
                return last; // The list is not empty
            }
    
            Node newNode = new Node(data);
            last = newNode;
            last.next = last; // Linking back to itself in a circular manner
            return last;
        }
    
        public void displayList(String message) {
            if (last == null) {
                System.out.println("The list is empty");
                return;
            }
    
            System.out.print(message + ": ");
            Node current = last.next;
            do {
                System.out.print(current.data + " ");
                current = current.next;
            } while (current != last.next);
            System.out.println();
        }
    
        public static void main(String[] args) {
            CircularLinkedList circularLinkedList = new CircularLinkedList();
    
            // Creating a circular linked list with data 1, 2, and 3
            circularLinkedList.addToEmpty(1);
            circularLinkedList.addBegin(2);
            circularLinkedList.addBegin(3);
    
            // Display the circular linked list before addition
            circularLinkedList.displayList("Before Insertion");
    
            // Adding a node with data 6 to the beginning
            circularLinkedList.addBegin(6);
    
            // Display the circular linked list after addition
            circularLinkedList.displayList("After Insertion");
        }
    }
        
    
    #include <iostream>
    
    class Node {
    public:
        int data;
        Node* next;
    
        Node(int data) : data(data), next(nullptr) {}
    };
    
    class CircularLinkedList {
    private:
        Node* last;
    
    public:
        CircularLinkedList() : last(nullptr) {}
    
        Node* addBegin(int data) {
            if (last == nullptr) {
                return addToEmpty(data);
            }
    
            Node* newNode = new Node(data);
            newNode->next = last->next;
            last->next = newNode;
    
            return last;
        }
    
        Node* addToEmpty(int data) {
            if (last != nullptr) {
                return last; // The list is not empty
            }
    
            Node* newNode = new Node(data);
            last = newNode;
            last->next = last; // Linking back to itself in a circular manner
            return last;
        }
    
        void displayList(const std::string& message) {
            if (last == nullptr) {
                std::cout << "The list is empty" << std::endl;
                return;
            }
    
            std::cout << message << ": ";
            Node* current = last->next;
            do {
                std::cout << current->data << " ";
                current = current->next;
            } while (current != last->next);
            std::cout << std::endl;
        }
    };
    
    int main() {
        CircularLinkedList circularLinkedList;
    
        // Creating a circular linked list with data 1, 2, and 3
        circularLinkedList.addToEmpty(1);
        circularLinkedList.addBegin(2);
        circularLinkedList.addBegin(3);
    
        // Display the circular linked list before addition
        circularLinkedList.displayList("Before Insertion");
    
        // Adding a node with data 6 to the beginning
        circularLinkedList.addBegin(6);
    
        // Display the circular linked list after addition
        circularLinkedList.displayList("After Insertion");
    
        return 0;
    }
        

    Output

    Before Insertion: 1 2 3 
    After Insertion: 6 1 2 3   
  2. Insertion at a specific position/in between the nodes: Suppose we want to insert a node with value 6 after the head node with value 1 in the given circular linked list. The following three steps to accomplish this operation:
    1. travel to the node given i.e. node 1
    2. point the next of new Node to the node next to node 1
    3. store the address of the new Node at the next of node 1.
    4. Insertion at a specific position/in between the nodes

    Example of Insertion in Between or at a Given Position in a Circular Linked List

    
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class CircularLinkedList:
        def __init__(self):
            self.last = None
    
        def add_after(self, data, item):
            if self.last is None:
                return None
    
            temp, P = None, self.last.next
            while True:
                if P.data == item:
                    temp = Node(data)
                    temp.next = P.next
                    P.next = temp
    
                    if P == self.last:
                        self.last = temp
                    return self.last
                P = P.next
                if P == self.last.next:
                    print(item, "not present in the list.")
                    break
    
        def display_list(self, message):
            if self.last is None:
                print("The list is empty")
                return
    
            print(message + ": ", end="")
            current = self.last.next
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.last.next:
                    break
            print()
    
    circular_linked_list = CircularLinkedList()
    
    # Creating a circular linked list with data 1, 2, and 3
    circular_linked_list.last = Node(1)
    circular_linked_list.last.next = circular_linked_list.last  # Pointing to itself initially
    
    circular_linked_list.add_after(2, 1)
    circular_linked_list.add_after(3, 2)
    
    # Display the circular linked list before insertion
    circular_linked_list.display_list("Before Insertion")
    
    # Adding a node with data 6 after node with data 1
    circular_linked_list.add_after(6, 1)
    
    # Display the circular linked list after insertion
    circular_linked_list.display_list("After Insertion")
        
    
    class Node {
        int data;
        Node next;
    
        public Node(int val) {
            data = val;
            next = null;
        }
    }
    
    class CircularLinkedList {
        Node last;
    
        public Node addAfter(Node last, int data, int item) {
            if (last == null)
                return null;
    
            Node temp, P;
            P = last.next;
            do {
                if (P.data == item) {
                    temp = new Node(data);
                    temp.next = P.next;
                    P.next = temp;
    
                    if (P == last)
                        last = temp;
                    return last;
                }
                P = P.next;
            } while (P != last.next);
    
            System.out.println(item + " not present in the list.");
            return last;
        }
    
        public void displayList(String message) {
            if (last == null) {
                System.out.println("The list is empty");
                return;
            }
    
            System.out.print(message + ": ");
            Node current = last.next;
            do {
                System.out.print(current.data + " ");
                current = current.next;
            } while (current != last.next);
            System.out.println();
        }
    
        public static void main(String[] args) {
            CircularLinkedList circularLinkedList = new CircularLinkedList();
    
            // Creating a circular linked list with data 1, 2, and 3
            circularLinkedList.last = new Node(3);
            circularLinkedList.last.next = circularLinkedList.last;  // Pointing to itself initially
    
            circularLinkedList.addAfter(circularLinkedList.last, 2, 3);
            circularLinkedList.addAfter(circularLinkedList.last, 1, 3);
    
            // Display the circular linked list before insertion
            circularLinkedList.displayList("Before Insertion");
    
            // Adding a node with data 6 after node with data 1
            circularLinkedList.addAfter(circularLinkedList.last, 6, 1);
    
            // Display the circular linked list after insertion
            circularLinkedList.displayList("After Insertion");
        }
    }
        
    
    #include <iostream>
    
    // Node structure for the Circular Linked List
    struct Node {
        int data;
        Node* next;
    
        // Constructor
        Node(int val) : data(val), next(nullptr) {}
    };
    
    // Function to add a node after a specific node
    Node* addAfter(Node* last, int data, int item) {
        if (last == nullptr)
            return nullptr;
    
        Node* temp, *P;
        P = last->next;
        do {
            if (P->data == item) {
                temp = new Node(data);
                temp->next = P->next;
                P->next = temp;
    
                if (P == last)
                    last = temp;
                return last;
            }
            P = P->next;
        } while (P != last->next);
    
        std::cout << item << " not present in the list." << std::endl;
        return last;
    }
    
    // Function to display the Circular Linked List
    void displayList(Node* last, const std::string& message) {
        if (last == nullptr) {
            std::cout << "The list is empty" << std::endl;
            return;
        }
    
        std::cout << message << ": ";
        Node* current = last->next;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != last->next);
        std::cout << std::endl;
    }
    
    int main() {
        Node* last = nullptr;
    
        // Creating a circular linked list with data 1, 2, and 3
        last = new Node(1);
        last->next = last;  // Pointing to itself initially
    
        last = addAfter(last, 2, 1);
        last = addAfter(last, 3, 2);
    
        // Display the circular linked list before insertion
        displayList(last, "Before Insertion");
    
        // Adding a node with data 6 after node with data 1
        last = addAfter(last, 6, 1);
    
        // Display the circular linked list after insertion
        displayList(last, "After Insertion");
    
        // Clean up memory (optional in this example)
        delete last;
    
        return 0;
    }
        

    Output

    Before Insertion: 1 2 3 
    After Insertion: 1 6 2 3     
  3. Insertion at the end: Suppose we want to insert a node with value 6 after the last node with value 3 in the given circular linked list. The following three steps to accomplish this operation:
    1. store the address of the head node to the next of new Node (making new Node the last node)
    2. point the current last node to new Node
    3. make new Node as the last node
    4. Insertion at the end

    Example of Insertion at the End of a Circular Linked List

    
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class CircularLinkedList:
        def __init__(self):
            self.last = None
    
        def add_end(self, data):
            if self.last is None:
                return None
    
            new_node = Node(data)
    
            new_node.next = self.last.next
            self.last.next = new_node
            self.last = new_node
    
            return self.last
    
        def display_list(self, message):
            if self.last is None:
                print("The list is empty")
                return
    
            print(message + ": ", end="")
            current = self.last.next
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.last.next:
                    break
            print()
    
    circular_linked_list = CircularLinkedList()
    
    # Creating a circular linked list with data 1, 2, and 3
    circular_linked_list.last = Node(1)
    circular_linked_list.last.next = circular_linked_list.last  # Pointing to itself initially
    
    circular_linked_list.add_end(2)
    circular_linked_list.add_end(3)
    
    # Display the circular linked list before addition
    circular_linked_list.display_list("Before Insertion")
    
    # Adding a node with data 6 at the end
    circular_linked_list.add_end(6)
    
    # Display the circular linked list after addition
    circular_linked_list.display_list("After Insertion")
        
    
    class Node {
        int data;
        Node next;
    
        public Node(int val) {
            data = val;
            next = null;
        }
    }
    
    class CircularLinkedList {
        Node last;
    
        public Node addEnd(Node last, int data) {
            if (last == null)
                return null;
    
            Node newNode = new Node(data);
    
            newNode.next = last.next;
            last.next = newNode;
            last = newNode;
    
            return last;
        }
    
        public void displayList(String message) {
            if (last == null) {
                System.out.println("The list is empty");
                return;
            }
    
            System.out.print(message + ": ");
            Node current = last.next;
            do {
                System.out.print(current.data + " ");
                current = current.next;
            } while (current != last.next);
            System.out.println();
        }
    
        public static void main(String[] args) {
            CircularLinkedList circularLinkedList = new CircularLinkedList();
    
            // Creating a circular linked list with data 1, 2, and 3
            circularLinkedList.last = new Node(1);
            circularLinkedList.last.next = circularLinkedList.last;  // Pointing to itself initially
    
            circularLinkedList.addEnd(circularLinkedList.last, 2);
            circularLinkedList.addEnd(circularLinkedList.last, 3);
    
            // Display the circular linked list before addition
            circularLinkedList.displayList("Before Insertion");
    
            // Adding a node with data 6 at the end
            circularLinkedList.addEnd(circularLinkedList.last, 6);
    
            // Display the circular linked list after addition
            circularLinkedList.displayList("After Insertion");
        }
    }
        
    
    #include <iostream>
    
    // Node structure for the Circular Linked List
    struct Node {
        int data;
        Node* next;
    
        // Constructor
        Node(int val) : data(val), next(nullptr) {}
    };
    
    // Function to add a node at the end
    Node* addEnd(Node* last, int data) {
        if (last == nullptr)
            return nullptr;
    
        Node* newNode = new Node(data);
    
        newNode->next = last->next;
        last->next = newNode;
        last = newNode;
    
        return last;
    }
    
    // Function to display the Circular Linked List
    void displayList(Node* last, const std::string& message) {
        if (last == nullptr) {
            std::cout << "The list is empty" << std::endl;
            return;
        }
    
        std::cout << message << ": ";
        Node* current = last->next;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != last->next);
        std::cout << std::endl;
    }
    
    int main() {
        Node* last = nullptr;
    
        // Creating a circular linked list with data 1, 2, and 3
        last = new Node(1);
        last->next = last;  // Pointing to itself initially
    
        last = addEnd(last, 2);
        last = addEnd(last, 3);
    
        // Display the circular linked list before addition
        displayList(last, "Before Insertion");
    
        // Adding a node with data 6 at the end
        last = addEnd(last, 6);
    
        // Display the circular linked list after addition
        displayList(last, "After Insertion");
    
        // Clean up memory (optional in this example)
        delete last;
    
        return 0;
    }
        

    Output

    Before Insertion: 1 2 3 
    After Insertion: 1 2 3 6    

  1. Deletion

Circular Linked Lists in Data Structures

In the above given circular linked list, deletion can also be done in three ways:
  1. If it's the only node: Follow the given two steps procedure
    1. free the memory occupied by the node
    2. store NULL in the last
  2. If it's the last node: Follow the given four steps procedure
    1. find the node before the last node (let it be temp)
    2. store the address of the node next to the last node in temp
    3. free the memory of the last
    4. make temp the last node
    5. If it's the last node

  3. If it's any other node: Follow the given four steps procedure
    1. travel to the node to be deleted (here we are deleting node two)
    2. Let the node before node two be temp
    3. store the address of the node next to two in temp
    4. free the memory of two
    5. If it's any other node

  4. Example of Deletion Operation in a Circular Linked List

    
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class CircularLinkedList:
        def __init__(self):
            self.last = None
    
        def push(self, data):
            ptr1 = Node(data)
            ptr1.next = self.last
    
            if self.last is not None:
                temp = self.last
                while temp.next != self.last:
                    temp = temp.next
                temp.next = ptr1
            else:
                ptr1.next = ptr1
    
            self.last = ptr1
    
        def print_list(self):
            temp = self.last
            if self.last is not None:
                while True:
                    print(temp.data, end=" ")
                    temp = temp.next
                    if temp == self.last:
                        break
            print()
    
        def delete_node(self, key):
            if self.last is None:
                return
    
            if self.last.data == key and self.last.next == self.last:
                self.last = None
                return
    
            temp = self.last
            d = None
    
            if self.last.data == key:
                while temp.next != self.last:
                    temp = temp.next
    
                temp.next = self.last.next
                self.last = temp.next
                return
    
            while temp.next != self.last and temp.next.data != key:
                temp = temp.next
    
            if temp.next.data == key:
                d = temp.next
                temp.next = d.next
            else:
                print("No such key found")
    
    
    # Creating a circular linked list with data 1, 2, and 3
    circular_linked_list = CircularLinkedList()
    circular_linked_list.push(3)
    circular_linked_list.push(2)
    circular_linked_list.push(1)
    
    # Display the circular linked list before deletion
    print("List Before Deletion:", end=" ")
    circular_linked_list.print_list()
    
    # Deleting the first node
    circular_linked_list.delete_node(1)
    
    # Display the circular linked list after deletion
    print("List after deletion of first node:", end=" ")
    circular_linked_list.print_list()
    
    circular_linked_list.push(1)
    
    # Deleting a node in between (node with data 2)
    circular_linked_list.delete_node(2)
    
    # Display the circular linked list after deletion
    print("List after deletion of an inner node:", end=" ")
    circular_linked_list.print_list()
    
    # Deleting the last node
    circular_linked_list.delete_node(3)
    
    # Display the circular linked list after deletion
    print("List after deletion of last node:", end=" ")
    circular_linked_list.print_list()
        
    
    class Node {
        int data;
        Node next;
    
        // Constructor
        Node(int val) {
            data = val;
            next = null;
        }
    }
    
    class CircularLinkedList {
        Node last;
    
        // Function to insert a node at the beginning of
        // a Circular linked list
        void push(int data) {
            Node ptr1 = new Node(data);
            ptr1.next = last;
    
            if (last != null) {
                Node temp = last;
                while (temp.next != last)
                    temp = temp.next;
                temp.next = ptr1;
            } else {
                ptr1.next = ptr1;
            }
    
            last = ptr1;
        }
    
        // Function to print nodes in a given
        // circular linked list
        void printList() {
            Node temp = last;
            if (last != null) {
                do {
                    System.out.print(temp.data + " ");
                    temp = temp.next;
                } while (temp != last);
            }
    
            System.out.println();
        }
    
        // Function to delete a given node from the list
        void deleteNode(int key) {
            if (last == null)
                return;
    
            if (last.data == key && last.next == last) {
                last = null;
                return;
            }
    
            Node temp = last;
            Node d;
    
            if (last.data == key) {
                while (temp.next != last)
                    temp = temp.next;
    
                temp.next = last.next;
                last = temp.next;
                return;
            }
    
            while (temp.next != last && temp.next.data != key) {
                temp = temp.next;
            }
    
            if (temp.next.data == key) {
                d = temp.next;
                temp.next = d.next;
            } else {
                System.out.println("No such key found");
            }
        }
    
        public static void main(String[] args) {
            CircularLinkedList circularLinkedList = new CircularLinkedList();
    
            // Creating a circular linked list with data 1, 2, and 3
            circularLinkedList.push(3);
            circularLinkedList.push(2);
            circularLinkedList.push(1);
    
            // Display the circular linked list before deletion
            System.out.print("List Before Deletion: ");
            circularLinkedList.printList();
    
            // Deleting the first node
            circularLinkedList.deleteNode(1);
    
            // Display the circular linked list after deletion
            System.out.print("List after deletion of first node: ");
            circularLinkedList.printList();
    
            circularLinkedList.push(1);
    
            // Deleting a node in between (node with data 2)
            circularLinkedList.deleteNode(2);
    
            // Display the circular linked list after deletion
            System.out.print("List after deletion of an inner node: ");
            circularLinkedList.printList();
    
            // Deleting the last node
            circularLinkedList.deleteNode(3);
    
            // Display the circular linked list after deletion
            System.out.print("List after deletion of last node: ");
            circularLinkedList.printList();
        }
    }
        
    
    #include <iostream>
    
    class Node {
    public:
        int data;
        Node* next;
    
        // Constructor
        Node(int val) : data(val), next(nullptr) {}
    };
    
    void push(Node** head_ref, int data) {
        Node* ptr1 = new Node(data);
        ptr1->next = *head_ref;
    
        if (*head_ref != nullptr) {
            Node* temp = *head_ref;
            while (temp->next != *head_ref)
                temp = temp->next;
            temp->next = ptr1;
        } else {
            ptr1->next = ptr1;
        }
    
        *head_ref = ptr1;
    }
    
    void printList(Node* head) {
        Node* temp = head;
        if (head != nullptr) {
            do {
                std::cout << temp->data << " ";
                temp = temp->next;
            } while (temp != head);
        }
    
        std::cout << std::endl;
    }
    
    void deleteNode(Node** head, int key) {
        if (*head == nullptr)
            return;
    
        if ((*head)->data == key && (*head)->next == *head) {
            delete *head;
            *head = nullptr;
            return;
        }
    
        Node* last = *head;
        Node* d;
    
        if ((*head)->data == key) {
            while (last->next != *head)
                last = last->next;
    
            last->next = (*head)->next;
            delete *head;
            *head = last->next;
            return;
        }
    
        while (last->next != *head && last->next->data != key) {
            last = last->next;
        }
    
        if (last->next->data == key) {
            d = last->next;
            last->next = d->next;
            delete d;
        } else {
            std::cout << "No such key found" << std::endl;
        }
    }
    
    int main() {
        Node* head = nullptr;
    
        // Creating a circular linked list with data 1, 2, and 3
        push(&head, 3);
        push(&head, 2);
        push(&head, 1);
    
        // Display the circular linked list before deletion
        std::cout << "List Before Deletion: ";
        printList(head);
    
        // Deleting the first node
        deleteNode(&head, 1);
    
        // Display the circular linked list after deletion
        std::cout << "List after deletion of first node: ";
        printList(head);
        
             push(&head, 1);
        // Deleting a node in between (node with data 2)
        deleteNode(&head, 2);
    
        // Display the circular linked list after deletion
        std::cout << "List after deletion of an inner node: ";
        printList(head);
        
        //  Deleting the last node
        deleteNode(&head, 3);
    
        // Display the circular linked list after deletion
        std::cout << "List after deletion of last node: ";
        printList(head);
    
        return 0;
    }
        

    Output

    List Before Deletion: 1 2 3 
    List after deletion of first node: 2 3 
    List after deletion of an inner node: 1 3 
    List after deletion of last node: 1
    

  1. Traversal

We can access each element of the circular linked list starting from the
head node until we reach back to it.

Example of Traversing a Circular Linked List


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

# Function to traverse and print the Circular Linked List
def display_list(last):
    if last is None:
        print("The list is empty")
        return

    current = last.next
    while True:
        print(current.data, end=" ")
        current = current.next
        if current == last.next:
            break
    print()

# Initialize nodes
last = None
one = Node(1)
two = Node(2)
three = Node(3)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save the address of the third node in last
last = three

# Displaying the circular linked list
display_list(last)
    

class Node {
    int data;
    Node next;

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

class CircularLinkedList {
    // Function to traverse and print the Circular Linked List
    static void displayList(Node last) {
        if (last == null) {
            System.out.println("The list is empty");
            return;
        }

        Node current = last.next;
        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != last.next);

        System.out.println();
    }

    public static void main(String[] args) {
        // Initialize nodes
        Node last = null;
        Node one = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);

        // Connect nodes
        one.next = two;
        two.next = three;
        three.next = one;

        // Save the address of the third node in last
        last = three;

        // Displaying the circular linked list
        displayList(last);
    }
}
    

#include <iostream>

// Define the node structure
struct Node {
    int data;
    Node* next;
};

// Function to traverse and print the Circular Linked List
void displayList(Node* last) {
    if (last == nullptr) {
        std::cout << "The list is empty" << std::endl;
        return;
    }

    Node* current = last->next;
    do {
        std::cout << current->data << " ";
        current = current->next;
    } while (current != last->next);

    std::cout << std::endl;
}

int main() {
    // Initialize nodes
    Node* last = nullptr;
    Node* one = nullptr;
    Node* two = nullptr;
    Node* three = nullptr;

    // Allocate memory
    one = new Node;
    two = new Node;
    three = new Node;

    // Assign data values
    one->data = 1;
    two->data = 2;
    three->data = 3;

    // Connect nodes
    one->next = two;
    two->next = three;
    three->next = one;

    // Save the address of the third node in last
    last = three;

    // Displaying the circular linked list
    displayList(last);

    // Clean up memory
    delete one;
    delete two;
    delete three;

    return 0;
}
    

Output

1 2 3     

Complexity Analysis of Circular Linked List Operations

OperationsTime ComplexitySpace Complexity
Insertion

O(1) or O(N)

O(1)

Deletion

O(1)

O(1)

Traversal

O(N)

O(1)

Applications of Circular Linked List

  1. This is used in multiplayer games to give each participant a chance to play.
  2. In an operating system, a circular linked list can be used to organize many running applications.
  3. In resource allocation difficulties, circular linked lists might be useful.
  4. Circular linked lists are frequently used to build circular buffers.
  5. They can also be used in simulation and gaming.

Advantages of Circular Linked Lists

  1. Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
  2. Useful for the implementation of a queue. Unlike this implementation, we don’t need to maintain two-pointers for the front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.
  3. Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
  4. Circular Doubly Linked Lists are used for the implementation of advanced data structures like the Fibonacci Heap.
  5. Implementing a circular linked list can be relatively easy compared to other more complex data structures like trees or graphs.

Disadvantages of Circular Linked Lists

  1. Compared to singly linked lists, circular lists are more complex.
  2. Reversing a circular list is more complicated than reversing a singly or doubly linked list.
  3. The code can go into an infinite loop if it is not handled carefully.
  4. It is harder to find the end of the list and control the loop.
  5. Although circular linked lists can be efficient in certain applications, their performance can be slower than other data structures in certain cases, such as when the list needs to be sorted or searched.
  6. Circular linked lists don’t provide direct access to individual nodes.
Summary

So, here we saw every aspect of a circular linked list in data structures. You might have got at least some idea regarding circular linked lists and their applications. I know it's quite difficult and tricky to understand the whole topic in a single go. There are a lot of concepts and logic to be understood in this. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Best Data Structures And Algorithms Course.

FAQs

Q1. What is a Circular Linked List?

A circular linked list is a variation of linked lists where the pointer of the last node instead of pointing to NULL points to the first or the head node. This connects the first node with the last node resulting in a circle of interconnected nodes.

Q2. How many types of Circular Linked Lists are there?

There are two types of circular linked Lists in Data Structures.

Q3. Are circular linked lists easy to implement than trees or graphs?

Implementing a circular linked list can be relatively easy compared to other more complex data structures like trees or graphs.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
Angular Certification Course Jun 22 SAT, SUN
Filling Fast
09:30AM to 11:30AM (IST)
Get Details
ASP.NET Core (Project) Jun 23 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Azure Developer Certification Training Jun 23 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
.NET Microservices Certification Training Jun 23 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Solution Architect Certification Training Jun 23 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Full Stack .Net Developer Jun 30 SAT, SUN
Filling Fast
11:00AM to 01:00PM (IST)
Get Details
ASP.NET Core Certification Training Jun 30 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
React JS Certification Training | Best React Training Course Jun 30 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jun 30 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Generative AI For Software Developers Jul 14 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this