Circular Linked List

Introduction

Circular Linked List represent a unique variation of the traditional linked list data structure. Unlike linear linked list, where the last node points to null, circular linked list have their last node pointing back to the first node, creating a circular structure. This circular arrangement offers distinct advantages in certain scenarios, providing efficient traversal and operations.

Definition and Overview

A Circular Linked List is a type of linked list where each node points to the next node in the sequence, and the last node points back to the first node, forming a loop. This structure eliminates the need to maintain a separate tail pointer, enabling seamless traversal from any node to any other node in constant time.

Difference between Circular Linked List and linear linked list

The key difference between Circular Linked List and linear linked list lies in their termination condition. In linear linked list, the last node points to null, indicating the end of the list. Conversely, Circular Linked List create a loop by having the last node point back to the first node, allowing continuous traversal without encountering a null pointer.

This unique circular arrangement offers advantages such as simplified insertion and deletion operations, efficient looping through the entire list, and suitability for applications requiring cyclic behavior or periodic processing. However, it also introduces complexities in certain operations, such as determining the end of the list and handling special cases like an empty list.

Node Structure

In a Circular Linked List, each node contains two main components: data and a pointer to the next node. Here’s the structure of a node in a Circular Linked List:

Node structure of Circular linked list java

public class Node {
    // Data stored in the node
    int data;

    // Pointer to the next node in the list
    Node next;

