• Articles
• Tutorials
• Interview Questions

# Introduction to Circular Linked List

A circular linked list is a way of organizing and storing data where the last node points to the first, forming a closed circle. It is effective for tasks such as managing memory in various applications because it can execute operations like insertion and deletion. Circular linked lists optimize code by allowing constant-time insertions and deletions (O(1)) and enabling efficient iteration without handling null references. They are particularly useful in applications like real-time systems, gaming, and networking, where cyclic data processing is required. In this blog, we will learn about circular linked lists, their types, operations performed, and applications.

Explore the world of C programming with this captivating YouTube video—your gateway to a comprehensive learning experience!

## What is a Circular Linked List?

The circular linked list is like a regular linked list where the last node is connected back to the first node, forming a circle. Imagine a chain where the last link connects to the first one, creating a continuous loop. This structure allows you to go through the elements of data from any point in the list.

The above image represents a circular linked list with 4 nodes. In this image, the first node comprises two components: one holding the data and the other containing the address (pointer/ptr)  pointing towards the next node. The first node in a list is commonly referred to as the “Head.” If the first node is deleted, the second node (now the first) takes on the role of the “Head.”

Nodes in the list are interconnected; for example, node 1 is linked to node 2, node 2 to node 3, and so forth. The final node (node 4 in this case) is connected back to the initial node, creating a circular linked list.

Syntax:

struct Node {

int data;

struct Node *next;

};

If you want to know more about C programming, you can go through this C Programming Certification Course!

## Types of Circular Linked Lists

The circular linked list consists of two types:

A circular singly linked list is a variation of a singly linked list where the last node of the list points back to the first node, forming a circular structure. It has two components:

• Data: It holds the actual data or value that the node is storing.
• Next Pointer: It points to the next node in the sequence.

In the above image, the first node is pointing towards the second node, the second node is pointing towards the third node, and the last node is pointing back to the first node, hence forming a circle. Once we move to the next node, we cannot go back to the previous node.

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

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

}

public void append(int data) {
Node newNode = new Node(data);
} else {
current = current.next;
}
current.next = newNode;
}
}

public void printList() {
System.out.println("List is empty.");
return;
}
do {
System.out.print(current.data + " -> ");
current = current.next;
}

public static void main(String[] args) {
cSLL.append(1);
cSLL.append(2);
cSLL.append(3);
cSLL.printList();
}
}
```

A circular doubly linked list is a list where each node has a reference to both the next and the previous nodes. In addition to being doubly linked, the pointer of the last node points to the first node, and the pointer of the first node points to the last node, forming a circular structure.

It has three components:

• Data: Holds the actual data or value that the node is storing
• Next Pointer: Points to the next node in the sequence
• Previous Pointer: Points to the previous node in the sequence

In the above image, the first node is pointing to the next and also pointing backward to the last node. Similarly, the second node points toward the third node and also points backward to the previous node. This shows that each node is connected to both the next and previous node.

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

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

}

public void append(int data) {
Node newNode = new Node(data);
} else {
tail.next = newNode;
newNode.prev = tail;
}
}

public void printList() {
System.out.println("List is empty.");
return;
}
do {
System.out.print(current.data + " <-> ");
current = current.next;
}

public static void main(String[] args) {
cDLL.append(1);
cDLL.append(2);
cDLL.append(3);
cDLL.printList();
}
}
```

## Operations on Circular Linked List

The main three operations that one can perform on a circular linked list are as follows:

### Traversal

To traverse a circular linked list, we need to follow these steps:

Initialize a pointer: Start with the initial node (head) of the circular linked list. Loop until the desired condition is met: Continue traversing through the list until we reach the end or until we meet a certain condition (e.g., reaching a specific node).

Update the pointer: After visiting a node, update the pointer to move to the next node in the list. Since it’s a circular list, ensure the pointer wraps around correctly to start from the beginning again after reaching the end.

Here’s a simple example in Python to demonstrate how to traverse a circular linked list:

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

def __init__(self):

# Method to add nodes at the end of the list
def append(self, data):
else:
new_node = Node(data)
cur = cur.next
cur.next = new_node

