Updated March 31, 2023
Introduction to Circular linked list in C++
The following article provides an outline for a circular linked list in C++. A Circular Linked list is a series of elements where each and every element has points to its next element in the series, and the last element points to the first element. Here the previous node stores the address of the next node, and the last node stores address of the initial node. Elements in the list map to each other circularly, which looks like a circular chain. The memory will be allocated whenever needed in a circular linked list, so their size is dynamic.
Syntax
Let’s see the declaration syntax of the circular linked list as follows,
struct Node
{
int data_;
struct Node *next_;
};To implementing the linked list to maintain the pointer “last”, this links to the last node in the circular linked list.
How Circular linked list works in C++?
The circular linked list is a variant of a linked list, where nodes are linked within several formats to form a circular chain. In this, the next pointer of the last node is not null; it contains the addresses of the initial node to form a circular chain.
A circular linked list supports several operations such as insertion, deletion, and traversal of the list.
Insertion of the List
In the circular linked list, there are of three insertion operations were performed; they are
- Inserting_at_beginning
- Inserting_at_end
- Inserting_at_specificNode
Deletion of the List
In the circular linked list, there are of three deletion operations were performed; they are
- Deleting_at_beginning
- Deleting_at_end
- Deleting_at_specificNode
Traversing Circular Linked List
Traversing a list is nothing but displaying the elements of a circular linked list; the display process is as follows,
if (last_ == NULL)
{
cout << "Circular linked List is Empty." << endl;
return;
}
p = last_ -> next;
// Traversing from starting to end circularly till it reaches again
do {
cout << p -> data << "==>";
p = p -> next;
} while(p != last_->next);
if(p == last_->next)
cout<<p->data;
cout<<"\n\n";
}- First to check whether the list is empty that is head = = NULL
- If the list is empty, it displays as “List is Empty”, and it exits the function
- If the list is not empty, it defines a pointer ‘temp’ and initializes the head node. It keeps displaying the data as temp data until temp reaches the last node.
- Finally, it displays temp data with a pointer to head data.
Examples of Circular linked list in C++
Let’s see the Circular linked list with several operations such as insertion, deletion, and traversal of the list programmatically as follows,
Code:
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
//inserting new-node at empty list
struct Node *Inserting_At_Empty(struct Node *last_, int new_data)
{
// return last, if the list is not empty and the last node is not null
if (last_ != NULL)
return last_;
// to allocating memory for new-node
struct Node *temp = new Node;
// to assign the data.
temp -> data = new_data;
last_ = temp;
// to create the link.
last_->next = last_;
return last_;
}
//to demonstrate - inserting new-node at the beginning list
struct Node *Inserting_At_Begin(struct Node *last_, int new_data)
{
// call the function - Inserting_At_Empty() to add a node, if list is empty
if (last_ == NULL)
return Inserting_At_Empty(last_, new_data);
//else to create a new_node
struct Node *temp = new Node;
//to set new_data to node
temp -> data = new_data;
temp -> next = last_ -> next;
last_ -> next = temp;
return last_;
}
//to insert new_node in the list - Inserting_At_End
struct Node *Inserting_At_End(struct Node *last_, int new_data)
{
//call function - Inserting_At_Empty and add the node,if list is empty
if (last_ == NULL)
return Inserting_At_Empty(last_, new_data);
//else to create new_node
struct Node *temp = new Node;
//to assigning new_node
temp -> data = new_data;
temp -> next = last_ -> next;
last_ -> next = temp;
last_ = temp;
return last_;
}
//inserting in between the nodes
struct Node *Inserting_After(struct Node *last_, int new_data, int after_item)
{
//if list is empty- to return null
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 << "Node Data "<<after_item << " is not present in the list." << endl;
return last_;
}
//to traversing the list in circular way
void Traversing_List(struct Node *last_) {
struct Node *p;
//return- If list is empty
if (last_ == NULL) {
cout << "Circular linked List is Empty." << endl;
return;
}
p = last_ -> next; // in the list it Points to the first-Node
// Traversing from starting to end circularly till it reaches again
do {
cout << p -> data << "==>";
p = p -> next;
} while(p != last_->next);
if(p == last_->next)
cout<<p->data;
cout<<"\n\n";
}
//to delete the node
void Deleting_Node(Node** head, int key)
{
// If linked list is empty return
if (*head == NULL)
return;
if((*head)->data==key && (*head)->next==*head) {
free(*head);
*head=NULL;
}
Node *last_=*head,*d;
// If head-key
if((*head)->data==key) {
while(last_->next!=*head) // Finding last node
last_=last_->next;
last_->next=(*head)->next;
free(*head);
*head=last_->next;
}
while(last_->next!=*head&&last_->next->data!=key) {
last_=last_->next;
}
// if deleted node found then to freeing the memory space to display it
if(last_->next->data==key) {
d=last_->next;
last_->next=d->next;
cout<<"Deletion Process\n";
cout<<"Node-Data " <<key<<" Deleted from list"<<endl;
free(d);
cout<<endl;
cout<<"Once deletion done, the Circular linked list "<<key<<" as follows:"<<endl;
Traversing_List(last_);
}
else
cout<<"Node-Data"<< key << " not in the list"<<endl;
}
// main function
int main()
{
struct Node *last_ = NULL;
last_ = Inserting_At_Empty(last_, 25);
last_ = Inserting_At_Begin(last_, 55);
last_ = Inserting_At_Begin(last_, 65);
last_ = Inserting_At_End(last_, 15);
last_ = Inserting_At_End(last_, 75);
last_ = Inserting_After(last_, 55,75 );
cout<<"Circular Linked List\n";
cout<<"--------------------\n";
cout<<"Circular Linked List is Created:\n"<<endl;
Traversing_List(last_);
Deleting_Node(&last_,15);
return 0;
}
When a node is not present in the list
Recommended Articles
This is a guide to Circular linked list in C++. Here we discuss the Circular Linked List, which is a collection of nodes where every node links to form a circle. You may also look at the following articles to learn more –
