Linked lists are a fundamental data structure in computer science, offering flexibility and efficiency in managing collections of data. Among the variations of linked lists, the circular linked list stands out for its unique structure and applications. In this blog post, we’ll delve into the concept of circular linked lists, explore their implementation in Java, and discuss their advantages and use cases.

**Understanding Circular Linked Lists**

A circular linked list is similar to a regular linked list, with the key distinction being that the last node points back to the first node, forming a circle. Unlike linear linked lists, which have a NULL pointer at the end, circular linked lists have no NULL pointers within the list itself. This circular structure allows for traversal from any node to any other node within the list.

The basic components of a circular linked list include:

**Node:**A unit of data that contains both the data value and a reference (pointer) to the next node in the sequence.**Head:**A reference to the first node in the list. In a circular linked list, this node is connected to the last node, forming a circle.**Tail:**Although not always explicitly maintained, it refers to the last node in the list, which points back to the head.

**How to represent a circular singly linked list in java?**

A Circular Singly Linked List is similar to a singly linked list, with the difference that in a circular linked list, the last node points to the first node and not null. Instead of keeping track of the head, we keep track of the last node in the circular singly linked list.

For example:

In a Singly Linked List:

head –> 1 –> 8 –> 10 –> 16 –> null

In a Circular Singly Linked List:

```
last --> 16 --> 1 --> 8 --> 10 -->
^____________________________|
```

** last –> 16 –> 1 –> 8 –> 10 –> 16 // Please refer to the actual diagram for clarification.**

We can **insert nodes at both the end and beginning** with **constant time complexity**.

**How to implement a Circular Singly Linked List in a java ?**

```
public class CircularSinglyLinkedList {
private ListNode last; // Keep track of the last node of the circular linked list
private int length; // Hold the size of the circular singly list
private class ListNode {
private int data;
private ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public CircularSinglyLinkedList() {
last = null; // When we initialize the circular singly linked list, we know the last points to null and that time the list is empty
length = 0; // So the length is also 0;
}
// Gives the size of the circular singly linked list
public int length() {
return length;
}
// Check whether the circular list is empty or not
public boolean isEmpty() {
return length == 0;
}
public void createCircularLinkedList() {
ListNode first = new ListNode(1);
ListNode second = new ListNode(5);
ListNode third = new ListNode(10);
ListNode fourth = new ListNode(15);
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = first; // Here we make the list in circular nature by assigning the first node
last = fourth; // Last node points to the fourth node
}
public static void main(String[] args) {
CircularSinglyLinkedList csll = new CircularSinglyLinkedList();
csll.createCircularLinkedList();
}
}
```

This Java class `CircularSinglyLinkedList`

defines a circular singly linked list. It includes inner class `ListNode`

for representing each node in the list. The class provides methods to create a circular linked list, check its length, and check whether it is empty. The `main`

method demonstrates creating a circular linked list instance and initializing it.

**How to traverse and print a circular linked list in java ?**

```
last --> 16 --> 1 --> 8 --> 10 -->
^____________________________|
```

**Algorithm & Execution**

```
if (last == null) {
return;
}
ListNode first = last.next;
while (first != last) {
System.out.println(first.data + "");
first = first.next;
}
System.out.println(first.data + "");
```

The basic idea here is to find the first node using the last node, and then traverse the list from the first node to the last node. When the first node equals the last node, at that point, we are at the last node, but our while loop terminates, so we couldn’t print the last node’s data. That’s why we print it separately after the loop.

**Code**

```
public void display() {
if (last == null) {
return;
}
ListNode first = last.next;
while (first != last) {
System.out.println(first.data + "");
first = first.next;
}
System.out.println(first.data + "");
}
```

This method `display`

is designed to print the elements of the circular singly linked list. It starts from the `first`

node, which is the node after the `last`

node. Then, it traverses the list until it reaches the `last`

node, printing the data of each node. Finally, it prints the data of the `last`

node itself. If the list is empty (i.e., `last`

is null), the method simply returns without performing any operation.

**How to insert node at the beginning of a circular Singly Linked List in java ?**

```
ListNode temp = new ListNode(data);
if (last == null) {
last = temp;
} else {
temp.next = last.next;
}
last.next = temp;
length++;
```

- We create a temporary node (
`temp`

) which we will insert at the beginning of the circular list. - If the
`last`

node is null, it means our list is empty. In this case, we assign the`temp`

node to be the`last`

node. Both`last`

and`temp`

now point to the same new node we inserted. We update the`last.next`

pointer to point to`temp`

, forming the circular nature for the first node. - If the list is not empty (
`last`

is not null), we create a new`temp`

