Post
Ask Question

Circular Linked List in C#

Introduction

 
Hello friends, today I am going to explain the Circular linked list. Furthermore, we will discuss Insertion, Deletion, and Search operations in a Circular Linked list and where its implementation is useful.
 
So, let's get started. 
 
In a Singly Linked list and a Doubly Linked list, we can reach the end of the LL, because it is indicated with "Null". However, in a Circular LL, there is no null, which means the end of the LL will point back to the head. While traversing a Circular linked list we need to be careful, since we might end up looping infinite times. In a Circular LL, each node has a successor.
 
These types of LLs are useful in a round robin algorithm, where several processes are using the same computer resource for the same amount of time.
 
Let's see the pictorial representation of a Circular LL.
 
Circular Single Linked List In C#
 
Now let's see how to Create a Circular Single Linked List. Let's see the algorithm first:
 
Algorithm
 
Step 1: Create Circular Single LL (nodeValue)----------------O(1)
Step 2: create a blank node-------------------------------------O(1)
Step 3: node.value = nodeValue// assign value to balnk node-O(1)
Step 4: node.next = node----------------------------------------------O(1)
Step 5: head= node // there is only one node in LL------------O(1)
Step 6: tail=node ------------------------------------------------------O(1)
 
Time and Space Complexity is O(1)
  1. public Class SingleCircularLinkedList {  
  2.        private SingleNode head;  
  3.        private SingleNode tail;  
  4.        private int sizeofList;  
  5.   
  6.     SingleNode CreateCircularSingleLL(int nodeValue){  
  7.      
  8.              head = new SingleNode();  
  9.              var node = new SingleNode();  
  10.              node.setValue(nodeValue);  
  11.              node.setNext(node);  
  12.              head= node;  
  13.              tail= node;  
  14.              sizeodList=1;  
  15.              return head;  
  16.        }  
  17.   
  18. }  

Inserting a Node in a CircularLL

 
Inserting a node in a CircularLL is the same as Single LL. Here, there are 3 cases:
  1. Inserting a node at start of a LL
  2. Inserting a node at end of a LL
  3. Inserting a node at the middle/specified location of a LL
Inserting a Node at the start of a LL
  1. We need to create an empty node and insert the value in it
  2. We need set the reference of the new node to point the head node
  3. Update the reference of the head node with new node, and mark the new node as head node 
  4. Change the reference of the last node to the new node reference. 
Let's look at the pictorial representation of the LL.
 
Circular Single Linked List In C#
 
Insert a New Node at the End of a Circular LL
  1. Create a blank node and insert a value in the node
  2. Update the last node reference with new node reference and create a connection from the last node to the new node.
  3. Set the last node reference with a head node reference and connect the new node with a head node.
Let's see the pictorial representation:
 
Circular Single Linked List In C#
 
Insert a Node at a Given Location/Middle of the Circular LL
 
Inserting a new node at given location remains the same as a Single LL.
  1. We need to create a blank node and insert value in it.
  2. Set the reference of the next node to the new node.
  3. Update the previous node reference with the new node reference.
Circular Single Linked List In C#
 
We've seen the above 3 cases. Now let's learn to program them. Let's see how the algorithm for these 3 cases looks:
 
Algorithm
 
Step 1. Insert New Node In CircularLL(nodeValue, location)-----------O(1)
Step 2: Create a blank node-------------------------------------------------O(1)
Step 3: Insert node value node.value = nodeValue-------------------O(1)
Step 4: if(head == null) return error---------------------------------------O(1)
Step 5: else if(location==0)--------------------------------------------------O(1)
Step 6: node.next= head;----------------------------------------------------O(1)
            head= node-----------------------------------------------------------O(1)
            tail.next= head -----------------------------------------------------O(1)
Step 7: else if(location > = sizeofList)---------------------------------O(1)
            node.next= head ------------------------------------------------O(1)
            tail.next= node-----------------------------------------------------O(1)
            tail=node----------------------------------------------------------O(1)
Step 8: else
            loop : from tempNode= 0 to location -1-----------------O(n)
             node.next=tempNode.next------------------------------O(1)
             tempNode.next= node -----------------------------------O(1)
 
Time Complexity : O(n)
Space Complexity : O(1)
  1. public void InsertNewNodeInCircularLL(int nodeValue, int  location){  
  2.   
  3.              var node = new SingleNode();  
  4.              node.setValue(nodeValue);  
  5.              if(head == null) return ;  
  6.             else if(location == 0) {  //Insert at first position  
  7.                   node.setNext(head);  
  8.                   head = node;  
  9.                   tail.setNext(node);  
  10.          }else if(location >= sizeofList){  
  11.                 node.setNext(head);  
  12.                 tail=node; //to keep track of last node  
  13.                 tail.setNext(head);  
  14.           } else{  
  15.               var tempNode= new SingleNode();  
  16.              int index=0;  
  17.             while(index < location-1){  
  18.                   tempNode = tempnode.getNext();  
  19.                   index++;  
  20.              }  
  21.              node.setNext(tempNode.getNext());  
  22.              tempNode.setNext(node)  
  23.         }  
  24.        sizeofList++;  
  25.   
  26. }  

Traversing Circular LL

 
Traversing the Circular LL is same as a Single LL. Let's see the algrithm and code for it:
 
Algorithm
 
Step 1:  TraverseCircularLL()-----O(1)
Step 2: if(head==null) return error-------O(1)
Step 3: loop head to tail--------------------O(n)
Step 4: Print the currentnode value -----O(1)
 
