## 1. Introduction

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

## 2. Circular Linked List

**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.

## 3. Implementation in Java

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.

### 3.1. Inserting Elements

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 ***head* node is null, that is there are no elements already added. In this case, we'll make the new node we add as both the *head* and *tail* of the list since there is only one node
**The ***head* node isn't null, that is to say, there are one or more elements already added to the list. In this case, the existing *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;
}

### 3.2. Finding an Element

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));
}

### 3.3. Deleting an Element

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 ***head* itself. In this case, we need to update the *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 ***head*. 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

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));
}

### 3.4. Traversing the List

**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.

## 4. Conclusion

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.

Java bottom
### The early-bird price of the new *Learn Spring Security OAuth* course packages will **increase by $50 on Wednesday**:

**>> CHECK OUT THE COURSE**
## Leave a Reply