00:00

Find length of Circular Linked List

Last updated:

The length of a circular linked list is the number of nodes in the ring. It is counted by walking once around the ring from the head.

The only difference from a linear list is the stop condition. The last node does not point to null; it points back to the head. So the count stops when the walk returns to the head, and a do-while loop makes sure the head itself is counted. An empty list (head == null) has length 0.

Example: the ring in the diagram has three nodes, so its length is 3.

Circular linked list of three nodes; the last node stores the address of the first node

Example: Find the length of Circular Linked List in Java

FindLengthInCLL.java
// Class representing a node in a circular linked list
class Node {
  public int data;    // Store value of the node
  public Node next;   // Store address of the next node

  // Constructor to initialize a node
  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

// Java program to find the length of a circular linked list
public class FindLengthInCLL {
  // Function to find length of circular linked list
  static void findLength(Node head) {
    int length = 0;
    if (head != null) {
      Node node = head;
      do {
        node = node.next;
        length++;
      } while (node != head);
    }
    System.out.println("Length of Circular Linked List is: " + length);
  }

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

    // Find and print the length of a Circular Linked List
    findLength(head);
  }
}
Output
Length of Circular Linked List is: 5

Time Complexity: O(n), where n is the number of nodes; each node is visited once.

Extra Space: O(1)