Circular Linked List in Data Structure

In previous articles, singly-linked lists and doubly-linked lists are explained in detail. Here we will be focusing on the circular linked list and its modified versions. Circular linked lists are a modified version of singly-linked lists.

We know that in singly-linked lists the last node points to NULL. But in a circular linked list, the last node points to its first node forming a circular loop. In this article, we will learn about circular linked lists and doubly circular linked lists.

Circular Linked List

A circular linked list is a more efficient version of a singly linked list where the last node points to the first node instead of NULL. Just like a singly linked list, here also each node has two parts.

The first part contains data and the second part points to the next node. It contains the address of the next node in the actual memory.

Memory Representation of Circular Linked List

Operations on Circular Linked List

• Insert: inserting a new node into a circular linked list.
• Delete: deleting a node from a circular linked list.
• Search: finding a node in a circular linked list.
• Display: displaying the circular linked list.

Insert Node in Circular Linked List

1. Insert Node at the beginning of Circular Linked List

For Adding node at the beginning of the list, Unlink the last and first node and point the last node to the new node. Now point the new node to the head node and make the new node the new head.

void insertAtFirst(node *new)
{ 
temp = head;  
            while(temp->next != head)  
                temp = temp->next;  
            new->next = head;   
            temp -> next =new;   
            head =new;  
        }

2. Insert node at the end of Circular Linked List

For adding a node at the end of the list, unlink the last and first node and point the last node to the new node. Now point new node to head node.

void insertAtLAst(Node *new)
{
temp = head;  
            while(temp -> next != head)  
                      temp = temp -> next;  
            temp -> next = new;   
            new -> next = head;  
        }

Delete Nodes in Circular Linked List

1. Deleting node at the start of Circular Linked List

Delete an existing node from the first position in the list. Point the head to the second node.

void deleteAtFirst()
{
ptr = head;   
        while(ptr -> next != head)  
            ptr = ptr -> next;   
        ptr->next = head->next;  
        free(head);  
        head = ptr->next;  
}

2. Delete node at the last of Circular Linked List

Delete an existing node from the last position of the list. Unlink last node to head and point second last node to head node.

void deleteAtLast()
{ 
ptr = head;  
        while(ptr ->next != head)  
        {  
            ptr1=ptr;  
            ptr = ptr->next;  
        }  
        ptr1->next = ptr -> next;  
        free(ptr);
}

Display Circular Linked List

Traverse through the circular linked list starting from the head and print the data in each node.

void DisplayList() 
{
 
   struct node *disp = head;
   	
    if(head != NULL) 
      {
    
      while(disp -> next != disp) 
{     
         printf("(%d, ) ",disp -> data);
         disp = disp -> next;
      }
   }
}

Doubly Circular Linked List

A doubly circular linked list is a more efficient version of a Doubly linked list. Here, the next pointer of the last node points to the first node, and the previous pointer of the first node points to the last node.

Just like a doubly-linked list, here also each node has three parts. One part contains data and the other parts point to the next node and the previous node.

Memory Representation of Doubly Circular Linked List

Operations on doubly circular linked list

• Insert: adding a new node to the existing doubly circular linked list.
• Delete: removing a node from the existing doubly circular linked list.
• Search: finding  a node in the existing doubly circular linked list. 
• Display: display the existing doubly circular linked list.

Inserting Nodes in Doubly Circular Linked List

1. Insert node at the beginning of Doubly Circular Linked List

Adding a node at the beginning of the list is done by pointing the new node to the first and the last node and set it as the new head.

void insertAtFirst(node *new)
{ 
temp = head;  
            while(temp->next != head)  
                temp = temp->next;  
            new->next = head;  
            head -> previous = new; 
            temp -> next =new;   
            new -> previous = temp;
            head =new;  
        }

2. Insert node at the end of Doubly Circular Linked List

Adding a node at the end of the list is done by pointing the new node to the first and the last node.

void insertAtLast(Node *new)
{
temp = head;  
            while(temp -> next != head)  
                      temp = temp -> next;  
            new->next = head;  
            head -> previous = new; 
            temp -> next =new;   
            new -> previous = temp;
        }

Deleting Nodes in the Doubly Circular Linked List

1. Deleting node at the start of Doubly Circular Linked List

Delete an existing node from the first position in the list.

void deleteAtFirst()
{
ptr = head;   
        while(ptr -> next != head)  
            ptr = ptr -> next;   
        ptr->next = head->next;  
        free(head);  
        head = ptr->next;  
        head.previous -> ptr;
}

2. Delete node at last of Doubly Circular Linked List

Delete an existing node from the last position of the list. Unlink first and last node. Point second last node to the first node.

void deleteAtLast()
{ 
ptr = head;  
        while(ptr ->next != head)  
        {  
            ptr1=ptr;  
            ptr = ptr->next;  
        }  
        ptr1->next = ptr -> next;  
        free(ptr);
        head -> previous = ptr ;
}

