Traversal of Circular Linked List

Q: How do you traverse a circular linked list iteratively?

Java example: static void traverse(Node head) { if (head == null) { return; } Node current = head; do { System.out.print(current.data + " "); current = current.next; } while (current != head); }

Q: Why is a do-while loop used for circular traversal?

The stop condition is current != head. With a normal while loop, that condition is false at the very start, so nothing would be printed. A do-while processes the head first and checks the condition afterwards.

Q: Write a Java method that traverses the list k full rounds.

Java example: static void traverseRounds(Node head, int rounds) { if (head == null) { return; } Node current = head; for (int r = 0; r < rounds; r++) { do { System.out.print(current.data + " "); current = current.next; } while (current != head); System.out.println(); } }

Q: What happens if you use while (current != null) on a circular list?

The loop never ends, because no node has a null next. The program hangs, or, if the loop body collects data, eventually runs out of memory.

Q: Write a Java method to find the sum of all nodes in a circular linked list.

Java example: static int sum(Node head) { if (head == null) { return 0; } int total = 0; Node current = head; do { total += current.data; current = current.next; } while (current != head); return total; }

Q: What is the time and space complexity of circular traversal?

The iterative version is O(n) time and O(1) space. The recursive version is O(n) time and O(n) stack space.

Q: How do you print the nodes of a circular linked list in reverse?

Java example: static void printReverse(Node current, Node head) { if (current.next != head) { printReverse(current.next, head); } System.out.print(current.data + " "); } // Call: if (head != null) printReverse(head, head);

Q: How do you check whether a given linked list is circular during traversal?

Walk from the head. If you reach null, the list is linear; if you come back to the head, it is circular. If the list may loop back to a middle node, use Floyd's slow and fast pointers instead, because the walk would never return to the head.

Traversal of Circular Linked List

Traversing a Circular Linked List means visiting each node in the list starting from a given node and continuing until we return to the starting point. This process allows us to access all elements in the list efficiently, making it a useful technique in various applications such as implementing round-robin scheduling.

In this tutorial, we are going to explore how to traverse a circular linked list in Java.

There are two ways to traverse a list as given below.

Iterative Approach
Recursive Approach

1. Traverse a Circular Linked List using Iterative Approach

TraversalUsingIterative.java

// A Java program to traverse a circular linked list using Iterative approach
public class TraversalUsingIterative {
  // Function to traverse a list using Iterative approach
  static void printList(Node head) {
    // return if list is empty
    if (head == null)
      return;

      Node currNode = head;
    do {
      System.out.print(currNode.data + " ");
      currNode = currNode.next;

    } while (currNode != head);
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a circular linked list
    Node head = new Node(50);
    head.next = new Node(20);
    head.next.next = new Node(40);
    head.next.next.next = new Node(10);
    head.next.next.next.next = new Node(30);
    head.next.next.next.next.next = head;

    System.out.println("Traversing a circular linked list:");
    printList(head);
  }
}

Output

Traversing a circular linked list:
50 20 40 10 30

Time Complexity: O(n), here n represent the total number of nodes in a circular linked list.

Auxiliary Space: O(1)

2. Traverse a Circular Linked List using Recursive Approach

TraversalUsingRecursive.java

// A Java program to traverse a circular linked list using Recursive approach
public class TraversalUsingRecursive {
  static void printList(Node curr, Node head) {

    // return if list is empty
    if (head == null)
      return;

    System.out.print(curr.data + " ");

    if (curr.next == head)
      return;

    printList(curr.next, head);
  }

  public static void main(String[] args) {
    // Create a circular linked list
    Node head = new Node(67);
    head.next = new Node(42);
    head.next.next = new Node(81);
    head.next.next.next = new Node(10);
    head.next.next.next.next = new Node(58);
    head.next.next.next.next.next = head;

    System.out.println("Traversing a circular linked list:");
    printList(head, head);
  }
}

Output

Traversing a circular linked list:
67 42 81 10 58

Time Complexity: O(n)

Auxiliary Space: O(n)

Here n represent the total number of nodes in a circular linked list.

Frequently Asked Questions (FAQ)

Q1. How do you traverse a circular linked list iteratively?

TraverseIterative.java

static void traverse(Node head) {
    if (head == null) {
        return;
    }
    Node current = head;
    do {
        System.out.print(current.data + " ");
        current = current.next;
    } while (current != head);
}

Q2. Why is a do-while loop used for circular traversal?

The stop condition is current != head. With a normal while loop, that condition is false at the very start, so nothing would be printed. A do-while processes the head first and checks the condition afterwards.

Q3. How do you traverse a circular linked list recursively?

TraverseRecursive.java

static void traverse(Node current, Node head) {
    System.out.print(current.data + " ");
    if (current.next != head) {
        traverse(current.next, head);
    }
}

// Call: if (head != null) traverse(head, head);

The head is passed along so that each call knows where to stop.

Q4. Can you start the traversal from any node?

Yes. Pass any node as the start and stop when you come back to it. You will visit every node exactly once, just in a rotated order.

Q5. Write a Java method that traverses the list k full rounds.

TraverseRounds.java

static void traverseRounds(Node head, int rounds) {
    if (head == null) {
        return;
    }
    Node current = head;
    for (int r = 0; r < rounds; r++) {
        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != head);
        System.out.println();
    }
}

Q6. What happens if you use while (current != null) on a circular list?

The loop never ends, because no node has a null next. The program hangs, or, if the loop body collects data, eventually runs out of memory.

Q7. Write a Java method to find the sum of all nodes in a circular linked list.

SumCircular.java

static int sum(Node head) {
    if (head == null) {
        return 0;
    }
    int total = 0;
    Node current = head;
    do {
        total += current.data;
        current = current.next;
    } while (current != head);
    return total;
}

Q8. What is the time and space complexity of circular traversal?

The iterative version is O(n) time and O(1) space. The recursive version is O(n) time and O(n) stack space.

Q9. How do you print the nodes of a circular linked list in reverse?

PrintReverseCircular.java

static void printReverse(Node current, Node head) {
    if (current.next != head) {
        printReverse(current.next, head);
    }
    System.out.print(current.data + " ");
}

// Call: if (head != null) printReverse(head, head);

Q10. How do you check whether a given linked list is circular during traversal?

Walk from the head. If you reach null, the list is linear; if you come back to the head, it is circular. If the list may loop back to a middle node, use Floyd's slow and fast pointers instead, because the walk would never return to the head.

Was this tutorial helpful?

Help Us Improve

Traversal of Circular Linked List

1. Traverse a Circular Linked List using Iterative Approach

2. Traverse a Circular Linked List using Recursive Approach

Frequently Asked Questions (FAQ)