    // Constructor to initialize a node with data
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

In this structure:

• data: Represents the data stored in the node.
• next: Points to the next node in the Circular Linked List.

Since Circular Linked List have a circular structure where the last node points back to the first node, the next pointer of the last node in the list points back to the head or first node. This circular arrangement allows seamless traversal through the list without encountering a null pointer and enables efficient looping operations.

Operations

Insertion

In Circular Linked List, insertion operations can be performed at various positions within the list. Here are the main insertion scenarios along with their corresponding operations:

Insertion at the Beginning:

• To insert a node at the beginning of a Circular Linked List, follow these steps:
  • Create a new node with the given data.
  • If the list is empty, set the new node as both the head and tail of the list, and make its next pointer point to itself.
  • If the list is not empty, set the next pointer of the new node to the current head of the list.
  • Update the next pointer of the last node to point to the new node.
  • Set the new node as the new head of the list.

Insertion at the End:

• To insert a node at the end of a Circular Linked List, follow these steps:
  • Create a new node with the given data.
  • If the list is empty, set the new node as both the head and tail of the list, and make its next pointer point to itself.
  • If the list is not empty, set the next pointer of the new node to the current head of the list.
  • Update the next pointer of the current tail node to point to the new node.
  • Set the new node as the new tail of the list.

Insertion at a Specific Position:

• To insert a node at a specific position in a Circular Linked List, follow these steps:
  • Traverse the list to the node immediately before the desired position.
  • Create a new node with the given data.
  • Set the next pointer of the new node to the node at the desired position.
  • Update the next pointer of the previous node to point to the new node.

These insertion operations allow for the dynamic growth of Circular Linked List by adding nodes at different positions within the list. Each operation maintains the circular structure of the list by appropriately updating pointers to ensure continuous traversal.

Deletion

In Circular Linked List, deletion operations remove nodes from the list while maintaining its circular structure. Here are the main deletion scenarios along with their corresponding operations:

Deletion at the Beginning:

• To delete a node at the beginning of a Circular Linked List, follow these steps:
  • If the list is empty, return as there’s nothing to delete.
  • If the list has only one node, set both the head and tail pointers to null.
  • Otherwise, set the head pointer to the next node of the current head.
  • Update the next pointer of the last node to point to the new head.
  • Delete the node from memory.

Deletion at the End:

• To delete a node at the end of a Circular Linked List, follow these steps:
  • If the list is empty, return as there’s nothing to delete.
  • If the list has only one node, set both the head and tail pointers to null.
  • Otherwise, traverse the list to the node before the tail node.
  • Set the next pointer of the previous node to the head node.
  • Set the tail pointer to the previous node.
  • Delete the tail node from memory.

Deletion at a Specific Position:

• To delete a node at a specific position in a Circular Linked List, follow these steps:
  • If the list is empty, return as there’s nothing to delete.
  • If the list has only one node, set both the head and tail pointers to null.
  • Otherwise, traverse the list to the node before the node to be deleted.
  • Set the next pointer of the previous node to the next node of the node to be deleted.
  • Delete the node to be deleted from memory.

These deletion operations allow for the removal of nodes from different positions within the Circular Linked List while ensuring its circular structure is maintained. Each operation adjusts pointers appropriately to maintain the integrity of the list.

Traversal

In Circular Linked List, traversal can be performed in both forward and backward directions. Here’s how you can implement forward and backward traversal:

Forward Traversal:

• Start from the head node.
• Print the data of the current node.
• Move to the next node.
• Repeat steps 2-3 until you reach the head node again.

public void forwardTraversal() {
    if (isEmpty()) {
        System.out.println("Circular Linked List is empty");
        return;
    }

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

Backward Traversal:

• Start from the tail node.
• Print the data of the current node.
• Move to the previous node.
• Repeat steps 2-3 until you reach the tail node again.

public void backwardTraversal() {
    if (isEmpty()) {
        System.out.println("Circular Linked List is empty");
        return;
    }

    Node current = tail;
    do {
        System.out.print(current.data + " ");
        current = current.prev;
    } while (current != tail);
    System.out.println();
}

Both forward and backward traversal methods use a do-while loop to ensure that at least one iteration is performed, even if the list is initially empty. The loop continues until the current node reaches the starting point again, ensuring that all nodes in the circular list are traversed.

Special Operations

Splitting the Circular Linked List at a given node

To split a Circular Linked List at a given node, we need to find the node specified and then break the circular link by adjusting the pointers accordingly. Here’s how we can achieve this:

1. Traverse the Circular Linked List to find the given node.
2. Once the node is found, update its previous node’s next pointer to null, effectively breaking the circular link.
3. Update the tail pointer of the first part of the list to the previous node of the given node.
4. Create a new Circular Linked List with the given node as its head and the original tail as its tail.

Here’s the Java code to split a Circular Linked List at a given node:

public class CircularLinkedList {
    // Node class representing each element of the circular linked list
    private static class Node {
        int data;
        Node next;

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

    // Head and tail pointers of the circular linked list
    private Node head;
    private Node tail;

    // Method to split the circular linked list at a given node
    public void splitAtNode(int key) {
        if (head == null)
            return;

        Node current = head;
        Node prev = null;

        // Traverse the circular linked list to find the given node
        while (current.data != key) {
            if (current.next == head) {
                System.out.println("Node with key " + key + " not found");
                return;
            }
            prev = current;
            current = current.next;
        }

        // Update the next pointer of the previous node of the given node
        prev.next = null;

        // Update the tail pointer of the first part of the list
        tail = prev;

        // Create a new circular linked list with the given node as its head
        CircularLinkedList newList = new CircularLinkedList();
        newList.head = current;
        newList.tail = tail;

        // Update the next pointer of the original tail to the head of the new list
        tail.next = newList.head;
    }

    // Method to display the circular linked list
    public void display() {
        if (head == null) {
            System.out.println("Circular Linked List is empty");
            return;
        }

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

    // Main method for testing the implementation
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.head = new Node(1);
        cll.head.next = new Node(2);
        cll.head.next.next = new Node(3);
        cll.head.next.next.next = new Node(4);
        cll.head.next.next.next.next = cll.head; // Making it circular

        System.out.println("Original Circular Linked List:");
        cll.display();

        // Splitting the circular linked list at node with key 3
        cll.splitAtNode(3);

        System.out.println("Circular Linked List after splitting at node with key 3:");
        cll.display();
    }
}

This code splits the Circular Linked List at the node with the key value 3. It then displays the original list and the list after splitting at the specified node.

Merging two Circular Linked List

To merge two Circular Linked List, we need to adjust the pointers of the last node of the first list and the head node of the second list. Here’s how we can achieve this:

1. Find the last node of the first Circular Linked List.
2. Update the next pointer of the last node to point to the head node of the second Circular Linked List.
3. Update the tail pointer of the first list to the tail pointer of the second list.
4. Set the head pointer of the merged list to the head of the first list.

Here’s the Java code to merge two Circular Linked List:

public class CircularLinkedList {
    // Node class representing each element of the circular linked list
    private static class Node {
        int data;
        Node next;

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

    // Head and tail pointers of the circular linked list
    private Node head;
    private Node tail;

    // Method to merge two circular linked lists
    public void mergeLists(CircularLinkedList list1, CircularLinkedList list2) {
        if (list1.head == null) {
            head = list2.head;
            tail = list2.tail;
        } else if (list2.head == null) {
            head = list1.head;
            tail = list1.tail;
        } else {
            Node lastNodeList1 = list1.tail;
            lastNodeList1.next = list2.head;
            list2.tail.next = list1.head;
            head = list1.head;
            tail = list2.tail;
        }
    }

    // Method to display the circular linked list
    public void display() {
        if (head == null) {
            System.out.println("Circular Linked List is empty");
            return;
        }

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

    // Main method for testing the implementation
    public static void main(String[] args) {
        CircularLinkedList cll1 = new CircularLinkedList();
        cll1.head = new Node(1);
        cll1.head.next = new Node(2);
        cll1.head.next.next = new Node(3);
        cll1.head.next.next.next = cll1.head; // Making it circular

        CircularLinkedList cll2 = new CircularLinkedList();
        cll2.head = new Node(4);
        cll2.head.next = new Node(5);
        cll2.head.next.next = new Node(6);
        cll2.head.next.next.next = cll2.head; // Making it circular

        System.out.println("First Circular Linked List:");
        cll1.display();

        System.out.println("Second Circular Linked List:");
        cll2.display();

        CircularLinkedList mergedList = new CircularLinkedList();
        mergedList.mergeLists(cll1, cll2);

        System.out.println("Merged Circular Linked List:");
        mergedList.display();
    }
}

This code merges two Circular Linked List cll1 and cll2, and then displays the merged list.

Advantages and Disadvantages

Circular Linked List offer unique advantages and disadvantages compared to linear linked list. Here’s a breakdown:

Advantages

1. Efficient Traversal: Circular linked list allow efficient traversal in both forward and backward directions since the last node points back to the first node.
2. Constant Time Insertions and Deletions: Insertions and deletions at the beginning and end of the list can be done in constant time, O(1), by adjusting the pointers appropriately.
3. Space Efficiency: Circular linked list can save memory by eliminating the need for a separate tail pointer. The tail of the list points back to the head, creating a circular structure.
4. Useful in Circular Data Structures: Circular linked list are well-suited for modeling circular data structures such as queues, where elements cycle continuously.
5. No Need for Special Handling at the End: Unlike linear linked list, where you need to track the end of the list separately, circular linked list inherently handle the end of the list due to their circular nature.

Disadvantages

1. Complexity in Insertions and Deletions at Arbitrary Positions: Insertions and deletions at arbitrary positions in a circular linked list can be more complex than in linear linked list. They may require traversal from the beginning or end of the list to find the desired position.
2. Difficulty in Detecting End of the List: Since circular linked list do not have a distinct end marker, it can be challenging to detect the end of the list during traversal without maintaining extra information.
3. Increased Complexity in Operations: Certain operations, such as finding the length of the list or locating the nth element from the end, may require additional processing due to the circular structure.
4. Potential for Infinite Loop: If not handled carefully, circular references or incorrect pointer manipulations in circular linked list can lead to infinite loops during traversal.
5. Extra Space Overhead: While circular linked list can save memory by eliminating the need for a separate tail pointer, they may incur additional space overhead due to the need for a head pointer and potentially increased complexity in maintaining the circular structure.

In summary, Circular Linked List offer advantages such as efficient traversal, constant time insertions and deletions, and space efficiency, but they also come with disadvantages such as complexity in certain operations and the potential for infinite loops if not managed properly.

Application of Circular Linked List

Circular Linked List find applications in various real-world scenarios and software development due to their unique properties. Here are some common use cases:

1. Circular Buffers/Ring Buffers: Circular linked list are often used to implement circular buffers or ring buffers in embedded systems, operating systems, and communication protocols. They efficiently manage data streams by continuously cycling through a fixed-size buffer, making them suitable for applications like audio and video streaming, network packet processing, and sensor data collection.
2. Round-Robin Scheduling: In operating systems and task scheduling algorithms, Circular Linked List are employed to implement round-robin scheduling. Processes are organized in a circular queue, and each process gets a fixed time slice for execution before being moved to the end of the queue. This ensures fair CPU utilization and prevents starvation.
3. Game Development: Circular Linked List are utilized in game development for managing game objects in a circular manner. For example, in a game where enemies spawn and move in a looped pattern, a circular linked list can efficiently handle their movement and collision detection.
4. Music and Playlist Management: Music player applications often use circular linked list to manage playlists and play songs in a continuous loop. The last song in the playlist points back to the first song, allowing seamless playback without interruptions.
5. Memory Allocation and Garbage Collection: Circular linked list are employed in memory management systems for implementing memory allocation and garbage collection algorithms. They facilitate efficient memory allocation and deallocation by managing free memory blocks in a circular fashion, minimizing fragmentation and improving memory utilization.
6. Resource Management: Circular Linked List are used in resource management systems where resources need to be allocated and deallocated cyclically. For example, in resource pooling systems, such as database connection pooling or thread pooling, circular linked list efficiently manage the lifecycle of resources, ensuring optimal utilization and performance.
7. Simulation and Modeling: Circular Linked List find applications in simulations and modeling scenarios where entities interact in a circular or cyclical manner. They are used to represent interconnected systems, such as traffic flow simulations, supply chain management, and process modeling.

Overall, Circular Linked List offer versatile solutions for managing cyclic data structures and are widely employed in various domains, including embedded systems, operating systems, game development, multimedia applications, and resource management systems.

Implementation

Here’s a basic implementation of a Circular Linked List in Java:

Circular linked list program in data structure

public class CircularLinkedList {
    // Node class representing each element of the circular linked list
    private static class Node {
        int data;
        Node next;

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

    // Head pointer of the circular linked list
    private Node head;

    // Constructor to initialize an empty circular linked list
    public CircularLinkedList() {
        this.head = null;
    }

    // Method to insert a node at the beginning of the circular linked list
    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;
            }
            temp.next = newNode;
            newNode.next = head;
            head = newNode;
        }
    }

    // Method to insert a node at the end of the circular linked list
    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;
        }
    }

    // Method to display the circular linked list
    public void display() {
        if (head == null) {
            System.out.println("Circular Linked List is empty");
            return;
        }

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

    // Main method for testing the implementation
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.insertAtEnd(10);
        cll.insertAtEnd(20);
        cll.insertAtBeginning(5);

        System.out.println("Circular Linked List:");
        cll.display();
    }
}

This implementation includes methods to insert nodes at the beginning and end of the Circular Linked List, as well as a method to display the contents of the list. You can further extend this implementation by adding methods for deletion, searching, and other operations as needed.

Conclusion

In conclusion, Circular Linked List are a fundamental data structure that offers efficient traversal, constant time insertions and deletions, and space efficiency. Despite their advantages, Circular Linked List also come with certain complexities, such as handling insertions and deletions at arbitrary positions and detecting the end of the list during traversal. However, their unique properties make them suitable for various real-world applications, including circular buffers, round-robin scheduling, game development, and memory management systems.

Recap of Key Points:

• Circular Linked List allow efficient traversal in both forward and backward directions.
• Insertions and deletions at the beginning and end of the list can be done in constant time.
• Circular Linked List can save memory by eliminating the need for a separate tail pointer.
• They are well-suited for modeling cyclic data structures and handling continuous loops in applications.
• However, operations like insertions and deletions at arbitrary positions may require additional processing.
• Circular Linked List find applications in various domains, including embedded systems, operating systems, game development, and resource management systems.

Importance and Relevance:

Circular Linked List hold significant importance in the realm of data structures and algorithms due to their versatility and efficiency. They offer solutions to problems where cyclic behavior or continuous looping is required, making them indispensable in scenarios like round-robin scheduling, circular buffers, and game development.

Furthermore, Circular Linked List provide a foundation for understanding more complex data structures and algorithms. They serve as building blocks for more advanced concepts, such as graphs, circular queues, and circular buffers, laying the groundwork for deeper exploration into algorithmic problem-solving.

In conclusion, Circular Linked List play a crucial role in the landscape of data structures and algorithms, offering efficient solutions to a wide range of problems and serving as a stepping stone for learning more complex concepts in computer science.

FAQs

What differentiates a circular linked list from a normal linked list?

Here’s a comparison between a Circular Linked List and a normal (linear) Linked List

In summary, the main differences between a Circular Linked List and a normal Linked List lie in their structure, traversal capabilities, memory efficiency, and suitability for cyclic behavior. Circular Linked List offer advantages such as efficient traversal and space savings but are more specialized and suited for scenarios where cyclic behavior is required.

Read other awesome articles in Medium.com or in akcoding’s posts, you can also join our YouTube channel AK Coding