Introduction to Circular Linked List

A circular linked list is a way of organizing and storing data where the last node points to the first, forming a closed circle. It is effective for tasks such as managing memory in various applications because it can execute operations like insertion and deletion. Circular linked lists optimize code by allowing constant-time insertions and deletions (O(1)) and enabling efficient iteration without handling null references. They are particularly useful in applications like real-time systems, gaming, and networking, where cyclic data processing is required. In this blog, we will learn about circular linked lists, their types, operations performed, and applications.

• What is a Circular Linked List?
• Types of Circular Linked Lists
  • Circular Singly Linked List
  • Circular Doubly Linked List
• Operations on Circular Linked List
  • Traversal
  • Insertion
  • Deletion
• Advantages and Disadvantages of Circular Linked List
• Applications of Circular Linked List
• Concluding Thoughts
• FAQs

Explore the world of C programming with this captivating YouTube video—your gateway to a comprehensive learning experience!

What is a Circular Linked List?

The circular linked list is like a regular linked list where the last node is connected back to the first node, forming a circle. Imagine a chain where the last link connects to the first one, creating a continuous loop. This structure allows you to go through the elements of data from any point in the list.

The above image represents a circular linked list with 4 nodes. In this image, the first node comprises two components: one holding the data and the other containing the address (pointer/ptr)  pointing towards the next node. The first node in a list is commonly referred to as the “Head.” If the first node is deleted, the second node (now the first) takes on the role of the “Head.”

Nodes in the list are interconnected; for example, node 1 is linked to node 2, node 2 to node 3, and so forth. The final node (node 4 in this case) is connected back to the initial node, creating a circular linked list.

Syntax:

struct Node { 

    int data; 

    struct Node *next; 

}; 

Types of Circular Linked Lists

The circular linked list consists of two types:

• Circular Singly Linked List
• Circular Doubly Linked List

Circular Singly Linked List

A circular singly linked list is a variation of a singly linked list where the last node of the list points back to the first node, forming a circular structure. It has two components:

• Data: It holds the actual data or value that the node is storing.
• Next Pointer: It points to the next node in the sequence.

In the above image, the first node is pointing towards the second node, the second node is pointing towards the third node, and the last node is pointing back to the first node, hence forming a circle. Once we move to the next node, we cannot go back to the previous node. 

class Node {
    int data;
    Node next;

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

class CircularSinglyLinkedList {
    Node head;

    public CircularSinglyLinkedList() {
        this.head = null;
    }

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

    public void printList() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println("HEAD");
    }

    public static void main(String[] args) {
        CircularSinglyLinkedList cSLL = new CircularSinglyLinkedList();
        cSLL.append(1);
        cSLL.append(2);
        cSLL.append(3);
        cSLL.printList();
    }
}

Circular Doubly Linked List

A circular doubly linked list is a list where each node has a reference to both the next and the previous nodes. In addition to being doubly linked, the pointer of the last node points to the first node, and the pointer of the first node points to the last node, forming a circular structure.

It has three components:

• Data: Holds the actual data or value that the node is storing
• Next Pointer: Points to the next node in the sequence
• Previous Pointer: Points to the previous node in the sequence

In the above image, the first node is pointing to the next and also pointing backward to the last node. Similarly, the second node points toward the third node and also points backward to the previous node. This shows that each node is connected to both the next and previous node. 

class Node {
    int data;
    Node next;
    Node prev;

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

class CircularDoublyLinkedList {
    Node head;

    public CircularDoublyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
            head.prev = head;
        } else {
            Node tail = head.prev;
            tail.next = newNode;
            newNode.prev = tail;
            newNode.next = head;
            head.prev = newNode;
        }
    }

    public void printList() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = head;
        do {
            System.out.print(current.data + " <-> ");
            current = current.next;
        } while (current != head);
        System.out.println("HEAD");
    }

    public static void main(String[] args) {
        CircularDoublyLinkedList cDLL = new CircularDoublyLinkedList();
        cDLL.append(1);
        cDLL.append(2);
        cDLL.append(3);
        cDLL.printList();
    }
}

Operations on Circular Linked List

The main three operations that one can perform on a circular linked list are as follows: 

Traversal

To traverse a circular linked list, we need to follow these steps:

Initialize a pointer: Start with the initial node (head) of the circular linked list. Loop until the desired condition is met: Continue traversing through the list until we reach the end or until we meet a certain condition (e.g., reaching a specific node).

Update the pointer: After visiting a node, update the pointer to move to the next node in the list. Since it’s a circular list, ensure the pointer wraps around correctly to start from the beginning again after reaching the end.

