Circular Linked List Implementation in Java

1. Introduction

A circular linked list is a variation of the traditional linked list wherein the last node of the list points back to the first node instead of having a null reference. This structure creates a closed loop. It can be useful in applications where data needs to be rotated or processed in a circular manner, like managing processes in an operating system or multimedia playlist cycling.

2. Implementation Steps

1. Define a Node class to represent individual elements of the circular linked list.

2. Define a CircularLinkedList class which will:

a. Have a single reference head pointing to the start of the list.

b. Provide methods like add(), delete(), display(), and isEmpty().

3. Implement these methods to manage the circular linked list.

4. Create an instance of the CircularLinkedList class and perform operations in a main() method to demonstrate its functionality.

3. Implementation in Java

class Node<T> {
    T data;
    Node<T> next;
    Node(T data) {
        this.data = data;
        this.next = this;  // By default, a node points to itself
    }
}
class CircularLinkedList<T> {
    private Node<T> head;
    public CircularLinkedList() {
        head = null;
    }
    // Check if the list is empty
    public boolean isEmpty() {
        return head == null;
    }
    // Add element to the end of the list
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != head) {
                current = current.next;
            }
            current.next = newNode;
            newNode.next = head;
        }
    }
    // Delete the first occurrence of the given element
    public boolean delete(T data) {
        if (isEmpty()) return false;
        Node<T> current = head;
        Node<T> prev = null;
        do {
            if (current.data.equals(data)) {
                if (prev != null) {
                    prev.next = current.next;
                    if (current == head) head = current.next;  // Adjust head if needed
                } else {
                    Node<T> temp = head;
                    while (temp.next != head) temp = temp.next;
                    head = head.next;
                    temp.next = head;  // Last node should point to the new head
                }
                return true;
            }
            prev = current;
            current = current.next;
        } while (current != head);
        return false;
    }
    // Display the list
    public void display() {
        if (isEmpty()) return;
        Node<T> current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println("(back to) " + current.data);
    }
    public static void main(String[] args) {
        CircularLinkedList<Integer> cll = new CircularLinkedList<>();
        cll.add(10);
        cll.add(20);
        cll.add(30);
        cll.display();  // Outputs: 10 -> 20 -> 30 -> (back to) 10
        cll.delete(20);
        cll.display();  // Outputs: 10 -> 30 -> (back to) 10
    }
}

Output:

10 -> 20 -> 30 -> (back to) 10
10 -> 30 -> (back to) 10

Explanation:

1. The Node class is a generic representation of each element. It contains a data field and a next reference. In a circular linked list, by default, every node points to itself initially.

2. The CircularLinkedList class maintains the head reference that marks the start of the list.

3. isEmpty() checks if the list has any nodes.

4. add() appends a node to the list. If it's the first node, it sets it as the head. Otherwise, it iterates to the last node and updates its next reference.

5. delete() removes the first occurrence of a specified element. If the element to delete is the head, it updates the last node's next reference to point to the second node.

6. display() prints each node in the list until it loops back to the head.

7. The main() method showcases operations on a CircularLinkedList of Integers, demonstrating the structure's behavior.