A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.
There are basically two types of circular linked list:
1. Circular Singly Linked List
Here, the address of the last node consists of the address of the first node.
2. Circular Doubly Linked List
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.
Note: We will be using the singly circular linked list to represent the working of circular linked list.
Representation of Circular Linked List
Let's see how we can represent a circular linked list on an algorithm/code. Suppose we have a linked list:
Here, the single node is represented as
struct Node {
int data;
struct Node * next;
};
Each struct node has a data item and a pointer to the next struct node.
Now we will create a simple circular linked list with three items to understand how this works.
/* Initialize nodes */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;
/* Save address of third node in last */
last = three;
In the above code, one, two, and three are the nodes with data items 1, 2, and 3 respectively.
For node one
- next stores the address of two (there is no node before it)
For node two
- next stores the address of three
For node three
- next stores
NULL(there is no node after it) - next points to node one
Insertion on a Circular Linked List
We can insert elements at 3 different positions of a circular linked list:
Suppose we have a circular linked list with elements 1, 2, and 3.
Let's add a node with value 6 at different positions of the circular linked list we made above. The first step is to create a new node.
- allocate memory for
newNode - assign the data to
newNode
1. Insertion at the Beginning
- store the address of the current first node in the
newNode(i.e. pointing thenewNodeto the current first node) - point the last node to
newNode(i.e makingnewNodeas head)
2. Insertion in between two nodes
Let's insert newNode after the first node.
- travel to the node given (let this node be
p) - point the
nextofnewNodeto the node next top - store the address of
newNodeatnextofp
3. Insertion at the end
- store the address of the head node to
nextof newNode (makingnewNodethe last node) - point the current last node to
newNode - make
newNodeas the last node
Deletion on a Circular Linked List
Suppose we have a double-linked list with elements 1, 2, and 3.
1. If the node to be deleted is the only node
- free the memory occupied by the node
- store NULL in
last
2. If last node is to be deleted
- find the node before the last node (let it be
temp) - store the address of the node next to the last node in
temp - free the memory of last
- make
tempas the last node
3. If any other nodes are to be deleted
- travel to the node to be deleted (here we are deleting node 2)
- let the node before node 2 be
temp - store the address of the node next to 2 in
temp - free the memory of 2
Circular Linked List Code in Python, Java, C, and C++
# Python code to perform circular linked list operations
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.last = None
def addToEmpty(self, data):
if self.last != None:
return self.last
# allocate memory to the new node and add data to the node
newNode = Node(data)
# assign last to newNode
self.last = newNode
# create link to iteself
self.last.next = self.last
return self.last
# add node to the front
def addFront(self, data):
# check if the list is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the current first node in the newNode
newNode.next = self.last.next
# make newNode as last
self.last.next = newNode
return self.last
# add node to the end
def addEnd(self, data):
# check if the node is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the last node to next of newNode
newNode.next = self.last.next
# point the current last node to the newNode
self.last.next = newNode
# make newNode as the last node
self.last = newNode
return self.last
# insert node after a specific node
def addAfter(self, data, item):
# check if the list is empty
if self.last == None:
return None
newNode = Node(data)
p = self.last.next
while p:
# if the item is found, place newNode after it
if p.data == item:
# make the next of the current node as the next of newNode
newNode.next = p.next
# put newNode to the next of p
p.next = newNode
if p == self.last:
self.last = newNode
return self.last
else:
return self.last
p = p.next
if p == self.last.next:
print(item, "The given node is not present in the list")
break
# delete a node
def deleteNode(self, last, key):
# If linked list is empty
if last == None:
return
# If the list contains only a single node
if (last).data == key and (last).next == last:
last = None
temp = last
d = None
# if last node is to be deleted
if (last).data == key:
# find the node before the last node
while temp.next != last:
temp = temp.next
# point temp node to the next of last i.e. first node
temp.next = (last).next
last = temp.next
# travel to the node to be deleted
while temp.next != last and temp.next.data != key:
temp = temp.next
# if node to be deleted was found
if temp.next.data == key:
d = temp.next
temp.next = d.next
return last
def traverse(self):
if self.last == None:
print("The list is empty")
return
newNode = self.last.next
while newNode:
print(newNode.data, end=" ")
newNode = newNode.next
if newNode == self.last.next:
break
# Driver Code
if __name__ == "__main__":
cll = CircularLinkedList()
last = cll.addToEmpty(6)
last = cll.addEnd(8)
last = cll.addFront(2)
last = cll.addAfter(10, 2)
cll.traverse()
last = cll.deleteNode(last, 8)
print()
cll.traverse()
// Java code to perform circular linked list operations
class CircularLinkedList {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node last, int data) {
if (last != null)
return last;
// allocate memory to the new node
Node newNode = new Node();
// assign data to the new node
newNode.data = data;
// assign last to newNode
last = newNode;
// create link to iteself
newNode.next = last;
return last;
}
// add node to the front
static Node addFront(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the current first node in the newNode
newNode.next = last.next;
// make newNode as head
last.next = newNode;
return last;
}
// add node to the end
static Node addEnd(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the head node to next of newNode
newNode.next = last.next;
// point the current last node to the newNode
last.next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
static Node addAfter(Node last, int data, int item) {
if (last == null)
return null;
Node newNode, p;
p = last.next;
do {
// if the item is found, place newNode after it
if (p.data == item) {
// allocate memory to the new node
newNode = new Node();
// add data to the node
newNode.data = data;
// make the next of the current node as the next of newNode
newNode.next = p.next;
// put newNode to the next of p
p.next = newNode;
// if p is the last node, make newNode as the last node
if (p == last)
last = newNode;
return last;
}
p = p.next;
} while (p != last.next);
System.out.println(item + "The given node is not present in the list");
return last;
}
// delete a node
static Node deleteNode(Node last, int key) {
// if linked list is empty
if (last == null)
return null;
// if the list contains only a single node
if (last.data == key && last.next == last) {
last = null;
return last;
}
Node temp = last, d = new Node();
// if last is to be deleted
if (last.data == key) {
// find the node before the last node
while (temp.next != last) {
temp = temp.next;
}
// point temp node to the next of last i.e. first node
temp.next = last.next;
last = temp.next;
}
// travel to the node to be deleted
while (temp.next != last && temp.next.data != key) {
temp = temp.next;
}
// if node to be deleted was found
if (temp.next.data == key) {
d = temp.next;
temp.next = d.next;
}
return last;
}
static void traverse(Node last) {
Node p;
if (last == null) {
System.out.println("List is empty.");
return;
}
p = last.next;
do {
System.out.print(p.data + " ");
p = p.next;
}
while (p != last.next);
}
public static void main(String[] args) {
Node last = null;
last = addToEmpty(last, 6);
last = addEnd(last, 8);
last = addFront(last, 2);
last = addAfter(last, 10, 2);
traverse(last);
deleteNode(last, 8);
traverse(last);
}
}
// C code to perform circular linked list operations
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data) {
if (last != NULL) return last;
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to the new node
newNode->data = data;
// assign last to newNode
last = newNode;
// create link to iteself
last->next = last;
return last;
}
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the current first node in the newNode
newNode->next = last->next;
// make newNode as head
last->next = newNode;
return last;
}
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the head node to next of newNode
newNode->next = last->next;
// point the current last node to the newNode
last->next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
// check if the list is empty
if (last == NULL) return NULL;
struct Node *newNode, *p;
p = last->next;
do {
// if the item is found, place newNode after it
if (p->data == item) {
// allocate memory to the new node
newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// make the next of the current node as the next of newNode
newNode->next = p->next;
// put newNode to the next of p
p->next = newNode;
// if p is the last node, make newNode as the last node
if (p == last) last = newNode;
return last;
}
p = p->next;
} while (p != last->next);
printf("\nThe given node is not present in the list");
return last;
}
// delete a node
void deleteNode(struct Node** last, int key) {
// if linked list is empty
if (*last == NULL) return;
// if the list contains only a single node
if ((*last)->data == key && (*last)->next == *last) {
free(*last);
*last = NULL;
return;
}
struct Node *temp = *last, *d;
// if last is to be deleted
if ((*last)->data == key) {
// find the node before the last node
while (temp->next != *last) temp = temp->next;
// point temp node to the next of last i.e. first node
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
// travel to the node to be deleted
while (temp->next != *last && temp->next->data != key) {
temp = temp->next;
}
// if node to be deleted was found
if (temp->next->data == key) {
d = temp->next;
temp->next = d->next;
free(d);
}
}
void traverse(struct Node* last) {
struct Node* p;
if (last == NULL) {
printf("The list is empty");
return;
}
p = last->next;
do {
printf("%d ", p->data);
p = p->next;
} while (p != last->next);
}
int main() {
struct Node* last = NULL;
last = addToEmpty(last, 6);
last = addEnd(last, 8);
last = addFront(last, 2);
last = addAfter(last, 10, 2);
traverse(last);
deleteNode(&last, 8);
printf("\n");
traverse(last);
return 0;
}
// C++ code to perform circular linked list operations
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data) {
if (last != NULL) return last;
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to the new node
newNode->data = data;
// assign last to newNode
last = newNode;
// create link to iteself
last->next = last;
return last;
}
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the current first node in the newNode
newNode->next = last->next;
// make newNode as head
last->next = newNode;
return last;
}
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the head node to next of newNode
newNode->next = last->next;
// point the current last node to the newNode
last->next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
// check if the list is empty
if (last == NULL) return NULL;
struct Node *newNode, *p;
p = last->next;
do {
// if the item is found, place newNode after it
if (p->data == item) {
// allocate memory to the new node
newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// make the next of the current node as the next of newNode
newNode->next = p->next;
// put newNode to the next of p
p->next = newNode;
// if p is the last node, make newNode as the last node
if (p == last) last = newNode;
return last;
}
p = p->next;
} while (p != last->next);
cout << "\nThe given node is not present in the list" << endl;
return last;
}
// delete a node
void deleteNode(Node** last, int key) {
// if linked list is empty
if (*last == NULL) return;
// if the list contains only a single node
if ((*last)->data == key && (*last)->next == *last) {
free(*last);
*last = NULL;
return;
}
Node *temp = *last, *d;
// if last is to be deleted
if ((*last)->data == key) {
// find the node before the last node
while (temp->next != *last) temp = temp->next;
// point temp node to the next of last i.e. first node
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
// travel to the node to be deleted
while (temp->next != *last && temp->next->data != key) {
temp = temp->next;
}
// if node to be deleted was found
if (temp->next->data == key) {
d = temp->next;
temp->next = d->next;
free(d);
}
}
void traverse(struct Node* last) {
struct Node* p;
if (last == NULL) {
cout << "The list is empty" << endl;
return;
}
p = last->next;
do {
cout << p->data << " ";
p = p->next;
} while (p != last->next);
}
int main() {
struct Node* last = NULL;
last = addToEmpty(last, 6);
last = addEnd(last, 8);
last = addFront(last, 2);
last = addAfter(last, 10, 2);
traverse(last);
deleteNode(&last, 8);
cout << endl;
traverse(last);
return 0;
}
Circular Linked List Complexity
| Circular Linked List Complexity | Time Complexity | Space Complexity |
| Insertion Operation | O(1) or O(n) | O(1) |
| Deletion Operation | O(1) | O(1) |
1. Complexity of Insertion Operation
- The insertion operations that do not require traversal have the time complexity of
O(1). - And, an insertion that requires traversal has a time complexity of
O(n). - The space complexity is
O(1).
2. Complexity of Deletion Operation
- All deletion operations run with a time complexity of
O(1). - And, the space complexity is
O(1).
Why Circular Linked List?
- The NULL assignment is not required because a node always points to another node.
- The starting point can be set to any node.
- Traversal from the first node to the last node is quick.
Circular Linked List Applications
- It is used in multiplayer games to give a chance to each player to play the game.
- Multiple running applications can be placed in a circular linked list on an operating system. The os keeps on iterating over these applications.