Which application can be using the circular linked list to implement?

Circular Linked List | Set 1 [Introduction and Applications]

What is a Circular linked list?

A circular linked is very similar to a singly linked list, the only difference is in the singly linked list the last node of the list point to null but in the circular linked list the last node of the list point to the address of the head. This type of list is known as a circular linked list.

We can traverse all nodes starting from the head and stop when the next node is pointing to the head which indicates we have reached the last node.

Below is the figure of how circular linked list looks

While traversing the circular linked list, we have to break the loop if we find the next of the last node is equal to the head other we can go into an infinite loop.

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