Circular Linked List in Data Structure: Types & its Implementation

A Circular Linked List (CLL) is a data structure in which a group of nodes are connected to form a circle, where the last node points back to the first node. This means that there is no terminating null pointer at the end of the list.

The two main types of circular linked lists are:

1. Circular Singly Linked List

In a Circular Singly Linked List, each node points to the next node, and the last node points back to the first node. It allows one-way traversal, i.e., you can traverse the list from the head node to the last node and back to the head.

2. Circular Doubly Linked List

A Circular Doubly Linked List is more advanced as each node contains two pointers where one pointing to the next node and another pointing to the previous node. The last node points to the head, and the head points to the last node, forming a circle.

Here are the basic operations performed on the circular linked list:

1. Insertion

• Insert at the beginning
• Insert at the end
• Insert after a given node

2. Deletion

• Delete the first node
• Delete the last node
• Delete a specific node

3. Traversal

Traverse all nodes starting from a given node and looping back to the start.

4. Searching

Find a specific node in the circular linked list.

Here is the implementation of a circular linked list in data structures in C, C++, and Java:

C code

#include <stdio.h>
#include <stdlib.h>


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


struct Node* head = NULL;


// Function to insert at the beginning
void insertAtBeginning(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (head == NULL) {
        newNode->next = newNode;  // Point to itself if it's the only node
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        head = newNode;
    }
}


// Function to insert at the end
void insertAtEnd(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (head == NULL) {
        newNode->next = newNode;
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
    }
}


// Function to display the circular linked listvoid displayList() {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}


int main() {
    insertAtBeginning(10);
    insertAtBeginning(20);
    insertAtEnd(30);
    insertAtEnd(40);
    displayList();  // Output: 20 -> 10 -> 30 -> 40 -> (head)
    return 0;
}

C++ Code

#include <iostream>
using namespace std;


class CircularLinkedList {
public:
    struct Node {
        int data;
        Node* next;
    };
    Node* head;


    CircularLinkedList() {
        head = nullptr;
    }
     // Function to insert at the beginning
    void insertAtBeginning(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        if (!head) {
            newNode->next = newNode;
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != head) temp = temp->next;
            temp->next = newNode;
            newNode->next = head;
            head = newNode;
        }
    }


    // Function to insert at the end
    void insertAtEnd(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        if (!head) {
            newNode->next = newNode;
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != head) temp = temp->next;
            temp->next = newNode;
            newNode->next = head;
        }
    }


    // Function to display the circular linked list
    void displayList() {
        if (!head) {
            cout << "List is empty.\n";
            return;
        }
        Node* temp = head;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        cout << "(head)" << endl;
    }
};


int main() {
    CircularLinkedList cll;
    cll.insertAtBeginning(10);
    cll.insertAtBeginning(20);
    cll.insertAtEnd(30);
    cll.insertAtEnd(40);
    cll.displayList();  // Output: 20 -> 10 -> 30 -> 40 -> (head)
    return 0;
}

Java Code

class CircularLinkedList {
    static class Node {
        int data;
        Node next;


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


    private Node head = null;


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


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


    // Display the list
    public void displayList() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(head)");
    }


    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.insertAtBeginning(10);
        cll.insertAtBeginning(20);
        cll.insertAtEnd(30);
        cll.insertAtEnd(40);
        cll.displayList();  // Output: 20 -> 10 -> 30 -> 40 -> (head)
    }
}

Here are the advantages and disadvantages of a circular linked list in data structures:

Advantages

• A circular linked list allows for continuous traversal from any node, without encountering a null value or reaching the end of the list.
• Insertion and deletion operations can be performed efficiently, as the last node’s next pointer points back to the first node, eliminating the need to traverse the entire list.
• Finding the end of the list or loop control is easier, as there are no null values to mark the beginning and end.
• Circular linked lists are suitable for Round-Robin scheduling algorithms, where processes are queued circularly. 
• Circular linked lists can be used to implement Fibonacci heaps, a specialized data structure for priority queues.

Disadvantages

• Circular linked lists are more complex than singly linked lists, as they require additional logic to handle the circular structure.
• Reversing a circular linked list is more challenging than reversing a singly or doubly linked list, as it requires careful handling of the circular structure.
• If not handled correctly, circular linked lists can lead to infinite loops during traversal or insertion/deletion operations.
• Finding the end of the list or loop control can be harder than in a singly linked list, as there are no explicit null values to mark the beginning and end.
• Circular linked lists do not support direct access to elements, as the next pointer of each node only points to the next node in the circular sequence.

Here are the applications that use circular linked lists in real life:

1. Round Robin Scheduling

Circular Linked Lists are used in scheduling algorithms like round-robin scheduling, where each process is allocated a fixed time slot in a cyclic manner.

2. Memory Management

In memory management systems, Circular Linked Lists are used to manage memory blocks in a circular fashion, which allows efficient memory reuse.

3. Game Development

In games, Circular Linked Lists are used to manage players cyclically. For example, in a multiplayer game, the turn of players can be managed using a Circular Linked List.

4. Data Buffering

Circular Linked Lists are often used in buffering data in networking applications where the buffer is reused circularly.

In conclusion, a circular linked list is a flexible data structure with practical applications in real life. It offers insertion and deletion operations, efficient memory utilization, and suitable applications in multi-programming operating systems and games with multiple players. However, they also require more complex algorithms and can be error-prone if not implemented correctly.

1. How do you insert a new node at the beginning of a Circular Linked List? 

To insert a new node at the beginning, create a new node and make it point to the current head (which is the tail->next). Once this is done, update the current tail's next node to point to the new one. As a final step, update the head reference to point to the new node.

2. Can Circular Linked Lists be implemented using singly linked lists or doubly linked lists?

Yes, Circular Linked Lists can be implemented using either singly linked lists or doubly linked lists. The main difference is that the last node in a circular linked list points back to the first node, whereas in a regular linked list, the last node points to NULL.

3. How do you handle errors or edge cases in Circular Linked Lists?

When implementing Circular Linked Lists, it’s essential to handle errors and edge cases, such as inserting a new node at an invalid position, deleting a non-existent node, or traversing an empty list. Proper error handling and boundary checking can help prevent bugs and ensure the reliability of your implementation.