DSA Java - Circular Linked List

Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list

Singly Linked List as Circular

Doubly Linked List as Circular

as per above shown illustrations, following are the important points to be considered.

• Last Link'next points to first link of the list in both cases of singly as well as doubly linked list.

• First Link's prev points to the last of the list in case of doubly linked list.

public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    private Node head;

    public CircularLinkedList() {
        this.head = null;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public void insert(int data) {
        Node newNode = new Node(data);

        if (isEmpty()) {
            newNode.next = newNode;  // The new node points to itself
            head = newNode;  // Update the head
        } else {
            newNode.next = head.next;  // Make the new node point to the second node
            head.next = newNode;  // Make the head node point to the new node
            head = newNode;  // Update the head to the new node
        }
    }

    public void delete(int data) {
        if (isEmpty()) {
            System.out.println("The list is empty.");
            return;
        }

        Node current = head;

        // If the head node itself contains the data to be deleted
        if (current.data == data) {
            while (current.next != head) {
                current = current.next;
            }

            current.next = head.next;
            head = head.next;
            return;
        }

        // Search for the node to be deleted
        Node prev = current;
        current = current.next;

        while (current != head) {
            if (current.data == data) {
                prev.next = current.next;
                return;
            }

            prev = current;
            current = current.next;
        }

        System.out.println("The specified data was not found.");
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("The list is empty.");
            return;
        }

        Node current = head;

        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != head);

        System.out.println();
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        list.display();  // Output: 4 3 2 1

        list.delete(3);

        list.display();  // Output: 4 2 1
    }
}

In this example, the CircularLinkedList class represents the circular linked list. It has a Node class as an inner class to represent each node in the list. The Node class has a data field and a next field to point to the next node.

The circular linked list is initialized with a head node, which is initially set to null. The isEmpty() method checks if the list is empty. The insert() method inserts a new node at the beginning of the list. The delete() method deletes a node containing the specified data from the list. The display() method displays the elements of the list.

In the main() method, we create a circular linked list object, insert some elements, display the list, and then delete an element before displaying the updated list.