In this post, We will learn How to write a Java program to count the number of nodes in a circular linked list
Problem Statement in another word:
Check Whether the given LinkedList is NULL terminated. If there is a Cycle/Loop then Find the Length of the Loop.
For Below given diagram Answer would be 4
This problem is the extension of How to check whether a linked list has a loop/cycle in java ? After finding the loop in the LinkedList, keep the fastReference as it is. the slowReference keeps on moving until it again comes back to fastReference . While moving slowReference , use a counter variable which increments at the rate of 1.
Complete Source is given Below:
Node.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
package com.kkjavatutorials.util; /** * This class represent Node in Linked List * @author KK JavaTutorials */ public class Node<T>{ //Data hold by LinkedList Node private T data; //Reference to point next Node private Node<T> next; public Node(T data) { super(); this.data = data; this.next = null; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } } |
LinkedList.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
package com.kkjavatutorials.util; /** * How to find number of nodes in Circular linked list in Java * @author KK JavaTutorials */ public class LinkedList<T> { //head always point to first node private Node<T> head; /** * Method to insert Node in Linked List * @param newNode insert to List */ public void insert(Node<T> newNode) { if(isEmpty()) { head = newNode; }else { Node<T> current = head; while(current.getNext() !=null) { current = current.getNext(); } current.setNext(newNode); } } //Check if Linked is empty private boolean isEmpty() { return head == null; } /** * Method to find Circular Nodes * in LinkedList * @return Number of Circular Nodes */ public int countNodesInCircularList() { int numberOfNodeInCircularList = 0; boolean isCycle = false; //Initially both slow and fast reference pointing to head Node<T> slowReference = head; Node<T> fastReference = head; /*Now traverse slowReference one node and *fast reference two nodes at time if both pointers meet any point of time that means List is Circular*/ while (slowReference != null && fastReference !=null && fastReference.getNext() != null) { fastReference = fastReference.getNext().getNext(); slowReference = slowReference.getNext(); //if slow and fast reference meets that means list is circular if(slowReference == fastReference) { isCycle = true; break; } } /* If List is not Circulat Then print Message "List does not Circular!!" And exit*/ if(!isCycle) { System.out.println("List does not Circular!!"); System.exit(1); } /** * Now traverse slowReference and * increment numberOfNodeInCircularList * also keep checking if we reach * to fastReference pointer. */ while (slowReference !=null) { numberOfNodeInCircularList++; slowReference = slowReference.getNext(); if(slowReference == fastReference ) { break; } } return numberOfNodeInCircularList; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
package com.kkjavatutorials.util; /** * @author KK JavaTutorials * Client program to count number of nodes in circular linked list */ public class ClientTest { public static void main(String[] args) { //Create first LinkedList Instance LinkedList<Integer> linkedList1 = new LinkedList<>(); Node<Integer> node = new Node<Integer>(40); linkedList1.insert(new Node<Integer>(10)); linkedList1.insert(new Node<Integer>(20)); linkedList1.insert(new Node<Integer>(30)); linkedList1.insert(node); linkedList1.insert(new Node<Integer>(50)); linkedList1.insert(new Node<Integer>(60)); linkedList1.insert(new Node<Integer>(70)); linkedList1.insert(node); int nodeCountInCircularList = linkedList1.countNodesInCircularList(); System.out.println("Total Number of Cicular Nodes:"+nodeCountInCircularList); System.out.println("-------------------------------------------------------------"); //Create Second LinkedList Instance LinkedList<Integer> linkedList2 = new LinkedList<>(); Node<Integer> node1 = new Node<Integer>(2); linkedList2.insert(node1); linkedList2.insert(new Node<Integer>(5)); linkedList2.insert(new Node<Integer>(8)); linkedList2.insert(new Node<Integer>(40)); linkedList2.insert(new Node<Integer>(10)); linkedList2.insert(new Node<Integer>(90)); linkedList2.insert(node1); int nodeCountInCircularList2 = linkedList2.countNodesInCircularList(); System.out.println("Total Number of Cicular Nodes:"+nodeCountInCircularList2); } } |
Output Of this Program:
Total Number of Cicular Nodes:4
————————————————————-
Total Number of Cicular Nodes:6
You May Also Like:
Implementing a Circular Singly Linked List in Java ?
How to check whether a linked list has a loop/cycle in java ?
Find start node of loop in Singly LinkedList in java
That’s all about the Count the number of nodes in a circular linked list?
If you have any feedback or suggestion please feel free to drop in below comment box.