Circular Linked Lists in Data Structures

06 Jun 2024
Intermediate
10.3K Views
Learn via Video Course & by Doing Hands-on Labs

Circular Linked Lists in Data Structures: An Overview

We know that in a `linked list` the last node pointer points to `NULL`. Whereas in a `circular linked list`, all nodes are connected to form a circle. In this DSA tutorial, we will see the circular linked list data structure in detail i.e. its features, working, implementation, etc.To further enhance your understanding and application of `linked list` concepts, consider enrolling in the best Data Structures and Algorithms Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

Before moving forward make sure you are up to date with the concepts of Linked Lists and Doubly Linked Lists

What is a Circular Linked List in Data Structures?

A
`circular linked list` is a variation of `linked lists` where the pointer of the last node instead of pointing to `NULL` points to the first or the `head` node. This connects the first node with the last node resulting in a circle of interconnected nodes. There is no `NULL` at the end. We can traverse a circular linked list until we reach the same node where we started as there is no beginning and no ending.

Representation of a Circular Linked List in Data Structures

You can see that a circular linked list is represented similarly to the
`Linked Lists`, with one additional care to connect the last node to the first Node.

If you are still not good at pointers, please refer to the Pointers in C++ tutorial and come back.

Types of Circular Linked Lists in Data Structures

There are two types of circular linked Lists in Data Structures:
1. Circular Singly Linked List: Here, each node has only one pointer i.e. `next` pointer. The `next` pointer of the last node of the list points to the first node of the list creating a circular structure. We can transverse only in one direction in a circular manner in this.

2. Doubly Circular Linked List: We saw there are two pointers, `prev` and `next` in the doubly linked lists in data structures. In this type also each node has two pointers, `prev`points to the previous node, and the `next` points to the next node. Here, in addition to the last node's `next` pointer storing the address of the first node, even the first node's `prev` pointer will store the address of the last node thus forming a circular structure.

Read More - Data Structure Interview Questions for Experienced

How to declare/create a Circular Linked List in Data Structures?

Syntax to Declare a Circular Linked List in Different Languages

``````
class Node:
def __init__(self,data):
self.data = data
self.next = None
``````
``````
public class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}
``````
``````
struct node
{
int data;
struct node *next;
};
``````

Example of Creating a Circular Linked List in Data Structures

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

# Initialize nodes
last = None
one = Node(10)
two = Node(20)
three = Node(30)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save address of third node in last
last = three
``````
``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

# Initialize nodes
last = None
one = Node(10)
two = Node(20)
three = Node(30)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save address of third node in last
last = three
``````
``````
#include

// Define the node structure
struct Node {
int data;
Node* next;
};

int main() {
// Initialize nodes
Node *last;
Node *one = nullptr;
Node *two = nullptr;
Node *three = nullptr;

// Allocate memory
one = new Node;
two = new Node;
three = new Node;

// Assign data values
one->data = 10;
two->data = 20;
three->data = 30;

// Connect nodes
one->next = two;
two->next = three;
three->next = one;

// Save address of third node in last
last = three;

// clean up memory
delete one;
delete two;
delete three;

return 0;
}
``````
In the above code,
`one`, `two`, and `three` are the nodes with data items `10`, `20`, and `30` respectively.
• For node `one`, the pointer `next` stores the address of `two`.
• For node `two`, the pointer `next` stores the address of `three`.
• For node `three`, the `next` points to node `one`.

Standard Operations on Circular Linked Lists in Data Structures

Insertion

Adding a node to a circular linked list is similar to adding a node to a linked list. The only extra work is to connect the last node with the first node. In the above given circular linked list, Insertion can be done in three ways:
1. Insertion at the beginning: Let us understand this with an illustration. Suppose we want to insert a node with the value 6 at the beginning of the given circular linked list. The following three steps to accomplish this operation:
1. Create a new node
• allocate memory for new Node
• assign the data to the new Node.

2. store the address of the current first node in the new Node (i.e. pointing the new Node to the current first node)
3. point the last node to new Node (i.e making new Node as head)

Example of Insertion at the beginning of a Circular Linked List

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):
self.last = None  # Pointer to the last Node of the Circular Linked List.

if self.last is None:

new_node = Node(data)
new_node.next = self.last.next
self.last.next = new_node

return self.last

if self.last is not None:
return self.last  # The list is not empty

new_node = Node(data)
self.last = new_node
self.last.next = self.last  # Linking back to itself in a circular manner
return self.last

