Circular linked list

A linked list in which all the elements are connected to form a circle chain is a circular linked list. There is no null at the end. It can be a singly or doubly circular linked list 

Implementation:

To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.

The pointer last points to node Z and last -> next points to the node P.

               

For the insertion of a node in the beginning we need to traverse the whole list. Also, for insertion and the end, the whole list has to be traversed. If instead of the start pointer, we take a pointer to the last node then in both cases there won’t be any need to traverse the whole list. So insertion in the begging or at the end takes constant time irrespective of the length of the list, so we have taken the last pointer.

Below is a sample program to create and traverse in a Circular Linked List:

C++:

// A complete C++ program to demonstrate the 
// working of Circular Linked Lists

#include<bits/stdc++.h> 
using namespace std; 

// Circular Linked List Node
struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

// Function to add a node at the end of a 
// Circular Linked List
struct Node *addEnd(struct Node *last, int data) 
{ 
    if (last == NULL) 
    {
        // Creating a node dynamically. 
        struct Node *temp = new Node; 
    
        // Assigning the data. 
        temp -> data = data; 
        last = temp; 
    
        // Creating the link. 
        last -> next = last; 
    
        return last; 
    }
    
    struct Node *temp = new Node; 

    temp -> data = data; 
    temp -> next = last -> next; 
    last -> next = temp; 
    last = temp; 

    return last; 
} 

// Function to traverse a Circular Linked list
// Using a pointer to the Last Node
void traverse(struct Node *last) 
{ 
    struct Node *p; 

    // If list is empty, return. 
    if (last == NULL) 
    { 
        cout << "List is empty." << endl; 
        return; 
    } 

    // Pointing to first Node of the list. 
    p = last -> next; 

    // Traversing the list. 
    do
    { 
        cout << p -> data << " "; 
        p = p -> next; 

    } 
    while(p != last->next); 

} 

// Driver Program 
int main() 
{ 
    struct Node *last = NULL; 

    last = addEnd(last, 45); 
    last = addEnd(last, 6); 
    last = addEnd(last, 93); 
    last = addEnd(last, 5); 
    last = addEnd(last, 12); 
    last = addEnd(last, 10); 

    traverse(last); 

    return 0; 
} 

Java:

 // A complete Java program to demonstrate the 
// working of Circular Linked Lists

class CLL 
{ 
    // A circular linked list node
    static class Node 
    { 
        int data; 
        Node next; 
    }; 

    // Function to insert a node in a Circular
    // linked list at the end
    static Node addEnd(Node last, int data) 
    { 
        if (last == null) 
        {
            // Creating a node dynamically. 
            Node temp = new Node(); 
        
            // Assigning the data. 
            temp.data = data; 
            last = temp; 
        
            // Creating the link. 
            last.next = last; 
        
            return last; 
        } 
        
        Node temp = new Node(); 
    
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
        last = temp; 
    
        return last; 
    } 
    
    // Function to traverse a given Circular Linked 
    // List using the Last pointer
    static void traverse(Node last) 
    { 
        Node p; 
    
        // If list is empty, return. 
        if (last == null) 
        { 
            System.out.println("List is empty."); 
            return; 
        } 
    
        // Pointing to first Node of the list. 
        p = last.next; 
    
        // Traversing the list. 
        do
        { 
            System.out.print(p.data + " "); 
            p = p.next; 
    
        } 
        while(p != last.next); 
    
    } 
    
    // Driver code 
    public static void main(String[] args) 
    { 
        Node last = null; 
    
        last = addEnd(last, 45); 
        last = addEnd(last, 6); 
        last = addEnd(last, 93); 
        last = addEnd(last, 5); 
        last = addEnd(last, 12); 
        last = addEnd(last, 10); 
    
        traverse(last); 
    } 
} 

output:

45 6 93 5 12 10

Advantages of Circular Linked Lists:

1. Flexibility in choosing the starting point: One of the advantages of circular linked lists is that any node can serve as a starting point for traversal. This flexibility allows us to traverse the entire list by starting from any node, making it convenient for specific algorithms or requirements.

2. Efficient implementation of queues: Circular linked lists are particularly useful for implementing queues. Unlike other data structures, such as arrays, where we need to maintain separate pointers for the front and rear, a circular linked list can efficiently handle the operations of enqueueing and dequeuing elements by maintaining just a pointer to the last inserted node. The front of the queue can always be obtained as the next node of the last inserted node.

3. Circularity for repetitive cycles: Circular lists excel in scenarios where cyclic operations are involved. For instance, in multitasking operating systems, applications are often placed in a list, and the system cycles through them, allocating execution time to each application in turn. By using a circular linked list, when the end of the list is reached, it seamlessly loops back to the beginning, enabling efficient cyclic processing of the applications.

4. Support for advanced data structures: Circular doubly linked lists find application in the implementation of advanced data structures like the Fibonacci Heap. These data structures rely on the properties of circularity and doubly linked nodes to optimize their operations, providing efficient and effective solutions for complex algorithms.

These advantages make circular linked lists a valuable choice in various scenarios, offering flexibility, efficiency, and support for advanced data structures.