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)

public Class SingleCircularLinkedList {
private SingleNode head;
private SingleNode tail;
private int sizeofList;
SingleNode CreateCircularSingleLL(int nodeValue){
head = new SingleNode();
var node = new SingleNode();
node.setValue(nodeValue);
node.setNext(node);
head= node;
tail= node;
sizeodList=1;
return head;
}
}

Inserting a Node in a CircularLL

Inserting a node in a CircularLL is the same as Single LL. Here, there are 3 cases:

Inserting a node at start of a LL
Inserting a node at end of a LL
Inserting a node at the middle/specified location of a LL

Inserting a Node at the start of a LL

We need to create an empty node and insert the value in it
We need set the reference of the new node to point the head node
Update the reference of the head node with new node, and mark the new node as head node
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

Create a blank node and insert a value in the node
Update the last node reference with new node reference and create a connection from the last node to the new node.
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.

We need to create a blank node and insert value in it.
Set the reference of the next node to the new node.
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 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)

public void InsertNewNodeInCircularLL(int nodeValue, int location){
var node = new SingleNode();
node.setValue(nodeValue);
if(head == null) return ;
else if(location == 0) { //Insert at first position
node.setNext(head);
head = node;
tail.setNext(node);
}else if(location >= sizeofList){
node.setNext(head);
tail=node; //to keep track of last node
tail.setNext(head);
} else{
var tempNode= new SingleNode();
int index=0;
while(index < location-1){
tempNode = tempnode.getNext();
index++;
}
node.setNext(tempNode.getNext());
tempNode.setNext(node)
}
sizeofList++;
}

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)

public void TraverseCircularLL(){
if(head==null) return;
SingleNode tempNode= head;
for(int i=0;i<sizeofList;i++){
Console.Write(tempNode.getValue());
if(i != sizeofList-1)
Console.Write("-->");
tempNode= tempNode.getNext();
}
Console.WriteLine("\n");
}

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:

public boolean SearchNodeInCircularLL(int nodeValue)
{
if(head==null) return;
else {
SingleNode tempNode= head;
for(int i=0;i< sizeofList;i++){
if(tempNode.getValue() == nodeValue){
Console.WriteLine(tempNode.Value);
return true;
}
}
}
Console.WriteLine("Value not found in Circular LL");
return false;
}

Deletion of a Node in Circular LL

Deletion in Circular linked list has 3 cases:

Delete a node at the start of the LL
Delete a node at the End of an LL
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:

Remove the connection of the head node
Change the Head node reference to point to the next node
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)

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:

public void DeleteNodeInCircularLL(int location)
{
if(head == null) return;
else if(location ==0){
head=head.getNext();
tail.setNext(head);
sizeofList--;
}else if( location>= sizeOfList){
SingleNode tempNode= head;
for(int i=0;i<sizeofList-1;i++){
tempNode = tempNode.getNext();
}
if (tempNode == head) { //if this is the only element in the list
tail = head = null;
setSize(getSize()-1);
return;
}
tempNode.setNext(head);
tail = tempNode;
sizeOfList--;
}else{
SningleNode tempNode = head;
for(int i=0;i<location-1;i++){
tempNode = tempNode.getNext();
}
tempNode.setNext( tempNode.getNext().getNext());
sizeofList--;
}
}

Last but not least, to delete the entire linked list:

//Delete entire linked list
void deleteLinkedList() {
Console.WriteLine("\n\nDeleting Linked List...");
head = null;
if(tail == null) {
Console.WriteLine("Linked List is already deleted, nothing to delete !");
return;
}else {
tail.setNext(null);
tail = null;
Console.WriteLine("Linked List deleted successfully !");
}
}

Thank you guys, that's it for the Circular LL. I hope you enjoyed the article. :-)

3 Comments

Join the conversation! Your thoughts help the community grow.

patrick le breton6y ago
What about something simpler: /// <summary> /// simple rotating list /// </summary> /// <typeparam name="T"></typeparam> public class CircularList<T> { private List<T> _container; public T this[int index] { get { return _container[index % _container.Count]; } } public void Add(T item) { _container.Add(item); } public void Remove(T item) { _container.Remove(item); } public CircularList() { } public CircularList(IEnumerable<T> data) { _container = data.ToList(); } }
patrick le breton6y ago
What about:
Rikam Palkar6y ago
hey good job buddy m