Here’s a simple example in Python to demonstrate how to traverse a circular linked list:

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

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

    # Method to add nodes at the end of the list
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
        else:
            new_node = Node(data)
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
            new_node.next = self.head

    # Method to print the list
    def display(self):
        elements = []
        cur_node = self.head
        while True:
            elements.append(cur_node.data)
            cur_node = cur_node.next
            if cur_node == self.head:
                break
        return elements

# Example usage
cll = CircularLinkedList()
cll.append('A')
cll.append('B')
cll.append('C')

print("Circular Linked List:", cll.display())

Insertion

In a circular linked list, insertion involves adding a new node to the existing list. The process includes 

• creating a new node
• setting its data
• adjusting the pointers to put the new node into the circular structure

At the Beginning 

Here we will add the elements at the start of the list.

In the above image, our list already consists of two elements, i.e., 7 and 9, and we are inserting 2 at the beginning.

As a result, we have successfully inserted 2 at the beginning of the list, as shown in the figure above.

class Node {
    int data;
    Node next;

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

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

    public void insertAtStart(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            newNode.next = head.next;
            head.next = newNode;
            if (newNode.next == head) {
                tail = newNode;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList clist = new CircularLinkedList();
        clist.addNode(5);
        clist.addNode(4);
        clist.addNode(3);
        clist.addNode(2);
        clist.addNode(1);
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
        clist.insertAtStart(0); // Inserts 0 at the start
        System.out.println(clist); // Expected output: 0 -> 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
    }
}

In the Middle

Here we will add the elements in the middle of the list.

In the above image, we have elements 1 and 8, and we want to insert element 3 between these two nodes.

As a result, element 3 is successfully inserted into the circular linked list. Now the first node, i.e., element 1, will point towards the second node, i.e., element 3. 

class Node {
    int data;
    Node next;

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

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

    public void insertInMiddle(int data) {
        if (head == null) {
            head = new Node(data);
            tail = head;
            head.next = head;
        } else {
            Node newNode = new Node(data);
            Node slowPtr = head;
            Node fastPtr = head;
            do {
                fastPtr = fastPtr.next;
            } while (fastPtr!= head && fastPtr.next!= head);
            newNode.next = fastPtr.next;
            fastPtr.next = newNode;
            if (newNode.next == head) {
                tail = newNode;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList clist = new CircularLinkedList();
        clist.addNode(5);
        clist.addNode(4);
        clist.addNode(3);
        clist.addNode(2);
        clist.addNode(1);
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
        clist.insertInMiddle(6); // Inserts 6 in the middle
        System.out.println(clist); // Expected output: 5 -> 4 -> 6 -> 3 -> 2 -> 1 -> HEAD
    }
}

At the End

Here we will add the elements at the end of the list.

In the above image, we have three elements in the list and want to add the fourth element.

As a result, we have successfully inserted the fourth element at the end of the list. Now the new node will be pointing toward the 1st node.

class Node {
    int data;
    Node next;

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

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList clist = new CircularLinkedList();
        clist.addNode(5);
        clist.addNode(4);
        clist.addNode(3);
        clist.addNode(2);
        clist.addNode(1);
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
        clist.insertAtEnd(6); // Inserts 6 at the end
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> 6 -> HEAD
    }
}

Deletion

In a circular linked list, deletion refers to the process of removing a specific node from the list. The deletion process varies based on the position of the node to be removed within the list. Three main scenarios are considered: 

• deleting the head node
• deleting a node from the middle of the list
• deleting the last node 

At the Beginning

Here we will remove the elements at the start of the list.

As we have five elements in the original list, we want to delete the first element from the list.

As a result, the first element from the list has been deleted successfully.

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null; // For simplicity, assuming singly linked list
    }
}

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head; // Make it circular
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

    public void deleteFromBeginning() {
        if (head == null) return; // List is empty

        // Find the new head node
        Node current = head;
        do {
            current = current.next;
        } while (current!= head);

        // Update the head node
        head = current.next;
        tail.next = head; // Ensure the list remains circular

        // Delete the old head node
        current.next = null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList clist = new CircularLinkedList();

    clist.addNode(5);
    clist.addNode(4);
    clist.addNode(3);
    clist.addNode(2);
    clist.addNode(1);
    System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD

    // Deleting from the beginning
    clist.deleteFromBeginning();
    System.out.println(clist); // Expected output: 4 -> 3 -> 2 -> 1 -> HEAD

    }
}

In the Middle

Here we will remove the elements in between the list.

We have five elements in the list: 1, 2, 3, 4, and 5. We want deletion in the middle of the list, i.e., we want to delete the middle element “3”.

As a result, “3” has been removed from the circular linked list.

class Node {
    int data;
    Node next;

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

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

    public void deleteMiddleElement() {
        if (head == null || head.next == head) return;
        Node slowPtr = head;
        Node fastPtr = head;
        boolean found = false;
        do {
            fastPtr = fastPtr.next;
            if (fastPtr!= head) {
                found = true;
            }
            fastPtr = fastPtr.next;
        } while (fastPtr!= head &&!found);
        if (!found) {
            slowPtr = slowPtr.next;
        }
        slowPtr.next = slowPtr.next.next;
        tail.next = head;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList clist = new CircularLinkedList();
        clist.addNode(5);
        clist.addNode(4);
        clist.addNode(3);
        clist.addNode(2);
        clist.addNode(1);
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
        clist.deleteMiddleElement(); // Deletes the middle element
        System.out.println(clist); // Expected output: 5 -> 3 -> 2 -> 1 -> HEAD
    }
}

At the End

Here we will remove the elements at the end of the list.

Here, we have again five elements in the list: 1, 2, 3, 4, and 5. We want to delete the last element from the circular linked list.

As a result, we have successfully deleted the last node in the circular linked list.

class Node {
    int data;
    Node next;

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

public class CircularLinkedList {
    private Node head;
    private Node tail;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            head.next = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            tail = newNode;
        }
    }

    public void removeLastElement() {
        if (head == null) return;
        if (head.next == head) { // Only one node exists
            head = null;
            tail = null;
        } else {
            Node current = head;
            do {
                current = current.next;
            } while (current.next!= head);
            tail = current;
            tail.next = head.prev; // Set the new tail's next to the previous head
            head.prev.next = head; // Connect the previous head's next to the new head
            head.prev = null; // Reset the previous head's prev to null
            head = head.prev; // Move the head to the new head
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = head;
        do {
            sb.append(current.data).append(" -> ");
            current = current.next;
        } while (current!= head);
        sb.append("HEAD");
        return sb.toString();
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        clist.addNode(5);
        clist.addNode(4);
        clist.addNode(3);
        clist.addNode(2);
        clist.addNode(1);
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
        clist.removeLastElement(); // Removes the last element
        System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> HEAD
    }
}

Advantages and Disadvantages of Circular Linked List

Circular linked lists, both singly and doubly, have their own set of advantages and disadvantages. Here’s an overview:

Advantages

• Insertion and deletion of nodes at the beginning and end of the list can be done more efficiently compared to linear linked lists. 
• No traversal is needed to update the last node’s next pointer during insertion or deletion at the end.
• Due to the circular structure, it’s easy to traverse the entire list, starting from any node. This can be useful in certain applications where circular traversal is required.
• In certain scenarios, circular linked lists can be more memory-efficient compared to linear linked lists due to their ability to reuse the last node’s “next” pointer to connect back to the first node.

Disadvantages:

• If not implemented or managed properly, circular linked lists can lead to infinite loops during traversal. 
• The circular structure adds complexity to the implementation and operations of the linked list.
• In a singly circular linked list, accessing the previous node while traversing requires additional traversal from the head, which can be less efficient compared to doubly linked lists.
• Each node in the circular linked list requires extra space for the next (and possibly previous in the case of doubly linked lists) pointer. This can increase memory overhead, especially for large lists.

Applications of Circular Linked List

Circular linked lists find applications in various scenarios due to their unique properties. Some of the common applications include:

1. Round-Robin Scheduling: Circular linked lists are used in scheduling algorithms, such as Round-Robin in operating systems. Each node represents a process, and the circular structure ensures that each process gets an equal share of the CPU time.

2. Music Playlist: Circular linked lists can be used to implement playlists in music players. The last song’s next pointer points back to the first song, creating a continuous loop of songs to play.

3. Multiplayer Games: In multiplayer games, a circular linked list can represent the order of turns or actions among players. After the last player takes their turn, the next turn goes back to the first player.

4. File System Management: In file systems, circular linked lists can be utilized for managing free disk blocks. The last block’s next pointer can return to the first free block.

5. Simulation Systems: In simulation systems, circular linked lists are used to model scenarios where entities cyclically interact with each other. Each node in the list represents an entity, and the simulation progresses in a circular sequence. This setup allows for continuous interactions among entities, creating a dynamic and repetitive simulation environment.

Concluding Thoughts

In conclusion, circular linked lists offer a versatile data structure with applications in memory management, task scheduling, and efficient navigation. Their ability to form a closed loop facilitates constant-time insertions and deletions, making them suitable for dynamic scenarios. The future scope involves exploring optimizations for specific use cases, enhancing algorithms for circular list manipulation, and integrating advanced features into diverse domains, thereby contributing to the evolution of efficient and scalable data structures in computer science.

FAQs