node with the given data, and it points to null initially. Then, we update`temp.next`

to point to`last.next`

, so it will be added at the beginning of the last node. Even now,`last`

and`temp.next`

will point to the last node. We need to update the`last`

node’s`next`

pointer to`temp`

so that the circular list nature remains intact. - Finally, we increment the length by 1 because every time we add a new node at the beginning of the last node.

**Code**

```
public void insertFirst(int data) {
ListNode temp = new ListNode(data);
if (last == null) {
last = temp;
} else {
temp.next = last.next;
}
last.next = temp;
length++;
}
```

This method `insertFirst`

is designed to insert a new node with the given data at the beginning of the circular singly linked list. If the list is empty (i.e., `last`

is null), the new node becomes both the first and last node. Otherwise, the new node is inserted after the last node, and its `next`

reference is updated to point to the node originally after the last node. Finally, the length of the list is incremented.

**How to insert node at the end of a circular singly linked list in Java?**

```
ListNode temp = new ListNode(data);
if (last == null) { // list is empty
last = temp;
last.next = last;
} else { // if list is non-empty
temp.next = last.next;
last.next = temp;
last = temp;
}
length++;
```

- First, we create a new temporary node (
`temp`

) with the given data value. - Initially, the circular list is empty, so
`last`

will point to null, i.e.,`last --> null`

. - When we insert a new node, we check whether we are inserting into an empty list or a non-empty list.
- If the list is empty, we point
`last`

to our temporary node, i.e.,`last = temp`

. - To create a circular structure, we need to make
`last.next`

point to`last`

itself, i.e.,`last.next = last`

. - After that, we increment the length by 1 as we successfully inserted a new node into the list.
- Now, let’s consider the scenario of a non-empty circular list. In this case, first, we assign
`last.next`

to the last node itself when there is only one node. If there is more than one node, then`last.next`

will point to the first node, and`temp.next`

will point to null. - Then, we attach the new temporary node to the end by assigning it as
`last.next`

. Previously, it pointed to itself because there was only one node. If there are more than one node, it will point to the`temp`

node because the last node becomes the first, and`temp`

will always become the last node to maintain the circular chain nature. - Finally,
`temp`

becomes our new`last`

because it is added at the end.

So, the basic logic is to add the temporary node at the end and always make that newly inserted node the last one.

**How to remove first node from a circular singly linked list in java ?**

```
if (isEmpty()) {
throw new NoSuchElementException();
}
ListNode temp = last.next;
if (last.next == last) {
last = null;
} else {
last.next = temp.next;
}
temp.next = null;
length--;
return temp;
```

- If the list is empty, meaning there are no elements to remove, we throw a
`NoSuchElementException`

. - We create a temporary node
`temp`

which will store the node to be removed, i.e., the first node (`last.next`

). - If
`last.next`

points to`last`

itself, it means there is only one node in the list. In this case, we remove the last node by assigning null to`last`

. - If
`last.next`

doesn’t point to`last`

, it means there are multiple nodes in the list. We remove the first node by updating`last.next`

to point to the second node (`temp.next`

). - We then set
`temp.next`

to null to detach`temp`

from the list. - We decrement the length of the list by 1 since we have successfully removed a node.
- Finally, we return the removed node
`temp`

.

So, the main logic is to remove the first node by adjusting pointers and then returning the removed node.

**Advantages of Circular Linked Lists**

Circular linked lists offer several advantages over their linear counterparts:

**Efficient Insertion and Deletion**: Insertion and deletion operations can be performed quickly, especially at the beginning or end of the list, as there’s no need to traverse the entire list.**Circular Traversal**: With a circular structure, traversal from any point in the list to any other point becomes straightforward.**Memory Efficiency**: Circular linked lists save memory by eliminating the need for a NULL pointer at the end of the list.

**Use Cases of Circular Linked Lists**

Circular linked lists find applications in various scenarios, including:

**Round-Robin Scheduling**: In operating systems, circular linked lists are used to implement round-robin scheduling algorithms, where tasks are executed in a circular order.**Music and Video Playlists**: Circular linked lists can be used to implement circular playlists, allowing seamless looping from the last item to the first.**Resource Management**: In resource allocation systems, circular linked lists can represent a pool of resources where allocation and deallocation operations are frequent.

**Conclusion**

Circular linked lists provide an elegant solution to certain problems by leveraging their circular structure and efficient operations. In Java, implementing a circular linked list involves managing node connections carefully to maintain the circular property. Understanding the strengths and applications of circular linked lists can aid in designing efficient algorithms and data structures for various computational tasks.