Time Complexity : O(n)
Space Complexity : O(1) 
  1. public void TraverseCircularLL(){  
  2.        if(head==null) return;  
  3.        SingleNode tempNode= head;  
  4.        for(int i=0;i<sizeofList;i++){  
  5.               Console.Write(tempNode.getValue());  
  6.               if(i != sizeofList-1)  
  7.                  Console.Write("-->");  
  8.            tempNode= tempNode.getNext();  
  9.       }  
  10.      Console.WriteLine("\n");  
  11.   
  12. }  
Searching a Node in Circular LL
 
Searching a node in Circular LL is same as a Single LL. However, if you give a node that is not present in the circular linked list, you may wonder how to exit the node when it reaches the end since in circular LL the last node reference will be pointing to first node and we will end up with an infinite loop.
 
In this situation, we will compare each node reference with a tail node reference. Once the referenece of a node matches with tail node reference, then we say that we have reached the end of the LL since the tail node will have the reference of the Last node.
 
Let's look in to the algorithm and then the code.
 
Algorithm
 
Step 1: SerachNodeInCicularLL(nodeValue)---------------O(1)
Step 2: loop: tempNode= start to tail-------------------------O(n)
Step 3: if(tempNode.value equals nodeValue)-------------O(1)
               print tempNode.Value--------------------------------O(1)
               return------------------------------------------------------O(1)
            else-----------------------------------------------------------O(1)
               print node value is not present in circular LL-----O(1)
                return ------------------------------------------------------O(1)
 
Time Complexity : O(n)
Space Complexity : O(1)
 
Now let's look at the code:
  1. public boolean SearchNodeInCircularLL(int nodeValue)  
  2. {  
  3.           if(head==null) return;  
  4.          else {  
  5.                  SingleNode tempNode= head;  
  6.                 for(int i=0;i< sizeofList;i++){  
  7.                       if(tempNode.getValue() == nodeValue){  
  8.                             Console.WriteLine(tempNode.Value);  
  9.                             return true;  
  10.                      }  
  11.                }  
  12.         }  
  13.           Console.WriteLine("Value not found in Circular LL");  
  14.             return false;  
  15. }  

Deletion of a Node in Circular LL

 
Deletion in Circular linked list has 3 cases:
  1. Delete a node at the start of the LL
  2. Delete a node at the End of an LL
  3. Delete a node at the middle/specified location of an LL
Delete Node at the Start of an LL
 
To delete a node at the start of an LL. We need to follow some steps:
  1. Remove the connection of the head node
  2. Change the Head node reference to point to the next node
  3. Update the reference of the last node in Circular LL.
Let's see the pictorial diagram of it.
Circular Single Linked List In C#
 
Delete Node at End of the List
 
If we want to delete the node at the end of the list, we need to update the tail reference with the previous node reference. The previous node reference should point to the head of the node reference.
 
Let's look at the pictorial representation:
 
Circular Single Linked List In C#
 
Delete a Node at the Given Position
 
We need to update the previous pointer reference with the next node reference 
 
Let's look at the pictorial representation:
Circular Single Linked List In C#
Let's look into the algorithm:
 
Algorithm
 
Step 1: DeleteNodeInCircularLL(Location)  -----O(1)
Step 2: if(head equal null) return ------------------O(1)
Step 3: else if( location equals 0)----------------O(1)
             head= head.next---------------------------O(1)
             tail.next = head------------------------------O(1)
Step 4: else if(location greaterthan equal to last)-----O(n) 
             loop till 2nd last node-----------------------------O(1)
             tail= tempNode------------------------------------O(1)
             tempNode.next = head--------------------------O(1)
Step 5: else---------------------------------------------------O(1)
            loop: tempNode= start to location-1---------O(1)
           tempnode.next = tempNode.next.next--------O(1)
 
Let's look at the code for this:
  1. public void DeleteNodeInCircularLL(int location)  
  2. {  
  3.        if(head == null) return;  
  4.        else if(location ==0){  
  5.             head=head.getNext();  
  6.            tail.setNext(head);  
  7.            sizeofList--;  
  8.        }else if( location>= sizeOfList){  
  9.             SingleNode tempNode= head;  
  10.            for(int i=0;i<sizeofList-1;i++){  
  11.                   tempNode = tempNode.getNext();  
  12.   
  13.            }  
  14.          if (tempNode == head) { //if this is the only element in the list  
  15.                 tail = head = null;  
  16.                 setSize(getSize()-1);  
  17.                 return;  
  18.     }  
  19.           tempNode.setNext(head);  
  20.          tail = tempNode;  
  21.          sizeOfList--;  
  22.   
  23.        }else{  
  24.           SningleNode tempNode = head;  
  25.          for(int i=0;i<location-1;i++){  
  26.               tempNode = tempNode.getNext();  
  27.         }  
  28.           tempNode.setNext( tempNode.getNext().getNext());  
  29.           sizeofList--;  
  30.       }  
  31.   
  32.   
  33. }  
Last but not least, to delete the entire linked list: 
  1. //Delete entire linked list  
  2.     void deleteLinkedList() {  
  3.         Console.WriteLine("\n\nDeleting Linked List...");  
  4.         head = null;  
  5.         if(tail == null) {  
  6.             Console.WriteLine("Linked List is already deleted, nothing to delete !");  
  7.             return;  
  8.         }else {  
  9.             tail.setNext(null);  
  10.             tail = null;  
  11.             Console.WriteLine("Linked List deleted successfully !");  
  12.         }  
  13.     }  
Thank you guys, that's it for the Circular LL. I hope you enjoyed the article. :-)


Similar Articles