# 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.

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)
3.        private SingleNode tail;
4.        private int sizeofList;
5.
6.     SingleNode CreateCircularSingleLL(int nodeValue){
7.
9.              var node = new SingleNode();
10.              node.setValue(nodeValue);
11.              node.setNext(node);
13.              tail= node;
14.              sizeodList=1;
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.

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:

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.

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 7: else if(location > = sizeofList)---------------------------------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);
6.             else if(location == 0) {  //Insert at first position
9.                   tail.setNext(node);
10.          }else if(location >= sizeofList){
12.                 tail=node; //to keep track of last node
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 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(){
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. {
4.          else {
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.

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:

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:
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)
Step 4: else if(location greaterthan equal to last)-----O(n)
loop till 2nd last node-----------------------------O(1)
tail= tempNode------------------------------------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. {
4.        else if(location ==0){
7.            sizeofList--;
8.        }else if( location>= sizeOfList){
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.     }
20.          tail = tempNode;
21.          sizeOfList--;
22.
23.        }else{
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: