In this article, we are going to understand what a circular singly linked list is. We will also see insertions, deletions, and searches in a circular singly linked list. We will also implement a circular singly linked list in Java.

## What is a Circular Singly Linked List?

A Circular Singly Linked List (DLL) is a slight variation of a singly or doubly linked list. In this variation, the last node of the list points to the first node of the list and therefore forms a circle. To know when the list has reached to where it will repeat the elements, we can either have a “last” pointer which will point to the last node or by hitting the same node again. None of the nodes will point to `NULL` in this case. We can create a circular singly as well as a circular doubly linked list. There isn’t much difference apart from a fact that circular doubly linked list will have a “`previous`” pointer as well.

• The major advantage is that we can start from any node and still we can traverse the entire list.
• We can maintain one pointer “`last`” and get the first (head) node using the next pointer of the last node.
• We no longer need a `NULL` assignment unless the list itself is empty.
• It is very useful in `CPU` round robin scheduling.

• The biggest disadvantage of this list is that if it is not programmed correctly, you will end up in an infinite loop.
• Implementing a circular linked list is complex compared to singly linked list.
• Reversing a circular linked list is complex, it is complex compared to singly linked list.

## 3. Circular Singly Linked List Representation

A Circular Singly linked list is made of a sequence of nodes. Each node contains a value (data), a pointer to the next node, and the last node’s next points to the first node of the list.

As per the above illustration, the following are the important points to be considered.

• The Head (optional) pointer points to the first node of the list.
• The Tail (Last) pointer points to the last node of the list.
• Each node has a data field, and a pointer to the next node.
• The last node’s next pointer points to the first node.

## 4. Basic Operations

We will go through the major operations of a linked list, and they are insertion, deletion, display, search, and size.

#### 4.1. Insertion

In a circular singly linked list, we can insert a node in three different ways.

Insert the new node as the first node:

1. The new node’s next will point to the first node or the last node’s next.
2. The last node’s next will point to the new node.
``````public void insertAtFirst(int data) {
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
} else {
//Store data into temporary node
//New node will point to temp as next node
newNode.next = temp;
//New node will be the head node
}
}``````

At a Given Index:

If we wish to insert a node at any index, we will first check if the index is less than the size of the list, we will then first traverse till the index. Next, we will do the following things:

1. The new node next will point to the previous node’s next.
2. The previous node’s next (`index-1`) will point to the new node.

As you can see below, we had a linked list `0->1->3->0` and we want to insert node `2` at index `2`, so we will change the pointers as per the above steps and the linked list will become `0->1->2->3->0`.

``````public void insertAtIndex(int data, int position) {
Node temp, newNode;
int i, count;
newNode = new Node();
count = size();
if (temp == null || size() < position)
System.out.println("Index is greater than size of the list");
else {
newNode.data = data;
for (i = 1; i < position - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
}``````

At the End of the Linked List:

When we want to insert a node at the end of a circular linked list, we will traverse the circular linked list till the current’s next points to the first node (using head or last pointer). The current is the last node of the list. At this stage we will do the following 3 things:

1. The new node next will point to the current last node’s next.
2. The current node’s next will point to the new node.
3. The last pointer will point to the new node.

As you can see below, we had a linked list 1`->2->3->1 `and we want to insert node 4 at last, so we will change the pointers as per the above steps and the linked list will become `1->2->3->4->1`.

``````public void insertAtLast(int data) {
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
} else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}``````

#### 4.2. Deletion

Like insertion, we can delete a node from a circular linked list in 3 ways: To delete a node from the circular linked list, we need to do the following steps.

Delete the First Node

To delete the first node from the circular linked list, point the last node’s next to the last node’s next’s next. You can see the illustration in the following diagram.

``````public void deleteFirst() {
return;
} else {
}
//If the list contains only one element
//then it will remove it and both head and tail will point to null
else {
}
}
}``````

Delete at an index:

To delete an element at the index from the circular linked list, we first check if the index is less than the size of the list. We then traverse till the index (using the last pointer and by keeping track of the current and previous nodes) and change the previous node’s next to the current node’s next. You can see the illustration in the following diagram.

``````public void deleteNode(int data) {
System.out.println("List is empty");
// Find the required node
Node previousNode = new Node();
while (currentNode.data != data) {
System.out.println("Given node with data " + data + " is not found in the circular linked list.");
break;
}
previousNode = currentNode;
currentNode = currentNode.next;
}

// Check if node is only node
}

// If more than one node, check if
// it is first node
previousNode = previousNode.next;
}
}

// check if node is last node
else if (currentNode.next == head) {
} else {
previousNode.next = currentNode.next;
}
}``````

Delete the last element

To delete the last element from the circular linked list, traverse till the second last element and change the previous node’s next to the last node’s next (effectively, the second last element will now point to the first node of the list). You can see the illustration in the following diagram.

``````public void deleteLast() {
return;
} else {
//Loop will iterate till the second last element as current.next is pointing to tail
while (current.next != tail) {
current = current.next;
}
//Second last element will be new tail
tail = current;
//Tail will point to head as it is a circular linked list
}
//If the list contains only one element
//Then it will remove it and both head and tail will point to null
else {
}
}
}``````