if self.last is None:
print("The list is empty")
return

print(message + ": ", end="")
current_node = self.last.next
while True:
print(current_node.data, end=" ")
current_node = current_node.next
if current_node == self.last.next:
break
print()

# Creating a circular linked list with data 1, 2, and 3

# Adding a node with data 6 to the beginning

``````
``````
class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

Node last;

last = null;
}

if (last == null) {
}

Node newNode = new Node(data);
newNode.next = last.next;
last.next = newNode;

return last;
}

if (last != null) {
return last; // The list is not empty
}

Node newNode = new Node(data);
last = newNode;
last.next = last; // Linking back to itself in a circular manner
return last;
}

public void displayList(String message) {
if (last == null) {
System.out.println("The list is empty");
return;
}

System.out.print(message + ": ");
Node current = last.next;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != last.next);
System.out.println();
}

public static void main(String[] args) {

// Creating a circular linked list with data 1, 2, and 3

// Adding a node with data 6 to the beginning

}
}
``````
``````
#include <iostream>

class Node {
public:
int data;
Node* next;

Node(int data) : data(data), next(nullptr) {}
};

private:
Node* last;

public:

if (last == nullptr) {
}

Node* newNode = new Node(data);
newNode->next = last->next;
last->next = newNode;

return last;
}

if (last != nullptr) {
return last; // The list is not empty
}

Node* newNode = new Node(data);
last = newNode;
last->next = last; // Linking back to itself in a circular manner
return last;
}

void displayList(const std::string& message) {
if (last == nullptr) {
std::cout << "The list is empty" << std::endl;
return;
}

std::cout << message << ": ";
Node* current = last->next;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != last->next);
std::cout << std::endl;
}
};

int main() {

// Creating a circular linked list with data 1, 2, and 3

// Adding a node with data 6 to the beginning

return 0;
}
``````

Output

``````Before Insertion: 1 2 3
After Insertion: 6 1 2 3   ``````
2. Insertion at a specific position/in between the nodes: Suppose we want to insert a node with value 6 after the head node with value 1 in the given circular linked list. The following three steps to accomplish this operation:
1. travel to the node given i.e. node 1
2. point the `next` of new Node to the node next to node 1
3. store the address of the new Node at the next of node 1.

Example of Insertion in Between or at a Given Position in a Circular Linked List

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):
self.last = None

if self.last is None:
return None

temp, P = None, self.last.next
while True:
if P.data == item:
temp = Node(data)
temp.next = P.next
P.next = temp

if P == self.last:
self.last = temp
return self.last
P = P.next
if P == self.last.next:
print(item, "not present in the list.")
break

def display_list(self, message):
if self.last is None:
print("The list is empty")
return

print(message + ": ", end="")
current = self.last.next
while True:
print(current.data, end=" ")
current = current.next
if current == self.last.next:
break
print()

# Creating a circular linked list with data 1, 2, and 3

# Display the circular linked list before insertion

# Adding a node with data 6 after node with data 1

# Display the circular linked list after insertion
``````
``````
class Node {
int data;
Node next;

public Node(int val) {
data = val;
next = null;
}
}

Node last;

public Node addAfter(Node last, int data, int item) {
if (last == null)
return null;

Node temp, P;
P = last.next;
do {
if (P.data == item) {
temp = new Node(data);
temp.next = P.next;
P.next = temp;

if (P == last)
last = temp;
return last;
}
P = P.next;
} while (P != last.next);

System.out.println(item + " not present in the list.");
return last;
}

public void displayList(String message) {
if (last == null) {
System.out.println("The list is empty");
return;
}

System.out.print(message + ": ");
Node current = last.next;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != last.next);
System.out.println();
}

public static void main(String[] args) {

// Creating a circular linked list with data 1, 2, and 3

// Display the circular linked list before insertion

// Adding a node with data 6 after node with data 1

// Display the circular linked list after insertion
}
}
``````
``````
#include <iostream>

// Node structure for the Circular Linked List
struct Node {
int data;
Node* next;

// Constructor
Node(int val) : data(val), next(nullptr) {}
};

// Function to add a node after a specific node
Node* addAfter(Node* last, int data, int item) {
if (last == nullptr)
return nullptr;

Node* temp, *P;
P = last->next;
do {
if (P->data == item) {
temp = new Node(data);
temp->next = P->next;
P->next = temp;

if (P == last)
last = temp;
return last;
}
P = P->next;
} while (P != last->next);

std::cout << item << " not present in the list." << std::endl;
return last;
}