# Method to print the list
def display(self):
elements = []
while True:
elements.append(cur_node.data)
cur_node = cur_node.next
break
return elements

# Example usage
cll.append('A')
cll.append('B')
cll.append('C')

```

### Insertion

In a circular linked list, insertion involves adding a new node to the existing list. The process includes

• creating a new node
• setting its data
• adjusting the pointers to put the new node into the circular structure

#### At the Beginning

Here we will add the elements at the start of the list.

In the above image, our list already consists of two elements, i.e., 7 and 9, and we are inserting 2 at the beginning.

As a result, we have successfully inserted 2 at the beginning of the list, as shown in the figure above.

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

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

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void insertAtStart(int data) {
Node newNode = new Node(data);
tail = newNode;
} else {
tail = newNode;
}
}
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
clist.insertAtStart(0); // Inserts 0 at the start
System.out.println(clist); // Expected output: 0 -> 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
}
}
```

#### In the Middle

Here we will add the elements in the middle of the list.

In the above image, we have elements 1 and 8, and we want to insert element 3 between these two nodes.

As a result, element 3 is successfully inserted into the circular linked list. Now the first node, i.e., element 1, will point towards the second node, i.e., element 3.

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

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

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void insertInMiddle(int data) {
} else {
Node newNode = new Node(data);
do {
fastPtr = fastPtr.next;
newNode.next = fastPtr.next;
fastPtr.next = newNode;
tail = newNode;
}
}
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
clist.insertInMiddle(6); // Inserts 6 in the middle
System.out.println(clist); // Expected output: 5 -> 4 -> 6 -> 3 -> 2 -> 1 -> HEAD
}
}
```

#### At the End

Here we will add the elements at the end of the list.

In the above image, we have three elements in the list and want to add the fourth element.

As a result, we have successfully inserted the fourth element at the end of the list. Now the new node will be pointing toward the 1st node.

Get ready for high-paying programming jobs with these Top C & Data Structure Interview Questions and Answers!

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

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

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void insertAtEnd(int data) {
Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
clist.insertAtEnd(6); // Inserts 6 at the end
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> 6 -> HEAD
}
}
```

### Deletion

In a circular linked list, deletion refers to the process of removing a specific node from the list. The deletion process varies based on the position of the node to be removed within the list. Three main scenarios are considered:

• deleting a node from the middle of the list
• deleting the last node

#### At the Beginning

Here we will remove the elements at the start of the list.

As we have five elements in the original list, we want to delete the first element from the list.

As a result, the first element from the list has been deleted successfully.

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

public Node(int data) {
this.data = data;
this.next = null; // For simplicity, assuming singly linked list
}
}

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void deleteFromBeginning() {
if (head == null) return; // List is empty

// Find the new head node
do {
current = current.next;

tail.next = head; // Ensure the list remains circular

// Delete the old head node
current.next = null;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {

System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD

// Deleting from the beginning
clist.deleteFromBeginning();
System.out.println(clist); // Expected output: 4 -> 3 -> 2 -> 1 -> HEAD

}
}
```

#### In the Middle

Here we will remove the elements in between the list.

We have five elements in the list: 1, 2, 3, 4, and 5. We want deletion in the middle of the list, i.e., we want to delete the middle element “3”.

As a result, “3” has been removed from the circular linked list.

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

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

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void deleteMiddleElement() {
boolean found = false;
do {
fastPtr = fastPtr.next;
found = true;
}
fastPtr = fastPtr.next;
if (!found) {
slowPtr = slowPtr.next;
}
slowPtr.next = slowPtr.next.next;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
clist.deleteMiddleElement(); // Deletes the middle element
System.out.println(clist); // Expected output: 5 -> 3 -> 2 -> 1 -> HEAD
}
}

```

#### At the End

Here we will remove the elements at the end of the list.

Here, we have again five elements in the list: 1, 2, 3, 4, and 5. We want to delete the last element from the circular linked list.

As a result, we have successfully deleted the last node in the circular linked list.

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

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

private Node tail;

Node newNode = new Node(data);
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}

