**Get started with Spring 5 and Spring Boot 2, through the ***Learn Spring* course:

*Learn Spring*course:

**>> CHECK OUT THE COURSE**

Last modified: March 11, 2020

In this tutorial, we'll look at the implementation of a circular linked list in Java.

**A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes**. In other words, this variation of the linked list doesn't have a *null* element at the end.

With this simple change, we gain some benefits:

**Any node in the circular linked list can be a starting point**- Consequently, the whole list can be traversed starting from any node
- Since the last node of the circular linked list has the pointer to the first node, it's easy to perform enqueue and dequeue operations

All in all, **this is very useful in the implementation of the queue data structure.**

Performance-wise, it is the same as other linked list implementations except for one thing: **Traversing from the last node to the head node can be done in constant time**. With conventional linked lists, this is a linear operation.

Let's start by creating an auxiliary *Node* class that will store *int* values and a pointer to the next node*:*

```
class Node {
int value;
Node nextNode;
public Node(int value) {
this.value = value;
}
}
```

Now let's create the first and last nodes in the circular linked list, usually called the *head* and *tail:*

```
public class CircularLinkedList {
private Node head = null;
private Node tail = null;
// ....
}
```

In the next subsections we'll take a look at the most common operations we can perform on a circular linked list.

The first operation we're going to cover is the insertion of new nodes. While inserting a new element we'll need to handle two cases :

**The**, that is there are no elements already added. In this case, we'll make the new node we add as both the*head*node is null*head*and*tail*of the list since there is only one node**The**, that is to say, there are one or more elements already added to the list. In this case, the existing*head*node isn't null*tail*should point to the new node and the newly added node will become the*tail*

In both of the above cases, the *nextNode* for *tail* will point to *head*

Let's create an *addNode* method that takes the *value* to be inserted as a parameter:

```
public void addNode(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
tail.nextNode = head;
}
```

Now we can add a few numbers to our circular linked list:

```
private CircularLinkedList createCircularLinkedList() {
CircularLinkedList cll = new CircularLinkedList();
cll.addNode(13);
cll.addNode(7);
cll.addNode(24);
cll.addNode(1);
cll.addNode(8);
cll.addNode(37);
cll.addNode(46);
return cll;
}
```

The next operation we'll look at is searching to determine if an element is present in the list.

For this, **we'll fix a node in the list (usually the head) as the currentNode and traverse through the entire list using the nextNode of this node**, until we find the required element.

Let's add a new method *containsNode* that takes the *searchValue* as a parameter:

```
public boolean containsNode(int searchValue) {
Node currentNode = head;
if (head == null) {
return false;
} else {
do {
if (currentNode.value == searchValue) {
return true;
}
currentNode = currentNode.nextNode;
} while (currentNode != head);
return false;
}
}
```

Now, let's add a couple of tests to verify that the above-created list contains the elements we added and no new ones:

```
@Test
public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() {
CircularLinkedList cll = createCircularLinkedList();
assertTrue(cll.containsNode(8));
assertTrue(cll.containsNode(37));
}
@Test
public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() {
CircularLinkedList cll = createCircularLinkedList();
assertFalse(cll.containsNode(11));
}
```

Next, we'll look at the delete operation. Similar to insertion we have a couple of cases (excluding the case where the list itself is empty) that we need to look at.

**Element to delete is the**. In this case, we need to update the*head*itself*head*as the next node of the current head*,*and the next node of the*tail*as the new head**Element to delete is any element other than the**. In this case, we just need to update the next node of the previous node as the next node of the node that needs to be deleted*head*

We'll now add a new method *deleteNode* that takes the *valueToDelete* as a parameter:

```
public void deleteNode(int valueToDelete) {
Node currentNode = head;
if (head != null) {
if (currentNode.value == valueToDelete) {
head = head.nextNode;
tail.nextNode = head;
} else {
do {
Node nextNode = currentNode.nextNode;
if (nextNode.value == valueToDelete) {
currentNode.nextNode = nextNode.nextNode;
break;
}
currentNode = currentNode.nextNode;
} while (currentNode != head);
}
}
}
```

Let's now add a simple test to verify that deletion works as expected for all the cases:

```
@Test
public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() {
CircularLinkedList cll = createCircularLinkedList();
assertTrue(cll.containsNode(13));
cll.deleteNode(13);
assertFalse(cll.containsNode(13));
assertTrue(cll.containsNode(1));
cll.deleteNode(1);
assertFalse(cll.containsNode(1));
assertTrue(cll.containsNode(46));
cll.deleteNode(46);
assertFalse(cll.containsNode(46));
}
```

**We're going to take a look at the traversal of our circular linked list in this final section**. Similar to the search and delete operations, for traversal we fix the *currentNode* as *head* and traverse through the entire list using the *nextNode* of this node.

Let's add a new method *traverseList* that prints the elements that are added to the list:

```
public void traverseList() {
Node currentNode = head;
if (head != null) {
do {
LOGGER.info(currentNode.value + " ");
currentNode = currentNode.nextNode;
} while (currentNode != head);
}
}
```

As we can see, in the above example, during the traversal, we simply print the value of each of the nodes, until we get back to the head node.

In this tutorial, we've seen how to implement a circular linked list in Java and explored some of the most common operations.

First, we learned what exactly a circular linked list is including some of the most common features and differences with a conventional linked list. Then, we saw how to insert, search, delete and traverse items in our circular linked list implementation.

As usual, all the examples used in this article are available over on GitHub.