1. Introduction

A Circular Linked List is a variation of the standard linked list where the last node points back to the first node instead of having a null reference. This creates a closed loop in the list. The primary challenge with a circular linked list is in traversing it. Because it doesn’t end like a standard list, a simple traversal can lead to an infinite loop. In this post, we’ll explore how to traverse a circular linked list in Java without getting stuck in an endless loop.

2. Program Steps

1. Start from the head of the circular linked list.

2. Traverse the list until you reach the head again.

3. To avoid infinite loops, use a condition to stop the traversal once you encounter the head node for the second time.

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; // Pointing back to itself to maintain circularity
        } else {
            Node temp = head;
            while (temp.next != head) { // Traverse till the end of list
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head; // New node points to head to maintain circularity
        }
    }

    // Function to print the circular linked list
    public void printList() {
        if (head == null) {
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }

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

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

        list.printList();
    }
}

Output:

10 20 30 40

4. Step By Step Explanation

1. A Node class is created to represent the elements in our circular linked list.

2. The CircularLinkedList class provides the methods to add nodes and print the list.

3. In the append method, if the list is empty (i.e., the head is null), we set the new node as the head and make its next point to itself. This makes the single node circular.

4. If the list is not empty, we traverse to the end of the list and make the last node's next point to the new node. The new node's next is set to the head to ensure the list remains circular.

5. The printList method is designed to print the nodes of the circular linked list without entering an infinite loop. We start from the head and keep traversing and printing nodes until we reach the head again.

6. The do-while loop ensures that we at least print the head node once even if it's the only node in the list.

This approach enables us to effectively traverse and work with circular linked lists in Java.