Circular Linked List in Data Structure

So far, we have seen that there are mainly three types of linked lists:

1. Singly-linked list

2. Doubly linked list

3. Circular linked list

A circular linked list is a variation of a simple linked list. A circular linked list could be:

1. Singly circular linked list

2. Doubly circular linked list

What is a Circular Linked list?

A circular list is a list that does not contain any pointer pointing to NULL. In a circular linked list, all the nodes are inter-connected in a cyclic manner. Both singly and doubly linked lists can be circular.

1. Singly Circular Linked List

There is only one pointer in a singly linked list that points to NULL, i.e. the pointer from the last node of the list. If we want to make the singly linked list circular, we need to make the ‘Next’ pointer of the last node point to the first node.

The following list is a singly circular linked list:

2. Doubly Circular Linked List

A doubly linked list points to not only the next node but to the previous node as well. A circular doubly linked list contains 2 NULL pointers. The ‘Next’ of the last node points to the first node in a doubly-linked list. The ‘Prev’ of the first node points to the last node.

A doubly circular linked list looks as follows:

Memory Representation of Circular Linked List

Memory representation defines how a linked list is stored in the main memory.

1. Singly Circular Linked List

A singly circular list consists of only one addition pointer named ‘Next’. The ‘Next’ of each node, except the last node will contain the address of the upcoming node. The last node’s ‘Next’ will store the address of the first node.

For a singly linked list, the memory will be represented as follows:

2. Doubly Circular Linked List

In a doubly-linked list, there are two additional pointers: ‘Next’ and ‘Prev’. The ‘Next’ of each node links to the address of the upcoming node’s ‘Prev’. The ‘Next’ of the last node links to the first node. The ‘prev’ of each node has the address of the previous node. The ‘Prev’ of the first node links to the last node.

The memory representation diagram for the doubly linked list is:

Applications of Circular Linked List

A circular linked list has some real-life applications such as:

1. In multi-player games, all the players are kept/arranged in a circular linked list form. This gives a fixed turn number to every player.

2. Circular linked lists are implied in our computer’s operating system for scheduling various processes. In many cases, a lot of processes are aligned and they need to use the same resource. In such cases, they are put into a circular linked list and given a fixed time slot for execution.

3. We can also implement a circular queue using a circular linked list. This will help to reduce the number of pointers from 2 to 1 because a circular linked list will require only one pointer.

Basic operations on a Circular Linked List:

1. Traversal Operation:

The traversal operation includes traveling through all the nodes of the linked list and displaying their values if needed.

The function for traversal operation in a circular linked list is as follows:

Traversal()
{
   if (Head == NULL)
       return;
   else
   {
       Ptr = Head;
       while(Ptr->Next != Head)
       {
           Ptr = Ptr->Next;
           print(data);
       }
   }
}

2. Display Operation:

Display operation is used to print the value of all the nodes. To display a list, we need to traverse all its nodes and print their values.

The following function depicts the display operation in a circular linked list.

Display_listl()
{
   if (Head == NULL)
       return;
   else
   {
       Ptr = Head;
       while(Ptr->Next != Head)
       {
           Ptr = Ptr->Next;
           display(data);
       }
   }
}

3. Insertion Operation:

Insertion operation is used to insert nodes in a linked list. Let us see two different cases for insertion:

a. Insertion at the beginning:

Since a circular list could be both a singly circular list and a doubly circular linked list, let us check the insertion operation for both of them.

i. Singly circular linked list:

We will insert a node at the front of the list in the following way:

The above diagram shows that initially, the list was A→B→C→D.

After inserting a new node, the final list is E→A→B→C→D.

The function for performing this operation is as follows:

Insert_at_beginning_Singly(struct Node* Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct Node));  //Allocating memory for new Node
    if(Head == NULL)  //When the list is empty
    {  
        Head = Ptr;  
        Ptr->Next = Head;  
    }  
    temp = Head;  
    while(temp->next != head)  
        temp = temp->next;    
    temp->Next = Ptr;  //Making the last node point to the first node 
    Ptr->Next = Head;
    Head = Ptr; 
}

ii. Doubly circular linked list:

1. Insertion operation will lead to the shifting of various pointers in the list.

2. We insert a node at the beginning such that the next pointer points to the node which was at first before.

3. Let us take an example:
Initially, let the list be A→B→C→D.

Let us try inerting M into the list as shown:

Thus, the new list will be M→A→B→C→D.

The function for the above operation is:

Insert_at_beginning_Doubly(struct Node* Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct Node));  //Allocating memory for new Node
    if(Head == NULL)  //When the list is empty
    {  
        Head = Ptr;  
        Ptr->Next = Head;   
        Ptr->Prev = Head;     
    }  
    temp = Head;   
    while(temp->Next != Head)  
        temp = temp->Next;   
    temp->Next = Ptr;  
    Ptr->Prev = temp;  
    Head -> Prev = Ptr;  
    Ptr->Next = Head;  
    Head = Ptr;  
}

b. Insertion at the end:

This operation will add a node at the end of the circular linked list.

i. Singly linked list:

a. To insert a node at the end of the list, we first need to traverse the whole list.

 

b. The function for insertion at the end is:

Insert_at_end_singly(struct Node* Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct Node));  //Allocating memory for new Node
    if(Head == NULL)  //When the list is empty
    {  
        Head = Ptr;  
        Ptr->Next = Head;   
    }  
    temp = Head;   
    while(temp->Next != Head)  
        temp = temp->Next;   
    temp->Next = Ptr;  
    Ptr->Next = Head;  
}

