1. Introduction

A Circular LinkedList is a variation of a linked list in which the last node points back to the first node instead of having a null reference. This forms a closed loop or circle. The main advantage of a Circular LinkedList is that we can traverse the whole list starting from any point. This blog post will delve into the Java implementation of a Circular LinkedList covering common operations such as insertion and deletion.

2. Program Steps

1. Define the Node class which represents individual elements of the Circular LinkedList.

2. Create a CircularLinkedList class that includes methods for various operations.

3. Implement the different operations and test the CircularLinkedList.

3. Code Program

// Step 1: Define the Node class
class Node {
    int data;
    Node next;

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

// Step 2: Define the CircularLinkedList class
class CircularLinkedList {
    Node head;

    // Insert a new node at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }

    // Insert a new node at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
        } else {
            newNode.next = newNode;
        }
        head = newNode;
    }

    // Delete a node given its value
    public void delete(int value) {
        if (head == null) {
            return;
        }
        Node temp = head, prev = null;
        do {
            if (temp.data == value) {
                if (prev != null) {
                    prev.next = temp.next;
                    if (head == temp) {
                        head = temp.next;
                    }
                } else {
                    Node temp2 = head;
                    while (temp2.next != head) {
                        temp2 = temp2.next;
                    }
                    head = temp.next;
                    temp2.next = head;
                }
                return;
            }
            prev = temp;
            temp = temp.next;
        } while (temp != head);
    }

    // Display the list
    public void display() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        // Step 3: Implement and test the CircularLinkedList
        CircularLinkedList list = new CircularLinkedList();
        list.insertAtEnd(10);
        list.insertAtBeginning(5);
        list.insertAtEnd(15);
        list.display();

        list.delete(10);
        list.display();
    }
}

Output:

5 10 15
5 15

4. Step By Step Explanation

Step 1: The basic unit of the Circular LinkedList is represented by the Node class. It has a data field and a next pointer.

Step 2: The CircularLinkedList class provides:

1. insertAtEnd: This method appends a new node at the end of the list.

2. insertAtBeginning: This adds a node to the start of the list.

3. delete: This removes a node based on its value.

4. display: It traverses and prints the entire list.

Step 3: In the Main class, we test the CircularLinkedList. The test involves adding nodes at the beginning and end, and then deleting a node.

The output shows the nodes of the Circular LinkedList after each primary operation.