Display Doubly Circular Linked List

Traverse through the circular linked list starting from the head and print the data in each node.

void DisplayList() 
{
 
   struct node *disp = head;
   	
    if(head != NULL) 
      {
    
      while(disp -> next != disp) 
{     
         printf("(%d, ) ",disp -> data);
         disp = disp -> next;
      }
   }
}

Search for a node in a doubly circular linked list

Traverse through the circular linked list starting from the head and compare data in each node with the search element. If found, return the location at which the element was found. If not found, return -1.

int SearchElement(int se) 
{
  node *search = head;
  while(search != NULL && search -> data != se) 
{  
    search = search -> next;
  }
  return search;
}

Circular Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>
  
struct Node
 {
    int data;
    struct Node* next;
};
  
int main()
{
    struct Node* Node1 = NULL;
    struct Node* Node2 = NULL;
    struct Node* Node3 = NULL;
    struct Node* head = Node1;
  
    
   Node1 = (struct Node*)malloc(sizeof(struct Node));
   Node2 = (struct Node*)malloc(sizeof(struct Node));
   Node3 = (struct Node*)malloc(sizeof(struct Node));
  
     
    Node1 -> data = 1; 
    Node1 -> next = Node2;   
       
    Node2 -> data = 2;
    Node2 -> next = Node3;
  
     
    Node3 -> data = 3; 
    Node3 -> next = Node1;
  
    display(Node1);
    return 0;
}

void display(struct Node* disp)
{
    do
{
        printf(" %d ", disp -> data);
        disp = disp -> next;
    }while (disp != head) ;
}

Circular Linked list implementation in Python

class Node:
    def __init__(self, data):
        self.data = data  
        self.next = None  
  
class SinglyLinkedList:    
    def __init__(self):
        self.head = None
    
    def DisplayList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next
  
if __name__=='__main__':
  
    sll = SinglyLinkedList()
  
    sll.head = Node(“DATA”)
    Node2 = Node(“FLAIR”)
    Node3 = Node(“CLL”)
  
    sll.head.next = Node2; 
    Node2.next = Node3; 
    Node3.next = head;
  
    llist.DisplayList()

Implementation of Circular Linked list in C++

#include <bits/stdc++.h>
using namespace std;
  
class Node {
public:
    string data;
    Node* next;
};
  
void displayList(Node* n)
{
    while (n != NULL)
 {
        cout << n -> data << " ";
        n = n -> next;
    }
}
 
int main()
{
    Node* Node1 = NULL;
    Node* Node2 = NULL;
    Node* Node3 = NULL;
  
    Node1 = new Node();
    Node2 = new Node();
    Node3 = new Node();
  
    Node1 -> data = ”DATA” ; 
    Node1 -> next = Node2; 
  
    Node2 -> data = “FLAIR”; 
    Node2 -> next = Node3;
  
    Node3 -> data = “CLL”; 
    Node3 -> next = Node1;
  
    displayList(Node1);
  
    return 0;
}

Circular Linked list implementation in Java

class CircularLinkedList
 {
    
Node head; 
 
    static class Node
   {
        String data;
        Node next;
        
        Node(String d)
        {
            data = d;
            next = null;
        } 
    }
  
    
    public void DisplayList()
    {
        Node n = head;
        do
{
        System.out.print(n.data + " ");
            n = n.next;
    }while (n != head) ;
 
 
        
    }
  
    public static void main(String[] args)
    {
        
        CircularLinkedList cllist = new CircularLinkedList();
   
        Node Node1 = new Node("DATA");
        cllist.head = Node1;
        Node Node2 = new Node("FLAIR");
        Node Node3 = new Node("CLL");
  
        cllist.head.next = Node2; 
        Node2.next = Node3;
        Node3.next = Node1;
  
        cllist.DisplayList();
    }
}

Advantages of Circular Linked List

• We can consider any node as a starting point. The whole linked list is traversable from any starting point.
• The time complexity for jumping from the first node to last or last to first in a doubly circular linked list is constant
• We don’t need two different pointers for moving forward and backward. We can always reach the backward node by moving forward since it is a loop.

Applications of Circular Linked list

• All applications are put in a circular list on our personal computers. The operating system gives fixed time to each process for execution. It keeps on traversing through the list until all processes are executed.
• Circular linked lists are used in creating a circular queue.
• In multiplayer games like ludo king, all players are stored in a circular list and the pointer keeps on moving after each player’s chance.
• Doubly circular linked lists are very useful in the implementation of advanced data structures like the Fibonacci heap.

Conclusion

With this article, we end our discussion of linked lists. We now understand different types of linked lists and how to perform commonly used operations on them.

Linked lists are basic examples of Dynamic programming. In future articles, we will learn about other Data Structures that are implemented using a linked list.