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.
Generally speaking, after we delete an element, we need to update the nextNode reference of the previous node to point to the nextNode reference of the node that has been deleted.
However, there are some special cases we need to think about:
- The circular linked list has only one element, and we want to remove the element – In this case, we just need to set the head node and tail node to null
- The element to delete is the head node – We must make head.nextNode as the new head
- The element to delete is the tail node – We need to make the previous node of the node we want to delete as the new tail
Let’s take a look at the implementation of deleting an element:
public void deleteNode(int valueToDelete) {
Node currentNode = head;
if (head == null) { // the list is empty
return;
}
do {
Node nextNode = currentNode.nextNode;
if (nextNode.value == valueToDelete) {
if (tail == head) { // the list has only one single element
head = null;
tail = null;
} else {
currentNode.nextNode = nextNode.nextNode;
if (head == nextNode) { //we're deleting the head
head = head.nextNode;
}
if (tail == nextNode) { //we're deleting the tail
tail = currentNode;
}
}
break;
}
currentNode = nextNode;
} while (currentNode != head);
}
Let’s now create some tests to verify that deletion works as expected for all the cases:
@Test
public void givenACircularLinkedList_WhenDeletingInOrderHeadMiddleTail_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));
}
@Test
public void givenACircularLinkedList_WhenDeletingInOrderTailMiddleHead_ThenListDoesNotContainThoseElements() {
CircularLinkedList cll = createCircularLinkedList();
assertTrue(cll.containsNode(46));
cll.deleteNode(46);
assertFalse(cll.containsNode(46));
assertTrue(cll.containsNode(1));
cll.deleteNode(1);
assertFalse(cll.containsNode(1));
assertTrue(cll.containsNode(13));
cll.deleteNode(13);
assertFalse(cll.containsNode(13));
}
@Test
public void givenACircularLinkedListWithOneNode_WhenDeletingElement_ThenListDoesNotContainTheElement() {
CircularLinkedList cll = new CircularLinkedList();
cll.addNode(1);
cll.deleteNode(1);
assertFalse(cll.containsNode(1));
}
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.