What is circular linked list explain with its all operations?

Data Structure - Circular Linked List

Circular Linked List | Set 1 (Introduction and Applications)

We have discussed singly and doubly linked lists in the following posts.

Introduction to Linked List & Insertion
Doubly Linked List Introduction and Insertion

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.

2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Next Posts :
Circular Linked List | Set 2 (Traversal)
Circular Singly Linked List | Insertion

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

Article Tags :

Linked List

circular linked list

Practice Tags :

Linked List

circular linked list

Read Full Article

Circular Linked List

Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.

Application of Circular Linked List

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

class Node { public: int data; //pointer to the next node node* next; node() { data = 0; next = NULL; } node(int x) { data = x; next = NULL; } }

Circular Linked List

Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods.

class CircularLinkedList { public: node *head; //declaring the functions //function to add Node at front int addAtFront(node *n); //function to check whether Linked list is empty int isEmpty(); //function to add Node at the End of list int addAtEnd(node *n); //function to search a value node* search(int k); //function to delete any Node node* deleteNode(int x); CircularLinkedList() { head = NULL; } }

Insertion at the Beginning

Steps to insert a Node at beginning :

The first Node is the Head for any Linked List.
When a new Linked List is instantiated, it just has the Head, which is Null.
Else, the Head holds the pointer to the fisrt Node of the List.
When we want to add any Node at the front, we must make the head point to it.
And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.

int CircularLinkedList :: addAtFront(node *n) { int i = 0; /* If the list is empty */ if(head == NULL) { n->next = head; //making the new Node as Head head = n; i++; } else { n->next = head; //get the Last Node and make its next point to new Node Node* last = getLastNode(); last->next = n; //also make the head point to the new first Node head = n; i++; } //returning the position where Node is added return i; }

Insertion at the End

Steps to insert a Node at the end :

If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the Newly added Node point to the Head of the List.

int CircularLinkedList :: addAtEnd(node *n) { //If list is empty if(head == NULL) { //making the new Node as Head head = n; //making the next pointer of the new Node as Null n->next = NULL; } else { //getting the last node node *last = getLastNode(); last->next = n; //making the next pointer of new node point to head n->next = head; } }

Searching for an Element in the List

In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.

node* CircularLinkedList :: search(int x) { node *ptr = head; while(ptr != NULL && ptr->data != x) { //until we reach the end or we find a Node with data x, we keep moving ptr = ptr->next; } return ptr; }

Deleting a Node from the List

Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.

To remove any Node from the list, we need to do the following :

If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
If the Node is at the end, then remove it and make the new last node point to the head.

node* CircularLinkedList :: deleteNode(int x) { //searching the Node with data x node *n = search(x); node *ptr = head; if(ptr == NULL) { cout << "List is empty"; return NULL; } else if(ptr == n) { ptr->next = n->next; return n; } else { while(ptr->next != n) { ptr = ptr->next; } ptr->next = n->next; return n; } }

← Prev
Next →

Circular Singly Linked List

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked list as well as circular doubly linked list.

We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.

The following image shows a circular singly linked list.

Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.

Circular Linked List In C++

The arrangement shown below is for a singly linked list.

A circular linked list can be a singly linked list or a doubly linked list. In a doubly circular linked list, the previous pointer of the first node is connected to the last node while the next pointer of the last node is connected to the first node.

Its representation is shown below.

Declaration

We can declare a node in a circular linked list as any other node as shown below:

struct Node { int data; struct Node *next; };

In order to implement the circular linked list, we maintain an external pointer “last” that points to the last node in the circular linked list. Hence last->next will point to the first node in the linked list.

By doing this we ensure that when we insert a new node at the beginning or at the end of the list, we need not traverse the entire list. This is because the last points to the last node while last->next points to the first node.

This wouldn’t have been possible if we had pointed the external pointer to the first node.

Basic Operations

The circular linked list supports insertion, deletion, and traversal of the list. We will discuss each of the operations in detail now.

Insertion

We can insert a node in a circular linked list either as a first node (empty list), in the beginning, in the end, or in between the other nodes. Let us see each of these insertion operations using a pictorial representation below.

#1) Insert in an empty list

When there are no nodes in circular list and the list is empty, the last pointer is null, then we insert a new node N by pointing the last pointer to the node N as shown above. The next pointer of N will point to the node N itself as there is only one node. Thus N becomes the first as well as last node in the list.

#2) Insert at the beginning of the list

As shown in the above representation, when we add a node at the beginning of the list, the next pointer of the last node points to the new node N thereby making it a first node.

N->next = last->next

Last->next = N

#3) Insert at the end of the list

To insert a new node at the end of the list, we follow these steps:

N-> next = last ->next;
last ->next = N
last = N

#4) Insert in between the list

Suppose we need to insert a new node N between N3 and N4, we first need to traverse the list and locate the node after which the new node is to be inserted, in this case, its N3.

After the node is located, we perform the following steps.

N -> next = N3 -> next;
N3 -> next = N

This inserts a new node N after N3.

Deletion

The deletion operation of the circular linked list involves locating the node that is to be deleted and then freeing its memory.

For this we maintain two additional pointers curr and prev and then traverse the list to locate the node. The given node to be deleted can be the first node, the last node or the node in between. Depending on the location we set the curr and prev pointers and then delete the curr node.

A pictorial representation of the deletion operation is shown below.

Traversal

Traversal is a technique of visiting each and every node. In linear linked lists like singly linked list and doubly linked lists, traversal is easy as we visit each node and stop when NULL is encountered.

However, this is not possible in a circular linked list. In a circular linked list, we start from the next of the last node which is the first node and traverse each node. We stop when we once again reach the first node.

Now we present an implementation of the circular linked list operations using C++ and Java. We have implemented insertion, deletion and traversal operations here. For a clear understanding, we have depicted the circular linked list as

Thus to the last node 50, we again attach node 10 which is the first node, thereby indicating it as a circular linked list.

#include<iostream> using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << "The node with data "<<after_item << " is not present in the list." << endl; return last; } //traverse the circular linked list void traverseList(struct Node *last) { struct Node *p; // If list is empty, return. if (last == NULL) { cout << "Circular linked List is empty." << endl; return; } p = last -> next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout << p -> data << "==>"; p = p -> next; } while(p != last->next); if(p == last->next) cout<<p->data; cout<<"\n\n"; } //delete the node from the list void deleteNode(Node** head, int key) { // If linked list is empty retun if (*head == NULL) return; // If the list contains only a single node,delete that node; list is empty if((*head)->data==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<"The node with data "<<key<<" deleted from the list"<<endl; free(d); cout<<endl; cout<<"Circular linked list after deleting "<<key<<" is as follows:"<<endl; traverseList(last); } else cout<<"The node with data "<< key << " not found in the list"<<endl; } // main Program int main() { struct Node *last = NULL; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = insertAfter(last, 50,40 ); cout<<"The circular linked list created is as follows:"<<endl; traverseList(last); deleteNode(&last,10); return 0; }

Output:

Thecircularlinkedlistcreatedisasfollows:

10==>20==>30==>40==>50==>60==>10

The node with data 10 is deleted from the list

Circularlinkedlistafterdeleting10isasfollows:

20==>30==>40==>50==>60==>20

Next, we present a Java implementation for the Circular linked list operations.

//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println("The node with data " + after_item + " not present in the list."); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println("Cicular linked List is empty."); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + "==>"); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print("\n\n"); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf("\nGiven node " + key + " is not found" + “in the list!"); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println("After deleting " + key + " the circular list is:"); traverse(head); return head; } // Main code public static void main(String[] args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println("Circular linked list created is:"); traverse(last); last = deleteNode(last,40); } }

Output:

Circularlinkedlistcreatedis:

10==>20==>30==>40==>50==>60==>10

Afterdeleting40thecircularlistis:

10==>20==>30==>50==>60==>10

Advantages/Disadvantages

Let us discuss some advantages and disadvantages of the circular linked list.

Advantages:

We can go to any node and traverse from any node. We just need to stop when we visit the same node again.
As the last node points to the first node, going to the first node from the last node just takes a single step.

Disadvantages:

Reversing a circular linked list is cumbersome.
As the nodes are connected to form a circle, there is no proper marking for beginning or end for the list. Hence, it is difficult to find the end of the list or loop control. If not taken care, an implementation might end up in an infinite loop.
We cannot go back to the previous node in a single step. We have to traverse the entire list from first.

Applications Of Circular Linked List

Real-time application of circular linked list can be a multi-programming operating system wherein it schedules multiple programs. Each program is given a dedicated timestamp to execute after which the resources are passed to another program. This goes on continuously in a cycle. This representation can be efficiently achieved using a circular linked list.
Games that are played with multiple players can also be represented using a circular linked list in which each player is a node that is given a chance to play.
We can use a circular linked list to represent a circular queue. By doing this, we can remove the two pointers front and rear that is used for the queue. Instead, we can use only one pointer.

Conclusion

A circular linked list is a collection of nodes in which the nodes are connected to each other to form a circle. This means instead of setting the next pointer of the last node to null, it is linked to the first node.

A circular linked list is helpful in representing structures or activities which need to be repeated again and again after a specific time interval like programs in a multiprogramming environment. It is also beneficial for designing a circular queue.

Circular linked lists support various operations like insertion, deletion, and traversals. Thus we have seen the operations in detail in this tutorial.

In our next topic on data structures, we will learn about the stack data structure.

=> Check Here To See A-Z Of C++ Training Tutorials Here.