public void removeLastElement() {
tail = null;
} else {
do {
current = current.next;
tail = current;
tail.next = head.prev; // Set the new tail's next to the previous head
}
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
do {
sb.append(current.data).append(" -> ");
current = current.next;
return sb.toString();
}

public static void main(String[] args) {
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> HEAD
clist.removeLastElement(); // Removes the last element
System.out.println(clist); // Expected output: 5 -> 4 -> 3 -> 2 -> HEAD
}
}
```

Circular linked lists, both singly and doubly, have their own set of advantages and disadvantages. Here’s an overview:

• Insertion and deletion of nodes at the beginning and end of the list can be done more efficiently compared to linear linked lists.
• No traversal is needed to update the last node’s next pointer during insertion or deletion at the end.
• Due to the circular structure, it’s easy to traverse the entire list, starting from any node. This can be useful in certain applications where circular traversal is required.
• In certain scenarios, circular linked lists can be more memory-efficient compared to linear linked lists due to their ability to reuse the last node’s “next” pointer to connect back to the first node.

• If not implemented or managed properly, circular linked lists can lead to infinite loops during traversal.
• The circular structure adds complexity to the implementation and operations of the linked list.
• In a singly circular linked list, accessing the previous node while traversing requires additional traversal from the head, which can be less efficient compared to doubly linked lists.
• Each node in the circular linked list requires extra space for the next (and possibly previous in the case of doubly linked lists) pointer. This can increase memory overhead, especially for large lists.

## Applications of Circular Linked List

Circular linked lists find applications in various scenarios due to their unique properties. Some of the common applications include:

1. Round-Robin Scheduling: Circular linked lists are used in scheduling algorithms, such as Round-Robin in operating systems. Each node represents a process, and the circular structure ensures that each process gets an equal share of the CPU time.
1. Music Playlist: Circular linked lists can be used to implement playlists in music players. The last song’s next pointer points back to the first song, creating a continuous loop of songs to play.
1. Multiplayer Games: In multiplayer games, a circular linked list can represent the order of turns or actions among players. After the last player takes their turn, the next turn goes back to the first player.
1. File System Management: In file systems, circular linked lists can be utilized for managing free disk blocks. The last block’s next pointer can return to the first free block.
1. Simulation Systems: In simulation systems, circular linked lists are used to model scenarios where entities cyclically interact with each other. Each node in the list represents an entity, and the simulation progresses in a circular sequence. This setup allows for continuous interactions among entities, creating a dynamic and repetitive simulation environment.

## Concluding Thoughts

In conclusion, circular linked lists offer a versatile data structure with applications in memory management, task scheduling, and efficient navigation. Their ability to form a closed loop facilitates constant-time insertions and deletions, making them suitable for dynamic scenarios. The future scope involves exploring optimizations for specific use cases, enhancing algorithms for circular list manipulation, and integrating advanced features into diverse domains, thereby contributing to the evolution of efficient and scalable data structures in computer science.

Do you still have doubts about C programming? Clear your doubts and queries with our experts in our C Programming Community!

## FAQs

### Where are circular linked lists used in real-world applications?

Circular linked lists are used in scenarios such as round-robin scheduling, music playlists, multiplayer game turn management, resource allocation, job scheduling in real-time systems, file system management, simulation systems, buffer management, and undo/redo functionality.

### How do you insert a node into a circular linked list?

To insert a node into a circular linked list, you can traverse to the last node, create a new node, and update the last node’s next pointer to point to the new node. Ensure that the new node’s next pointer is set to the first node to maintain the circular structure.

### How do you delete a node from a circular linked list?

To delete a node from a circular linked list, you need to update the next pointer of the preceding node to skip the node to be deleted. Ensure proper handling of the last node’s next pointer to maintain the circular structure.

### How do you traverse a circular linked list?

Traversal involves starting from any node and moving to the next node until you reach the starting node again. A do-while loop is commonly used for traversal to ensure that the loop is executed at least once.

Yes, a circular linked list can be doubly linked, meaning each node has both next and previous pointers. This allows for more efficient traversal in both forward and backward directions.

Course Schedule

Name Date Details
Python Course 07 Sep 2024(Sat-Sun) Weekend Batch
View Details
Python Course 14 Sep 2024(Sat-Sun) Weekend Batch
View Details
Python Course 21 Sep 2024(Sat-Sun) Weekend Batch
View Details