ii. Doubly linked list:

a. If the list is empty, we will insert a node after the Head.

b. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.

Suppose we wish to insert the node ‘M’ at the end of the list, the list then will be A→B→C→D→M as shown:

The function will be:

Insert_at_end_doubly(struct Node* Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct Node));  //Allocating memory for new Node
    if(Head == NULL)  //When the list is empty
    {  
        Head = Ptr;  
        Ptr->Next = Head; 
        Ptr->Prev = Head;
    }  
    Head->Prev = Ptr;  
    Ptr->Next = Head;  
    temp->Next = Ptr;  
    Ptr->Prev = temp; 
}

4. Deletion from the beginning:

a. Singly linked list:

a. It involves deleting the first node from the linked list.

b. Suppose we have a list A→B→C→D and we wish to delete D from it, we will do it as follows:

The function for the deletion operation will be:

Delete_from_brginning_sngly(struct Node* Head)
{
    Ptr = (struct Node *) malloc(sizeof(struct Node));  //Allocating memory for new Node
    if(Head == NULL)  //When the list is empty
        return;
    if(Head->Next == Head)  //When the list contains a single node
    {  
        Head = NULL;  
        free(Head);  
    }  
    Ptr = Head;   
    while(Ptr->Next != Head)  
        Ptr = Ptr->Next;   
    Ptr->Next = Head->Next;
    free(Head);
}

While writing its function, we take into consideration three different cases:

1. When the list is empty

2. When the list has only one node

3. When the list has two or more nodes

b. Doubly linked list:

1. If we wish to delete the first node from a doubly-linked list, we need to make the Head point to the second node.

2. Suppose we have a doubly-linked list: A→B→C→D.

3. On deleting the first node, we will get B→C→D.

4. The pointer adjustments are shown below:

The pseudo-code for deleting operation will be:

Deletion_from_beginning_doubly(int key){
    
    if (Head == NULL)   //If the list is empty
    {
        free(Head);
        return;
    }
    temp = head;   
    while(temp->Next != head)  
        temp = temp->Next;  
    temp->Next = Head->Next;   //Make temp point to the last node of the list
    Head->Next->Prev = temp;  //the new Head must also point to the last node
    free(Head);   
    Head = temp->Next;  //Make the pointer next to Head as the new Head
}

a. Deletion at the End

1. It involves deleting the last node of the circular linked list.

2. But, a circular linked list has all the nodes inter-connected to each other, so technically there is no last node.

3. If we want to delete the last node, we will check out which node’s ‘Next’ points to the first node and we will delete that node.

i. Singly-linked list

While deleting the last node, we take into consideration three cases:

a. When the list is empty

b. When the list contains a single node

c. When the list contains two or more nodes

Suppose we have a list A→B→C→D. On deleting the last node, we get A→B→C as shown below:

The pseudo-code will be:

Deletion_at_end_singly(int key){
    if (Head == NULL)   //If the list is empty
        return;
    if(Head->Next == Head)  
    {  
        Head = NULL;  
        free(Head);  //When the list contains only one node
    }  
    Ptr = Head;  
    while(Ptr->Next != Head)  
    {  
        Ptr->Prev = Ptr;  
        Ptr = Ntr->Next;  
    }
    Ptr->Prev->Next = Ptr->Next;  
    free(Ptr);  
}

ii. Doubly linked list

a. If the list is empty, we will directly pass the return statement in the function.

b. If the list contains a single node, we just need to make the Head point towards NULL.

c. If the list has two or more nodes, we need to traverse the whole node and then delete the last node.

The deletion at the end of a doubly circular linked list is shown by the following example:

The pseudo-code for this operation will be:

Deletion_at_end_doubly(int key){
    struct Node *Ptr = Head;
    if (Head == NULL)   //If the list is empty
        return;
    if(Ptr->Next == Head)  
    {  
        Head = NULL;  
        free(Head);     //When the list contains only one node
        return;
    }  
    temp = head;   
    while(temp->Next != Head)  
        temp = temp->Next; 
    temp->Prev->Next = Head;  
    Head->Prev = Ptr->Prev;    
    free(Head);  
}

Advantages of a Circular Linked List

1. Since the list is circular, any node could be the starting point while traversal or some other operations.

2. We can traverse to any node while standing at a particular node. We didn’t have this privilege in a linear list as we could not go back to the previous nodes.

3. The circular linked list helps in the implementation of the queue. If we implement the queue using a circular linked list, we need not maintain two pointers for front and rear. Rather we can fulfill our purpose using a single pointer.

4. Circular doubly linked lists help in implementing advanced data structures like a Fibonacci heap.

5. Circular linked lists are used in various CPU scheduling algorithms such as the Round Robin scheduling algorithm. In this algorithm, processes are linked up in a circular manner with fixed time slots.

Disadvantages of a Circular Linked List

1. It is very difficult to reverse a circular linked list.

2. Finding the end of the list is very hard.

3. If not implemented rightly, there is a high possibility of an infinite loop.

Conclusion

In this article, we studied the third type of list i.e. circular linked list. We performed various standard operations on the circular linked lists such as traversal, insertion, and deletion. We took into consideration both singly and doubly circular linked lists.