// Function to display the Circular Linked List
void displayList(Node* last, const std::string& message) {
if (last == nullptr) {
std::cout << "The list is empty" << std::endl;
return;
}

std::cout << message << ": ";
Node* current = last->next;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != last->next);
std::cout << std::endl;
}

int main() {
Node* last = nullptr;

// Creating a circular linked list with data 1, 2, and 3
last = new Node(1);
last->next = last;  // Pointing to itself initially

// Display the circular linked list before insertion
displayList(last, "Before Insertion");

// Adding a node with data 6 after node with data 1

// Display the circular linked list after insertion
displayList(last, "After Insertion");

// Clean up memory (optional in this example)
delete last;

return 0;
}
``````

Output

``````Before Insertion: 1 2 3
After Insertion: 1 6 2 3     ``````
3. Insertion at the end: Suppose we want to insert a node with value 6 after the last node with value 3 in the given circular linked list. The following three steps to accomplish this operation:
1. store the address of the `head` node to the next of new Node (making new Node the last node)
2. point the current last node to new Node
3. make new Node as the last node

Example of Insertion at the End of a Circular Linked List

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):
self.last = None

if self.last is None:
return None

new_node = Node(data)

new_node.next = self.last.next
self.last.next = new_node
self.last = new_node

return self.last

def display_list(self, message):
if self.last is None:
print("The list is empty")
return

print(message + ": ", end="")
current = self.last.next
while True:
print(current.data, end=" ")
current = current.next
if current == self.last.next:
break
print()

# Creating a circular linked list with data 1, 2, and 3

# Adding a node with data 6 at the end

``````
``````
class Node {
int data;
Node next;

public Node(int val) {
data = val;
next = null;
}
}

Node last;

public Node addEnd(Node last, int data) {
if (last == null)
return null;

Node newNode = new Node(data);

newNode.next = last.next;
last.next = newNode;
last = newNode;

return last;
}

public void displayList(String message) {
if (last == null) {
System.out.println("The list is empty");
return;
}

System.out.print(message + ": ");
Node current = last.next;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != last.next);
System.out.println();
}

public static void main(String[] args) {

// Creating a circular linked list with data 1, 2, and 3

// Adding a node with data 6 at the end

}
}
``````
``````
#include <iostream>

// Node structure for the Circular Linked List
struct Node {
int data;
Node* next;

// Constructor
Node(int val) : data(val), next(nullptr) {}
};

// Function to add a node at the end
Node* addEnd(Node* last, int data) {
if (last == nullptr)
return nullptr;

Node* newNode = new Node(data);

newNode->next = last->next;
last->next = newNode;
last = newNode;

return last;
}

// Function to display the Circular Linked List
void displayList(Node* last, const std::string& message) {
if (last == nullptr) {
std::cout << "The list is empty" << std::endl;
return;
}

std::cout << message << ": ";
Node* current = last->next;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != last->next);
std::cout << std::endl;
}

int main() {
Node* last = nullptr;

// Creating a circular linked list with data 1, 2, and 3
last = new Node(1);
last->next = last;  // Pointing to itself initially

displayList(last, "Before Insertion");

// Adding a node with data 6 at the end

displayList(last, "After Insertion");

// Clean up memory (optional in this example)
delete last;

return 0;
}
``````

Output

``````Before Insertion: 1 2 3
After Insertion: 1 2 3 6    ``````

Deletion

In the above given circular linked list, deletion can also be done in three ways:
1. If it's the only node: Follow the given two steps procedure
1. free the memory occupied by the node
2. store NULL in the last
2. If it's the last node: Follow the given four steps procedure
1. find the node before the last node (let it be `temp`)
2. store the address of the node next to the last node in `temp`
3. free the memory of the last
4. make `temp` the last node
3. If it's any other node: Follow the given four steps procedure
1. travel to the node to be deleted (here we are deleting node `two`)
2. Let the node before node `two` be `temp`
3. store the address of the node next to `two` in `temp`
4. free the memory of `two`
4. Example of Deletion Operation in a Circular Linked List

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):
self.last = None

def push(self, data):
ptr1 = Node(data)
ptr1.next = self.last

if self.last is not None:
temp = self.last
while temp.next != self.last:
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1

self.last = ptr1

def print_list(self):
temp = self.last
if self.last is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.last:
break
print()