#### 4.3. Display

To display the nodes of the circular linked list, we will need to start from the head and print the node’s data. We will continue doing this until the current node’s next is not equal to the first node, and that means the end of the list.

``````public void display() {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("\n");
}``````

#### 4.4. Search

To search for a node of the linked list, we will need to start from the head and check if the current node’s data is equal to the data, or else we will move to the next node in the list. We will continue to go to the next node until the current node’s next is not equal to the first node and in that case, the data is not present in our linked list, or better, we don’t have a node that has the data.

``````public void searchNode(int data) {
System.out.println("Searching for data:" + data);
//Node current will point to head
int i = 1;
boolean flag = false;
//Checks whether list is empty
System.out.println("List is empty");
} else {
do {
//Compares element to be found with each node present in the list
if (current.data == data) {
flag = true;
break;
}
current = current.next;
i++;
if (flag)
System.out.println("Element is present in the list at the position : " + i);
else
System.out.println("Element is not present in the list");
}
}``````

#### 4.5. Size

To calculate the size of a doubly linked list, we will set a counter at `0` and keep incremented by `1` once we visit a node. We will start with the head and continue to go to the next node until the current node’s next is not equal to the first node. As said, we will increment the counter for each node we traverse. At the end, we will have the size of the list in the counter variable.You can see the code for this below. In our example, we are updating the size variable at every insert and delete, so we can directly use that variable.

``````public int size() {
int size = 0;
temp = temp.next;
size++;
}
size++;
}
return size;
}``````

## 6. Java Example

We have seen the all use cases for circular singly linked list. Let’s see how to implement a circular singly linked list in Java.

``````package DS.list;

static class Node {
int data;
Node next;
Node() {}
Node(int data) {
this.data = data;
}
}

private Node tail;

// constructor
this.tail = null;
}

public boolean isEmpty() {
}

/**
* insertAtFirst
* @param data
*/
public void insertAtFirst(int data) {
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
} else {
//Store data into temporary node
//New node will point to temp as next node
newNode.next = temp;
//New node will be the head node
}
}

/**
* insertAtLast
* @param data
*/
public void insertAtLast(int data) {
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
} else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}

/**
*
* @param data
* @param position
*/
public void insertAtIndex(int data, int position) {
Node temp, newNode;
int i, count;
newNode = new Node();
count = size();
if (temp == null || size() < position)
System.out.println("Index is greater than size of the list");
else {
newNode.data = data;
for (i = 1; i < position - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
}

/**
* delete the first node.
*/
public void deleteFirst() {
return;
} else {
}
//If the list contains only one element
//then it will remove it and both head and tail will point to null
else {
}
}
}

/**
*
*/
public void deleteLast() {
return;
} else {
//Loop will iterate till the second last element as current.next is pointing to tail
while (current.next != tail) {
current = current.next;
}
//Second last element will be new tail
tail = current;
//Tail will point to head as it is a circular linked list
}
//If the list contains only one element
//Then it will remove it and both head and tail will point to null
else {
}
}
}

/**
*
* @param data
* @return
*/
public void deleteNode(int data) {
System.out.println("List is empty");
// Find the required node
Node previousNode = new Node();
while (currentNode.data != data) {
System.out.println("Given node with data " + data + " is not found in the circular linked list.");
break;
}
previousNode = currentNode;
currentNode = currentNode.next;
}

// Check if node is only node
}

// If more than one node, check if
// it is first node
previousNode = previousNode.next;
}
}

// check if node is last node
else if (currentNode.next == head) {
} else {
previousNode.next = currentNode.next;
}
}

/**
* Display forward
*/
public void display() {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("\n");
}

public int size() {
int size = 0;
temp = temp.next;
size++;
}
size++;
}
return size;
}

/**
* Search the given node in doubly linked list
* @param data
*/
public void searchNode(int data) {
System.out.println("Searching for data:" + data);
//Node current will point to head
int i = 1;
boolean flag = false;
//Checks whether list is empty
System.out.println("List is empty");
} else {
do {
//Compares element to be found with each node present in the list
if (current.data == data) {
flag = true;
break;
}
current = current.next;
i++;
if (flag)
System.out.println("Element is present in the list at the position : " + i);
else
System.out.println("Element is not present in the list");
}
}

public static void main(String[] args) {
list.insertAtFirst(1);
list.display();
System.out.println("size :" + list.size());
list.insertAtFirst(2);
list.display();
System.out.println("size :" + list.size());
list.insertAtLast(3);
list.display();
System.out.println("size :" + list.size());
list.display();
list.insertAtLast(4);
System.out.println("size :" + list.size());
list.display();
list.insertAtIndex(5, 3);
System.out.println("size :" + list.size());
list.display();

list.deleteNode(8);
System.out.println("size :" + list.size());
list.display();

list.deleteNode(2);
System.out.println("Node with data 2 has been deleted");
System.out.println("size :" + list.size());
list.display();

list.searchNode(5);
list.display();
}
}``````

The Output: