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.
![Circular Linked List Representation Circular Linked List Representation](/sites/tutorial2program/files/cirular-linked-list.png)
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.
![Circular Doubly Linked List Representation Circular Doubly Linked List Representation](/sites/tutorial2program/files/circular-doubly-linked-list.png)
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:
![Initial circular linked list Initial circular linked list](/sites/tutorial2program/files/cirular-linked-list-example.png)
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.
![Initial circular linked list Initial circular linked list](/sites/tutorial2program/files/cirular-linked-list-example.png)
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
![New node New node](/sites/tutorial2program/files/cll-newnode.png)
1. Insertion at the Beginning
- store the address of the current first node in the
newNode
(i.e. pointing thenewNode
to the current first node) - point the last node to
newNode
(i.e makingnewNode
as head)
![Insert at the beginning Insert at the beginning](/sites/tutorial2program/files/cll-insertion-beginning.png)
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
next
ofnewNode
to the node next top
- store the address of
newNode
atnext
ofp
![Insertion at a node Insertion at a node](/sites/tutorial2program/files/cll-insertion-after.png)
3. Insertion at the end
- store the address of the head node to
next
of newNode (makingnewNode
the last node) - point the current last node to
newNode
- make
newNode
as the last node
![Insert at the end Insert at the end](/sites/tutorial2program/files/cll-insertion-end.png)
Deletion on a Circular Linked List
Suppose we have a double-linked list with elements 1, 2, and 3.
![Initial circular linked list Initial circular linked list](/sites/tutorial2program/files/cirular-linked-list-example.png)
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
temp
as the last node
![Delete the last node Delete the last node](/sites/tutorial2program/files/cll-deletion-last.png)
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
![Delete a specific node Delete a specific node](/sites/tutorial2program/files/cll-deletion-after.png)
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.