def delete_node(self, key):
if self.last is None:
return

if self.last.data == key and self.last.next == self.last:
self.last = None
return

temp = self.last
d = None

if self.last.data == key:
while temp.next != self.last:
temp = temp.next

temp.next = self.last.next
self.last = temp.next
return

while temp.next != self.last and temp.next.data != key:
temp = temp.next

if temp.next.data == key:
d = temp.next
temp.next = d.next
else:
print("No such key found")

# Creating a circular linked list with data 1, 2, and 3

# Display the circular linked list before deletion
print("List Before Deletion:", end=" ")

# Deleting the first node

# Display the circular linked list after deletion
print("List after deletion of first node:", end=" ")

# Deleting a node in between (node with data 2)

# Display the circular linked list after deletion
print("List after deletion of an inner node:", end=" ")

# Deleting the last node

# Display the circular linked list after deletion
print("List after deletion of last node:", end=" ")
``````
``````
class Node {
int data;
Node next;

// Constructor
Node(int val) {
data = val;
next = null;
}
}

Node last;

// Function to insert a node at the beginning of
void push(int data) {
Node ptr1 = new Node(data);
ptr1.next = last;

if (last != null) {
Node temp = last;
while (temp.next != last)
temp = temp.next;
temp.next = ptr1;
} else {
ptr1.next = ptr1;
}

last = ptr1;
}

// Function to print nodes in a given
void printList() {
Node temp = last;
if (last != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != last);
}

System.out.println();
}

// Function to delete a given node from the list
void deleteNode(int key) {
if (last == null)
return;

if (last.data == key && last.next == last) {
last = null;
return;
}

Node temp = last;
Node d;

if (last.data == key) {
while (temp.next != last)
temp = temp.next;

temp.next = last.next;
last = temp.next;
return;
}

while (temp.next != last && temp.next.data != key) {
temp = temp.next;
}

if (temp.next.data == key) {
d = temp.next;
temp.next = d.next;
} else {
System.out.println("No such key found");
}
}

public static void main(String[] args) {

// Creating a circular linked list with data 1, 2, and 3

// Display the circular linked list before deletion
System.out.print("List Before Deletion: ");

// Deleting the first node

// Display the circular linked list after deletion
System.out.print("List after deletion of first node: ");

// Deleting a node in between (node with data 2)

// Display the circular linked list after deletion
System.out.print("List after deletion of an inner node: ");

// Deleting the last node

// Display the circular linked list after deletion
System.out.print("List after deletion of last node: ");
}
}
``````
``````
#include <iostream>

class Node {
public:
int data;
Node* next;

// Constructor
Node(int val) : data(val), next(nullptr) {}
};

void push(Node** head_ref, int data) {
Node* ptr1 = new Node(data);

temp = temp->next;
temp->next = ptr1;
} else {
ptr1->next = ptr1;
}

}

do {
std::cout << temp->data << " ";
temp = temp->next;
}

std::cout << std::endl;
}

void deleteNode(Node** head, int key) {
return;

return;
}

Node* d;

last = last->next;

return;
}

while (last->next != *head && last->next->data != key) {
last = last->next;
}

if (last->next->data == key) {
d = last->next;
last->next = d->next;
delete d;
} else {
std::cout << "No such key found" << std::endl;
}
}

int main() {

// Creating a circular linked list with data 1, 2, and 3

// Display the circular linked list before deletion
std::cout << "List Before Deletion: ";

// Deleting the first node

// Display the circular linked list after deletion
std::cout << "List after deletion of first node: ";

// Deleting a node in between (node with data 2)

// Display the circular linked list after deletion
std::cout << "List after deletion of an inner node: ";

//  Deleting the last node

// Display the circular linked list after deletion
std::cout << "List after deletion of last node: ";

return 0;
}
``````

Output

``````List Before Deletion: 1 2 3
List after deletion of first node: 2 3
List after deletion of an inner node: 1 3
List after deletion of last node: 1
``````

Traversal

We can access each element of the circular linked list starting from the
`head` node until we reach back to it.

Example of Traversing a Circular Linked List

``````
class Node:
def __init__(self, data):
self.data = data
self.next = None

# Function to traverse and print the Circular Linked List
def display_list(last):
if last is None:
print("The list is empty")
return

current = last.next
while True:
print(current.data, end=" ")
current = current.next
if current == last.next:
break
print()

# Initialize nodes
last = None
one = Node(1)
two = Node(2)
three = Node(3)

