Circular Linked List in C++ with Real-Time Example
Introduction
A Circular Linked List (CLL) is an advanced version of a singly linked list where:
-
The last node points back to the first node (head)
-
There is no NULL pointer at the end
-
The list forms a circle
This structure is useful in applications where data needs to be processed in a loop.
Objective
In this lab session, you will learn how to:
-
Create a circular linked list
-
Insert nodes into the list
-
Delete nodes from the list
-
Traverse all nodes efficiently
Real-Time Example
🔄 Example: Round-Robin CPU Scheduling
In operating systems, processes are scheduled in a circular manner:
-
After the last process executes, control returns to the first process
-
The cycle continues indefinitely
This behavior is perfectly modeled using a Circular Linked List.
Structure of a Node:
struct Node {
int data;
Node* next;
};
Complete C++ Implementation
1️⃣ Creation of Circular Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* last = NULL; // Points to last node
Node* createNode(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = newNode; // points to itself
return newNode;
}
2️⃣ Insertion Operations
➤ Insert at Beginning
void insertAtBeginning(int value) {
Node* newNode = createNode(value);
if (last == NULL) {
last = newNode;
} else {
newNode->next = last->next;
last->next = newNode;
}
}
➤ Insert at End
void insertAtEnd(int value) {
Node* newNode = createNode(value);
if (last == NULL) {
last = newNode;
} else {
newNode->next = last->next;
last->next = newNode;
last = newNode;
}
}
➤ Insert After a Specific Value
void insertAfterValue(int value, int afterValue) {
if (last == NULL) return;
Node* temp = last->next;
do {
if (temp->data == afterValue) {
Node* newNode = createNode(value);
newNode->next = temp->next;
temp->next = newNode;
if (temp == last)
last = newNode;
return;
}
temp = temp->next;
} while (temp != last->next);
cout << "Value not found\n";
}
3️⃣ Deletion Operations
➤ Delete from Beginning
void deleteFromBeginning() {
if (last == NULL) return;
Node* temp = last->next;
if (last == temp) {
last = NULL;
} else {
last->next = temp->next;
}
delete temp;
}
➤ Delete from End
void deleteFromEnd() {
if (last == NULL) return;
Node* temp = last->next;
if (temp == last) {
delete last;
last = NULL;
return;
}
while (temp->next != last) {
temp = temp->next;
}
temp->next = last->next;
delete last;
last = temp;
}
➤ Delete a Specific Value
void deleteValue(int value) {
if (last == NULL) return;
Node* curr = last->next;
Node* prev = last;
do {
if (curr->data == value) {
if (curr == last && curr == last->next) {
last = NULL;
} else {
prev->next = curr->next;
if (curr == last)
last = prev;
}
delete curr;
return;
}
prev = curr;
curr = curr->next;
} while (curr != last->next);
cout << "Value not found\n";
}
🗑️ Delete Complete Circular Linked List
void deleteEntireList() {
if (last == NULL) {
cout << "List is already empty\n";
return;
}
Node* current = last->next; // head node
Node* nextNode;
// Traverse and delete all nodes
do {
nextNode = current->next;
delete current;
current = nextNode;
} while (current != last->next);
last = NULL; // Reset last pointer
cout << "Entire list deleted successfully\n";
}
⚠️ Important Concept
In a Circular Linked List, there is no NULL termination, so:
-
You cannot use
while (temp != NULL) -
Instead, use a do-while loop
-
Stop when you reach the starting node again
4️⃣ Traversal of Nodes
void display() {
if (last == NULL) {
cout << "List is empty\n";
return;
}
Node* temp = last->next;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != last->next);
cout << "(back to head)\n";
}
🧪 Main Function (Testing)
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtBeginning(5);
insertAfterValue(15, 10);
cout << "Circular List: ";
display();
deleteFromBeginning();
deleteFromEnd();
deleteValue(15);
cout << "After Deletion: ";
display();
return 0;
}
/*
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
cout << "Before Deletion: ";
display();
deleteEntireList();
cout << "After Deletion: ";
display();
return 0;
}
*/
📊 Advantages of Circular Linked List
✔ No NULL pointers (efficient memory usage)
✔ Easy to traverse repeatedly
✔ Ideal for cyclic processes
⚠️ Disadvantages
❌ Complex logic compared to linear lists
❌ Infinite loop risk if not handled properly
🎓 Conclusion
A Circular Linked List is an efficient data structure for applications that require continuous looping, such as scheduling systems and real-time simulations.
By mastering creation, insertion, deletion, and traversal in C++, you strengthen your data structure fundamentals and problem-solving skills.
Graded Lab Tasks
Lab Task 1
Write a function that deletes all those nodes from a linked list which have even/odd numbered value in their data part.
Lab Task 2
Write a function that implements Josephus problem.
Lab Task 3
Write a function that deletes all even positioned nodes from a linked list. Last node should also be deleted if its position is even.
🧠 Lab Tasks (For Students)
-
Create a circular linked list with 5 nodes
-
Insert a node after a given value
-
Delete the first and last node
-
Search for a value in the list
-
Count total nodes in the circular list
📢 Call to Action
Stay updated with the latest tutorials, practical coding examples, and expert insights in programming and technology. Subscribe to our blog and enhance your learning journey with hands-on content! 🚀
