Introduction to Circular Linked List
A circular linked list is a data structure where the last node points back to
the first node, forming a closed loop.
Structure: All nodes are connected in a circle, enabling continuous
traversal without encountering NULL.
Difference from Regular Linked List: In a regular linked list, the last
node points to NULL, whereas in a circular linked list, it points to the first
node.
Uses: Ideal for tasks like scheduling and managing playlists, where
smooth and repeated.
Types of Circular Linked Lists
We can create a circular linked list from both singly linked lists and doubly
linked lists. So, circular linked lists are basically of two types:
1. Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer called the
"next" pointer. The next pointer of the last node points back to the first
node and this results in forming a circle. In this type of Linked list, we can
only move through the list in one direction.
2. Circular Doubly Linked List:
In circular doubly linked list, each node has two pointers prev and next,
similar to doubly linked list. The prev pointer points to the previous node
and the next points to the next node. Here, in addition to the last node
storing the address of the first node, the first node will also store the
address of the last node.
Representation of a Circular Singly Linked List
Let's take a look on the structure of a circular linked list.
Create/Declare a Node of Circular Linked List
Here’s an example of creating a circular linked list with three nodes (10,
20, 30, 40, 50):
Why have we taken a pointer that points to the last node
instead of the first node?
For the insertion of a node at the beginning, we need to traverse the
whole list. Also, for insertion at the end, the whole list has to be traversed.
If instead of the start pointer, we take a pointer to the last node, then in
both cases there won't be any need to traverse the whole list. So insertion
at the beginning or at the end takes constant time, irrespective of the
length of the list.
Advantage of Circular Linked List
Efficient Traversal
No Null Pointers / References
Useful for Repetitive Tasks
Insertion at Beginning or End is O(1)
Uniform Traversal
Efficient Memory Utilization
Disadvantage of Circular Linked List
Complex Implementation
Infinite Loop Risk
Harder to Debug
Deletion Complexity
Memory Overhead (for Doubly Circular LL)
Not Cache Friendly
Operations on the Circular Linked List
Insertion : At the Beginning, At the End and At a Specific Position
Deletion : Removal from different positions
Insertion at the beginning in circular linked list
Step-by-step approach:
Create a new node with the given value.
Check Empty List (last == nullptr):
o Make newNode->next point to itself.
Insert at Beginning:
o Set newNode->next to last->next.
o Update last->next to newNode.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = nullptr;
};
Node* insertAtBeginning(Node* last, int key) {
Node* newNode = new Node(key);
if (last == nullptr) {
newNode->next = newNode;
return newNode;
newNode->next = last->next;
last->next = newNode;
return last;
void printList(Node* last) {
if (last == nullptr) return;
Node* head = last->next;
Node* temp = head;
do {
cout << temp->data;
temp = temp->next;
if (temp != head) cout << " -> ";
} while (temp != head);
cout << endl;
int main() {
// Create circular linked list: 2 -> 3 -> 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node* last = first->next->next;
last->next = first;
// Insert 5 at the beginning
last = insertAtBeginning(last, 5);
printList(last);
return 0;
Output
5 -> 2 -> 3 -> 4
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion at the end in circular linked list
A circular linked list is a data structure where each node points to the
next, and the last node connects back to the first, creating a
loop. Insertion at the end in circular linked list is an important
operation.
Insertion at the end in circular linked list
To insert a new node at the end of a circular linked list, we first create the
new node and allocate memory for it. If the list is empty (mean, last or tail
pointer being NULL), we initialize the list with the new node and making it
point to itself to form a circular structure. If the list already contains nodes
then we set the new node’s next pointer to point to the current head
(which is tail->next), then update the current tail's next pointer to point to
the new node. Finally, we update the tail pointer to the new node. This
will ensure that the new node is now the last node in the list while
maintaining the circular linkage.
Step-by-step approach:
Create a new node with the given value.
Check Empty List, If last is nullptr then initialize the list with the new
node and make it point to itself.
Otherwise, Set the new node's next to the head node.
Update the current last's next to point to the new node.
Update last to the new node.
#include <iostream>
using namespace std;
struct Node{
int data;
Node *next;
Node(int value)
data = value;
next = nullptr;
};
// Function to insert a node at the end of a circular linked list
Node *insertEnd(Node *tail, int value)
Node *newNode = new Node(value);
if (tail == nullptr){
// If the list is empty, initialize it with the new node
tail = newNode;
// Point to itself to form a circular structure
newNode->next = newNode;
else{
// Insert new node after the current tail
// and update the tail pointer.
// New node points to the head node
newNode->next = tail->next;
// Tail node points to the new node
tail->next = newNode;
// Update tail to be the new node
tail = newNode;
return tail;
void printList(Node *last){
if(last == NULL) return;
// Start from the head node
Node *head = last->next;
while (true){
cout << head->data << " ";
head = head->next;
if (head == last->next)
break;
cout << endl;
int main(){
// Create circular linked list: 2, 3, 4
Node *first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node *last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
// Insert elements at the end of the circular linked list
last = insertEnd(last, 5);
last = insertEnd(last, 6);
cout << "List after inserting 5 and 6: ";
printList(last);
return 0;
Output
Original list: 2 3 4
List after inserting 5 and 6: 2 3 4 5 6
Time Complexity: O(1)
Auxiliary Space: O(1)
