If you are not familiar with the LinkedList, I would highly recommend having a look at my blog:

Introduction to Linked List

In this tutorial, we will learn circular linked list in-depth by dividing topics in the following manner:

1. Definition of circular linked list.
2. Types of Circular linked list

3. Basic Operations on circular linked list

   a) Searching/Traversal
   b) Insertion
   c) Deletion

4. Singly linked list as a circular linked list.

5. Doubly linked list as a circular linked list.

6. Applications of circular linked list

7. Implementation of circular linked list.

Definition of circular linked list

In a circular linked list, elements are stored in random memory locations.
Similar to a singly linked list, each node of a circular linked list (I meant singly circular linked list) contains two fields:

1. data stored at that particular address.
2. Pointer which contains the address of the next node.

Unlike, singly linked list in which the last node of the contains a pointer to null to represent the termination of a linked list, in circular linked list, last node of linked list will point to the first node of the linked list.

Types of Circular Linked List:

There are two types of Circular linked list. i.e. we can make a circular linked list by modifying the Singly linked list as well as Doubly linked list.

1. Singly circular linked list

The above diagram is an example of a singly linked list in which the last node(Tail) points to NULL to represent the termination of the linked list.
To make it a singly circular linked list, you just need to modify the link of the last node.
Instead of pointing it to NULL, We are going to link it with the first(head) node.

Now, one question which might come into your mind is, how do we get to know termination condition, right?
Because, if we don’t apply termination condition our program will run into an infinite loop. Confused? 😕 😕 😕 😕 😕

Well, one thing you might do is, keep a track of head node and whenever we encounter it again, we say that we have traversed our whole linked list and Now it is time to terminate.
You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.

if (temp==head) ===> We have traversed whole linked list.
Well, it was just a brief explanation, we will see it via code in detail, later in this tutorial.

2. Doubly circular linked list

The above diagram is an example of doubly linked list in which the prev of head points to NULL and last node(Tail) points to NULL to represent the termination of linked list.
To make it a Doubly Circular Linked List, you just need to modify the link of the last node.
Instead of pointing next of last node (lastNode->next) to NULL, We are going to link it with first(head) node.
Moreover, the prev of first node (head->prev) will point to the last node.

In this case, keep a track of head node and whenever we encounter it again, we say that we have traversed whole linked list and now it is time to terminate.

You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.
if temp==head -----> We have traversed whole linked list.

Operations on Circular linked list

A. Traversal

Traversal in Circular linked list is similiar to singly or doubly linked list, we just need to take care of termination condition. In this case termination condition would be, If we reach again to our head node.

To perform this task do the following:
Take a temp node and store head ->next into it, now run a loop untill temp!=head and search for given element.
If we reach head ===> (temp==head): terminate loop.

Node *temp=head->next;
while(temp!=head)
{
  if(temp->data==ElementToFind) {
    cout<<"Element found"<<endl;
    break;
  }
  temp=temp->next;
}

B. Insertion

Insertion in Circular linked list will be exactly same as in singly linked list except inseting node at front and at last position.

• Inserting node in Between two nodes

• Inserting node at front

To insert a node at front, We need to know about the last node of linked list.
Hence we will traverse the whole linked list and reach to end of it.

Create a new node and link it with exisiting list as mentioned below:

LastNode->next=newNode;
newNode->next=head;

After, linking nodes, we need to update the head of linked list as we are inserting at the front and front node represent the head of linked list.
In our case, newNode would be our new head now.

head=newNode;

• Inserting node at last

It is similiar to inserting node at front. The only difference is that we don't need to update head in this case.

C. Deletion

• Deleting in between node

To delete in between node, find prev and next node of the node which needs to be deleted.

curr = head;
while(curr!=nodetoDelete) { 
   prev = curr;
   curr = curr->next;
}
prev->next=curr->next;
delete curr;

• Deleting node at front

To delete a Node from front, We need to know about the last node of linked list.
Hence we will traverse the whole linked list and reach to end of it.

ptr = head;  
while(ptr ->next != head) {  
       ptr = ptr->next;  
}  
temp = head;
ptr -> next = temp->next;
// update head node
head =head->next;
delete temp; 

• Deleting last node

It is similiar to deleting node at front. The only difference is that we won't be updating head in this case.

ptr = head;  
while(ptr ->next != head) {  
       preptr=ptr;  
       ptr = ptr->next;  
}  
preptr->next = ptr -> next;  

D. Advantages of Circular linked list

1. In a circular linked list, there is no requirement for a NULL assignment in the code. The good thing about a circular linked list is that It never points to a NULL pointer unless fully deallocated.

2. Circular linked lists are always good and advantageous for the end operations since the beginning and the end of circular linked list coincide with each other.

3. Many algorithms such as the Round Robin scheduling which uses queue can efficiently and easily eliminate processes that are queued in a circular way or fashion without encountering any dangling pointers or NULL-referential
   pointers.

4. The biggest advantage with a circular linked list is that It also performs all regular functions of a singly/doubly linked list along with additional features.

E. Disadvantage of circular linked list

1. Insertion at all positions (first node, last node, and In-between) takes O(n) time while in singly linked list insertion at first node takes O(1) time.

2. Deletion at all positions (first Node, Last Node, and In-between) takes O(n) time while in singly linked list deletion at first node takes O(1) time.

3. If we don’t apply the termination condition properly, our code might lead to infinite loop.

F. Applications of Circular linked list

1. If I talk about the real-life application of a circular linked list, It would be none other than our personal computers, which are capable of running multiple applications at a time. Computers process all applications in this manner that all running applications are kept in a queue which is implemented using a circular linked list and the operating system gives a fixed time(could be an example of Round Robin CPU Scheduling Process) slot know as time quantum to all for running processes.
   The operating system keeps on iterating over the
   circular linked list and keeps executing processes and removing them from waiting for queue until all the applications are executed/completed successfully.

2. We can also take an example multiplayer games in which all the players are kept in a queue which is implemented via a circular linked list and the pointer keeps on moving forward as the chance of a particular player ends.

3. We can also take an example of the circular linked list which can also be used to create a circular queue.
   The problem with a given queue is that we need to keep two pointers one for FRONT and another for REAR in memory all the time to implement a queue.
   But with the help of a Circular linked list we can do this task easily and efficiently because, in a circular linked list, only one pointer is required.

4. Circular linked list is also used in token rings scheduling in computer networks.

5. Circular linked list is used to display units like shop boards that require continuous traversal of data.

G. Implementation

#include <bits/stdc++.h>
using namespace std;
class NodeTaslim {
  public:
  int data;
  NodeTaslim *next;
  NodeTaslim() { 
    data = 0;
    next = NULL;
  }
  NodeTaslim(int x) {
    data = x;
    next = NULL;
  }
};


class CircularLinkedList {
   public:
   NodeTaslim *head;

   /* Insert at front */
   int addAtFront(int value);

   /* check list is empty or not */
   int isEmpty();

   /* Insert at end */
   int addAtEnd(int value);

   /* Search for an element in list */
   NodeTaslim *search(int k);

   /* Delete a node */
   NodeTaslim *deleteNode(int x);

   CircularLinkedList() {
     head = NULL;
   }
};

/* Find last Node of Linked List */
NodeTaslim *getLastNode(NodeTaslim *head) {
   NodeTaslim *temp = head;
   while (temp->next != head) {
     temp = temp->next;
   }
   return temp;
}

/* Add a Node at Front */
int CircularLinkedList ::addAtFront(int value)
{
   int i = 0;
   NodeTaslim *n = new NodeTaslim(value);
   /* Check list is empty or not */
   if (head == NULL) {
       n->next = head;
       head = n;
       i++;
   }
   else {
      NodeTaslim *last = getLastNode(head);
      n->next = head;
      last->next = n;
      head = n;
      i++;
   }
   return i;
}

/* Add a Node at Last */
int CircularLinkedList ::addAtEnd(int value) {
   NodeTaslim *n = new NodeTaslim(value);
   if (head == NULL) {
       head = n;
       n->next = NULL;
   }
   else {
       NodeTaslim *last = getLastNode(head);
       last->next = n;
       n->next = head;
   }
}

/* Search an Element in List */
NodeTaslim *CircularLinkedList ::search(int x) {
     NodeTaslim *ptr = head;
     while (ptr != NULL && ptr->data != x) {
           ptr = ptr->next;
     }
     return ptr;
}

/* Remove Node from List */
NodeTaslim *CircularLinkedList ::deleteNode(int x) {
    NodeTaslim *n = search(x);
    NodeTaslim *ptr1 = head;
    if (ptr1 == NULL) {
      cout << "List is empty";
      return NULL;
    }
    /*Remove first node*/
    else if (ptr1 == n) {
      ptr1->next = n->next;
      return n;
    }
    else {
      while (ptr1->next != n) {
         ptr1 = ptr1->next;
      }
      ptr1->next = n->next;
      return n;
    }
}