Circular Linked List Implementation In Java

In this article, we will discuss how to implement the circular linked list in Java and its advantages. We will also see how to perform different common operations such as Insertion, Deletion, and Search in a circular linked list.

You can also follow the previous articles to know the implementation of the Singly linked list and Doubly linked list in Java.

What is Circular Linked List

A Circular linked list is yet another variation of a linked list in which the tail node points to the head node of the list and hence a circular linked list does not have an end unlike singly linked list in which the tail node points to NULL.

In a circular linked list, each node has a successor. Below is a sample structure of circular linked list.

Advantages of Circular Linked List

• There are many computer science problems which are circular by nature such as the Round-robin scheduling algorithm. This a best use case to use a circular linked list.
• Similarly, the complete list can be traversed starting with any node.
• The queue data structure implementation in Java uses a circular linked list as its internal implementation.

Circular Linked List Node

Let us define our node class implementation of the circular linked list in Java. The node class implementation is exactly the same as single linked list node class implementation.

public class Node {

    private int data;
    private Node nextNode;

//setters and getters 

Circular Linked List Common Operations

The implementation contains two pointers as head and tail and the tail pointers internally point to the head node. Below is our implementation class.

public class CircularLinkedList {

    private Node head;
    private Node tail;

    public void insert(int data){
        
    }

    public boolean search(int data){
        
    }

    public void delete(int data){
       
    }

    public void traverse(){
        
    }

    public static void main(String[] args) {
       
    }

}

Insert Operation

The insertion can be at head or tail. If the node to be inserted is the first node i.e. head is null then we make this node as head and tail node and it internally points to itself fulfilling the condition of a circular linked list.

Else, the new node is inserted just after the tail node and before the head node and this new node will point to the head node.

public void insert(int data){
        Node newNode = new Node(data);
        if (head == null){
            head = newNode;
        }else {
            tail.setNextNode(newNode);
        }
        tail = newNode;
        tail.setNextNode(head);
    }

The time complexity would be O(1) and the space complexity would be also O(1) for creating one temporary variable.

Search Operation

The search operation iterates over all the nodes of the linked list and performs the comparison untill the head node is encountered meaning the search operation could not find the item.

public boolean search(int data){
        if (head == null){
            return false;
        }else {
            Node currentNode = head;
            while (currentNode.getNextNode() != head){
                if (currentNode.getData() == data){
                    return true;
                }
                currentNode = currentNode.getNextNode();
            }
        }
        return false;
    }

The time complexity would be O(n).

Delete Operation

Delete operation can be either deleting the head node or deleting any other nodes.

The head node can be deleted by marking the next node of previous head node as current head node and replacing the next node of tail node with the current head node.

Similarly, deletion of any other node can be achieved by replacing the next node of previous node of the node to be deleted with the next node of the node to be deleted.

public void delete(int data){
        Node currentNode = head;
        if (head != null){
            if (currentNode.getData() == data){
                head = currentNode.getNextNode();
                tail.setNextNode(head);
            }else {
                while(currentNode.getNextNode() != head){
                    if (currentNode.getNextNode().getData() == data){
                        currentNode.setNextNode(currentNode.getNextNode().getNextNode());
                        break;
                    }
                    currentNode = currentNode.getNextNode();
                }
            }
        }
    }

Traversal

The traversal operation can be performed by simply iterating each node of the list starting from the head node untill we encounter the head node again.

public void traverse(){
        if (head != null){
            Node currentNode = head;
            while (currentNode.getNextNode() != head){
                System.out.print(currentNode.getData() + " ");
                currentNode = currentNode.getNextNode();
            }
        }
        System.out.print(tail.getData());
    }

Circular Linked List Runner

Below is the runner class to verify our above implementations.

public static void main(String[] args) {
        CircularLinkedList circularLinkedList = new CircularLinkedList();
        circularLinkedList.insert(5);
        circularLinkedList.insert(10);
        circularLinkedList.insert(15);
        circularLinkedList.insert(20);
        circularLinkedList.insert(25);
        circularLinkedList.insert(30);

        System.out.println("Going to traverse the list");
        circularLinkedList.traverse();
        System.out.println();

        System.out.println("Delete 15 from the list");
        circularLinkedList.delete(15);

        System.out.println("Going to traverse the list after deletion ");
        circularLinkedList.traverse();
        System.out.println();

        System.out.println("Going to search 20 in the list");
        System.out.print(circularLinkedList.search(20));
    }

Conclusion

In this article, we discussed how to implement the circular linked list in Java and performed different common operations such as Insertion, Deletion, and Search in a circular linked list.