Count Total Nodes in Circular Linked List

Java Program to Count the Number of Nodes in a Circular Linked List

In this page, we’ll take a look at a program to Count Total Nodes in Circular Linked List in Java, a loop is required until the very first element reappears. Circular linked lists have a head and tail. 

In this article, we will focus on counting the total number of nodes present in a circular singly linked list using Java. The task involves traversing the list while maintaining a counter until we reach the starting node again.

count nodes of a linked list in java programming

Understanding Circular Linked List

In a singly circular linked list, each node contains two parts:

  1. data: The value stored in the node
  2. next: Reference to the next node

In contrast to a singly linked list where the last node’s next is null, in a circular linked list, the last node’s next points back to the head node.

Problem Statement:

Given the head of a circular singly linked list, write a program to count the total number of nodes in the list.

Count Total Nodes in Circular Linked List In java

Algorithm:

To count the total nodes in a circular linked list, follow the below steps:

Step by Step Algorithm:

  1. Check if head is null: If the list is empty, return count as 0
  2. Initialize a counter: Set count = 1 since the head is the first node
  3. Create a temporary pointer: Let current = head.next
  4. Traverse the list until we reach head again
  • While current != head
  • Increment count
  • Move current to current.next

Return the counter value.

Code Implementation:

Run
// Node class definition
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// CircularLinkedList class
public class CircularLinkedList {

    Node head;

    // Function to add a node to the circular linked list
    public void addToEmpty(int data) {
        if (head != null)
            return;

        Node newNode = new Node(data);
        head = newNode;
        newNode.next = head;
    }

    public void addNode(int data) {
        if (head == null) {
            addToEmpty(data);
            return;
        }

        Node newNode = new Node(data);
        Node temp = head;

        while (temp.next != head) {
            temp = temp.next;
        }

        temp.next = newNode;
        newNode.next = head;
    }

    // Function to count nodes in a circular linked list
    public int countNodes() {
        if (head == null)
            return 0;

        int count = 1;
        Node current = head.next;

        while (current != head) {
            count++;
            current = current.next;
        }

        return count;
    }

    // Function to display the list - for verification
    public void display() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }

    // Main method for testing
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();

        cll.addNode(10);
        cll.addNode(20);
        cll.addNode(30);
        cll.addNode(40);

        System.out.print("Circular Linked List: ");
        cll.display();

        int totalNodes = cll.countNodes();
        System.out.println("Total number of nodes: " + totalNodes);
    }
}

Output:

Circular Linked List: 10 20 30 40 
Total number of nodes: 4

Code to Count Total Nodes in Circular Linked List in Java

1. Code to Count Total Nodes in Singly Circular Linked List

  • It implements a singly circular linked list, where each node contains an element and a next pointer that links to the next node, and the last node connects back to the head.
  • It supports adding nodes at the end and traversing the list in a single direction. The countNodes() method uses the next pointer to loop through nodes until it reaches the head again and counts the total number of nodes.
  • This structure is memory efficient and suitable for simple circular list operations.

Specifications:

  • Node: element, next

  • Circularity: Single link (last node → head)

  • Memory: Less usage

  • Traversal: Forward only

  • prev pointer: Not present

Code:

Run

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.add(10);
        Obj.add(20);
        Obj.add(30);
        Obj.add(40);
        Obj.add(50);
        Obj.add(60);

        Obj.print();
        Obj.countNodes();
    }
    public class Node{
        int element;
        Node next;

        public Node(int element) {
            this.element = element;
        }
    }
    int cnt;
    static Node list1, list2;
    public Node head = null;
    public Node tail = null;
    public void print() {
        Node current = head;
        if(head == null) {
            System.out.println("Empty List");
        }
        else {
            System.out.println("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println();
        }
    }
    public void print(Node head) {
        Node current = head;
        if(head == null) {
            System.out.println("Empty List");
        }
        else {
            System.out.println("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println();
        }
    }

    public void add(int element){
        Node newNode = new Node(element);
        if(head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head;
        }
        else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head;
        }
    }
    public void countNodes() {
        Node temp = head;
        do{
            cnt++;
            temp = temp.next;
        }while(temp != head);
        System.out.println("Number of Nodes in the list is "+cnt);
    }
}

Output

Circular Linked List is
 10 20 30 40 50 60
Number of Nodes in the list is 6

2. Code to Count Total Nodes in Doubley Circular Linked List

  • It implements a doubly circular linked list, where each node contains an element, a next pointer to the next node, and a prev pointer to the previous node.
  • Like Code 1, it adds nodes to the end and connects the last node back to the head, but also links nodes backward.
  • However, the prev pointer is initialized but not utilized in traversal or other operations.
  • The list is capable of bi directional traversal and easier deletion operations if extended.

Specifications:

  • Node: element, next, prev

  • Circularity: Double link (last node → head, head → last node)

  • Memory: More usage (due to prev)

  • Traversal: Forward (only implemented), reverse possible

  • prev pointer: Present but unused

Code:

Run
import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.add(10);
        Obj.add(20);
        Obj.add(30);
        Obj.add(40);
        Obj.add(50);
        Obj.add(60);

        System.out.println("Original List");
        Obj.print();

        Obj.countNodes();
    }
    public class Node{
        int element;
        Node next;
        Node prev;

        public Node(int element) {
            this.element = element;
        }
    }
    int cnt;
    static Node list1, list2;
    public Node head = null;
    public Node tail = null;
    public void print() {
        Node temp = head;
        if(head == null) {
            System.out.println("null");
        }
        else {
            do{
                System.out.print(" "+ temp.element);
                temp = temp.next;
            }while(temp != head);
            System.out.println();
        }
    }

    public void add(int element){
        Node newNode = new Node(element);
        if(head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head;
            newNode.prev=head;
        }
        else {
            tail.next = newNode;
            newNode.prev=tail;
            tail = newNode;
            tail.next = head;
        }
    }
    public void print(Node head) {
        Node current = head;
        if(head == null) {
            System.out.println("Empty List");
        }
        else {
            System.out.println("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println();
        }
    }

    public void countNodes() {
        Node temp = head;
        do{
            cnt++;
            temp = temp.next;
        }while(temp != head);
        System.out.println("Number of Nodes in the list is "+cnt);
    }

}

Output

Original List
 10 20 30 40 50 60
Number of Nodes in the list is 6

Conclusion

  • Counting the total number of nodes in a circular linked list involves careful traversal to detect when we loop back to the starting node.
  • The key difference from linear linked list traversal is the stopping condition.
  • This concept is fundamental when working with circular data structures in areas like memory management, scheduling, and real time systems.

Learn DSA

FAQ's related to Segregate 0s and 1s in an array

Answer:

To count nodes in a circular linked list in Java, start at the head node and use a loop to traverse using the next pointer. Increment a counter at each step, and stop when you reach the head again.

A do while loop is recommended to ensure at least one iteration even if the list contains a single node.

Answer:

  • do while loop is preferred because in a circular linked list, the last node connects back to the head, and we must process the head before checking the condition.
  • while loop might skip the only node in a single node list if not carefully written.

Answer:

  • Time Complexity: O(n), where n is the number of nodes
  • Space Complexity: O(1), since no additional data structures are used

Answer:

Yes, the counter (e.g., cnt) should be reset to 0 at the beginning of the countNodes() method. If not reset, calling the method multiple times will result in an incorrect count due to accumulation from previous executions.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription