A circular linked list is used to loop your music playlist to implement a circular queue. A circular linked list is a unidirectional linked list; i.e., you can traverse it from head to tail. Unlike other linked lists, its tail points back at the head node. This tutorial will help you understand the fundamental technicalities of circular linked lists with all the necessary details and practical examples.
How to Implement a Circular Linked List?
You can create nodes of circular-linked lists using classes or structures. These nodes are then linked with each other using the next pointer.
Code:
//A c++ program to implement linked list
#include <bits/stdc++.h>
using namespace std;
//A class to create a node
class Node
{
public:
int data;
Node *next;
};
// a function to insert a node at the beginning
void push(Node **head, int data)
{
Node *newnode = new Node();
Node *temp = *head;
newnode->data = data;
newnode->next = *head;
//If linked list is not NULL then
//set the next of last node as newnode
if (*head != NULL)
{
while (temp->next != *head)
temp = temp->next;
temp->next = newnode;
}
else
newnode->next = newnode;
*head = newnode;//change head
}
//A function to print the linked list
void printList(Node *head)
{
Node *temp = head;
if (head != NULL)
{
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != head);
}
}
int main()
{
//we will start with empty list
Node *head = NULL;
// insert 12
push(&head, 12);//12->12
//insert 56
push(&head, 56);//56->12->56
//insert 2
push(&head, 2);//2->56->12->2
//Insert 11
push(&head, 11);//11->2->56->12->11
cout << "Created Linked List: \n ";
printList(head);
return 0;
}
What Operations Can You Perform on a Circular Linked List?
You can perform two types of operations on this kind of linked list:
- Insertion
- Deletion
How to Insert a Node in a Circular Linked List?
To insert a node, you need to change the previous node's next (if any) to the new node and the new node next to the previous node's next. You can insert a new node in three different locations.
- At the beginning of the list
- At the end of the list
- After a given node
Code:
//A c++ program to perform insertion.
#include<bits/stdc++.h>
using namespace std;
//A structure to create nodes
struct Node
{
int data;
struct Node *next;
};
//A function to insert in the empty list
struct Node *addToEmpty(struct Node *last, int data)
{
// Check if list is empty
if (last != NULL)
return last;
// Creating a node dynamically.
struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
last = temp;
// Creating the link.
last -> next = last;
return last;
}
//A function to insert at the beginning
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
return last;
}
//A function to insert at the end
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
//A function to insert after the given node
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
//A function to traverse and print the list
void traverse(struct Node *last)
{
struct Node *p;
// If the list is empty, return.
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
// Points to first node
p = last -> next;
// Traversing the list.
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
int main()
{
//start with empty list
struct Node *head = NULL;
//insert 6 in empty list
head = addToEmpty(head, 6);//6->6
//insert 4 at the beginning
head = addBegin(head, 4);//4->6->4
//insert 2 at the beginning
head = addBegin(head, 2);//2->4->6->2
//insert 8 at the end
head = addEnd(head, 8);//2->4->6->8->2
//insert 12 at the end
head = addEnd(head, 12);//2->4->6->8->12->2
//insert 10 after 8
head = addAfter(head, 10, 8);//2->4->6->8->10->12->2
traverse(head);
return 0;
}
How to Remove a Node From a Circular Linked List?
You need to change the previous node's next to the deleted node's next to delete a node. You can delete a node from three different positions.
- From the beginning of the list
- From the end of the list
- After a given node
Code:
//A C++ program to delete a given key
#include <bits/stdc++.h>
using namespace std;
// A class to create node
class Node {
public:
int data;
Node* next;
};
//A function to insert at the beginning
void push(Node** head, int data)
{
// Creating a newnode and make its next as head
Node* newnode = new Node();
newnode->data = data;
newnode->next = *head;
//If linked list is not empty
if (*head!= NULL)
{
// Find the node before head and update
// next to it.
Node* temp = *head;
while (temp->next != *head)
temp = temp->next;
temp->next = newnode;
}
else
newnode->next = newnode;
*head = newnode;
}
//A function to print the list
void printList(Node* head)
{
Node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
//A Function to delete a given node
void deleteNode(Node** headref, int key)
{
// If linked list is empty
if (*headref == NULL)
return;
// If the list has single node
if((*headref)->data==key && (*headref)->next==*headref)
{
free(*headref);
*headref=NULL;
return;
}
Node *last=*headref,*d;
// If the key is headref itself
if((*headref)->data==key)
{
// Find the last node of the list
while(last->next!=*headref)
last=last->next;
// Point last node to the next of headref i.e.
// the second node of the list
last->next=(*headref)->next;
free(*headref);
*headref=last->next;
}
//if key not found or end of the list not reached
while(last->next!=*headref && last->next->data!=key)
{
last=last->next;
}
// If node to be deleted was found
if(last->next->data==key)
{
d=last->next;
last->next=d->next;
free(d);
}
else
cout<<"no such key found";
}
/* Driver code */
int main()
{
// we will start list empty
Node* head = NULL;
//Created linked list will be 2->5->7->8->10
push(&head, 2);
push(&head, 5);
push(&head, 7);
push(&head, 8);
push(&head, 10);
cout << "List Before Deletion: ";
printList(head);
deleteNode(&head, 7);//delete 7
cout << "List After Deletion: ";
printList(head);
return 0;
}
What Are the Benefits of a Circular Linked List?
- You can traverse to any node from any node.
- It is faster to traverse from the last node to the first node.
- The circular linked list is beneficial in applications that require looping.
- You can implement complex data structures like circular queues.
What Are the Limitations of a Circular Linked List?
- It is hard to reverse traverse a circular linked list.
- While traversing, if not careful, you can end up in an infinite loop.
- Similar to singly linked lists and doubly linked lists, you can't directly access any element of the linked lists.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
"Stacks in data structure" will be your next stop. Stacks are nodes that are piled on one another. You can perform operations only on the top node. Stacks can be used to backtrack to the previous installation or to solve complex problems like N-Queens.
If you are perhaps looking to build a career in software development, explore Simplilearn’s Software Development Courses that will give you the work-ready software development training you need to succeed today.
If you have any questions about this article, please feel free to leave them in the comment section below. Our expert team is available 24/7 to answer all your queries for you at the earliest.
Happy learning!