# Connect nodes
one.next = two
two.next = three
three.next = one

# Save the address of the third node in last
last = three

# Displaying the circular linked list
display_list(last)
``````
``````
class Node {
int data;
Node next;

// Constructor
public Node(int data) {
this.data = data;
this.next = null;
}
}

// Function to traverse and print the Circular Linked List
static void displayList(Node last) {
if (last == null) {
System.out.println("The list is empty");
return;
}

Node current = last.next;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != last.next);

System.out.println();
}

public static void main(String[] args) {
// Initialize nodes
Node last = null;
Node one = new Node(1);
Node two = new Node(2);
Node three = new Node(3);

// Connect nodes
one.next = two;
two.next = three;
three.next = one;

// Save the address of the third node in last
last = three;

// Displaying the circular linked list
displayList(last);
}
}
``````
``````
#include <iostream>

// Define the node structure
struct Node {
int data;
Node* next;
};

// Function to traverse and print the Circular Linked List
void displayList(Node* last) {
if (last == nullptr) {
std::cout << "The list is empty" << std::endl;
return;
}

Node* current = last->next;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != last->next);

std::cout << std::endl;
}

int main() {
// Initialize nodes
Node* last = nullptr;
Node* one = nullptr;
Node* two = nullptr;
Node* three = nullptr;

// Allocate memory
one = new Node;
two = new Node;
three = new 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 the address of the third node in last
last = three;

// Displaying the circular linked list
displayList(last);

// Clean up memory
delete one;
delete two;
delete three;

return 0;
}
``````

Output

``1 2 3     ``

Complexity Analysis of Circular Linked List Operations

 Operations Time Complexity Space Complexity Insertion `O(1) or O(N)` `O(1)` Deletion `O(1)` `O(1)` Traversal `O(N)` `O(1)`

1. This is used in multiplayer games to give each participant a chance to play.
2. In an operating system, a circular linked list can be used to organize many running applications.
3. In resource allocation difficulties, circular linked lists might be useful.
4. Circular linked lists are frequently used to build circular buffers.
5. They can also be used in simulation and gaming.

1. Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
2. Useful for the implementation of a queue. Unlike this implementation, we don’t need to maintain two-pointers for the `front` and `rear` if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.
3. Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4. Circular Doubly Linked Lists are used for the implementation of advanced data structures like the Fibonacci Heap.
5. Implementing a circular linked list can be relatively easy compared to other more complex data structures like trees or graphs.

1. Compared to singly linked lists, circular lists are more complex.
2. Reversing a circular list is more complicated than reversing a singly or doubly linked list.
3. The code can go into an infinite loop if it is not handled carefully.
4. It is harder to find the end of the list and control the loop.
5. Although circular linked lists can be efficient in certain applications, their performance can be slower than other data structures in certain cases, such as when the list needs to be sorted or searched.
Summary

So, here we saw every aspect of a circular linked list in data structures. You might have got at least some idea regarding circular linked lists and their applications. I know it's quite difficult and tricky to understand the whole topic in a single go. There are a lot of concepts and logic to be understood in this. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Best Data Structures And Algorithms Course.

FAQs

Q1. What is a Circular Linked List?

A circular linked list is a variation of linked lists where the pointer of the last node instead of pointing to NULL points to the first or the head node. This connects the first node with the last node resulting in a circle of interconnected nodes.

Q2. How many types of Circular Linked Lists are there?

There are two types of circular linked Lists in Data Structures.

Q3. Are circular linked lists easy to implement than trees or graphs?

Implementing a circular linked list can be relatively easy compared to other more complex data structures like trees or graphs.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 ASP.NET Core Certification Training Sep 15 SAT, SUN Filling Fast09:30AM to 11:30AM (IST) Advanced Full-Stack .NET Developer Certification Training Sep 15 SAT, SUN Filling Fast09:30AM to 11:30AM (IST) .NET Solution Architect Certification Training Sep 22 SAT, SUN Filling Fast07:00AM to 09:00AM (IST) Software Architecture and Design Training Sep 22 SAT, SUN Filling Fast07:00AM to 09:00AM (IST) Advanced Full-Stack .NET Developer Certification Training Sep 29 SAT, SUN Filling Fast08:30PM to 10:30PM (IST) ASP.NET Core Certification Training Sep 29 SAT, SUN Filling Fast08:30PM to 10:30PM (IST)

Can't find convenient schedule? Let us know