1. Introduction

A Circular Linked List is a variation of a standard linked list in which the last node points back to the first node instead of having a null reference, forming a closed loop. One common operation with linked lists, including circular ones, is the deletion of nodes. In this blog post, we will demonstrate how to delete nodes from a circular linked list in Java.

2. Program Steps

1. Check if the Circular Linked List is empty. If yes, print an error message.

2. If the list is not empty and the node to be deleted is the head node, adjust pointers accordingly.

3. Traverse the list to find the node to be deleted and its previous node.

4. Adjust the next pointer of the previous node to bypass the node to be deleted.

5. If the node to be deleted was the only node in the list, set the head to null.

6. Delete the node by making its reference null.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class CircularLinkedList {
    Node head;

    // Function to add a new node at the end of the list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }

    // Function to delete a node from the circular linked list
    public void deleteNode(int key) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        // If the head node itself holds the key to be deleted
        if (head.data == key) {
            Node curr = head;
            while (curr.next != head) {
                curr = curr.next;
            }

            if (curr == head) {  // Only one node in the list
                head = null;
            } else {
                curr.next = head.next;
                head = head.next;
            }
            return;
        }

        Node prev = null, curr = head;
        while (curr.data != key) {
            if (curr.next == head) {
                System.out.println("Given node not found in the list");
                return;
            }
            prev = curr;
            curr = curr.next;
        }

        prev.next = curr.next;
    }

    // Function to print the circular linked list
    public void printList() {
        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 static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        list.append(10);
        list.append(20);
        list.append(30);
        list.append(40);

        System.out.println("Original List:");
        list.printList();

        list.deleteNode(20);
        System.out.println("List after deleting node with value 20:");
        list.printList();

        list.deleteNode(10);
        System.out.println("List after deleting node with value 10:");
        list.printList();
    }
}

Output:

Original List:
10 20 30 40
List after deleting node with value 20:
10 30 40
List after deleting node with value 10:
30 40

4. Step By Step Explanation

1. The Node class represents each node in the Circular Linked List and has an integer data and a reference to the next node.

2. The CircularLinkedList class has methods for appending data to the list, deleting nodes from it, and printing the list.

3. The append method adds a new node to the end of the list. If the list is empty, the new node becomes the head, and its next points to itself.

4. The deleteNode method deletes a node from the list based on a given key. There are several scenarios to consider:

– If the list is empty, print an error message.

– If the head node itself needs to be deleted, adjust the last node's next pointer and move the head pointer.

– If the node to be deleted is not the head, traverse the list to find it and its previous node, then adjust the previous node's next pointer.

– If the node to be deleted was the only node in the list, set the head to null.

5. The printList method prints each node in the circular linked list. It uses a do-while loop to