Traversal of Circular Linked List

Last Updated: 06 October, 2024 🕓 5 Mins Read

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

  
  // 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);
    }
  }

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

2. Traverse a Circular Linked List using Recursive Approach

  
  // 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);
    }
  }