In this post, we will discuss about the different algorithm for loop detection in a linked list.
Before writing the logic for loop detection in a linked list, we should understand the type and properties of the input parameter of this problem. We need a composite linked list consist of a singly linked list connected with a singly circular linked list. Below is the node structure of a given composite linked list.
To form a composite linked list, we will create one instance of SinglyLinkedList and one instance of SinglyCircularLinkedList then add the singly circular linked list to singly linked list. Refer the SinglyLinkedList.java and SinglyCircularLinkedList.java.
Now, we are going to discuss two techniques by which we can detect the loop in a given composite linked list and count the number of nodes in loop.
- Hashing : In Hashing technique, put all the node addresses into a HashSet and check if the node is available in HashSet. If yes, then loop detected in a composite linked list and stop moving to the next node. If no, then add the address into HashSet and move to the next node.This technique is good in case of less number of nodes in composite linked list, but if number of nodes in composite linked list is very huge, performance will be poor because we need to traverse through all the nodes to check the loop.
- Floyd’s loop detection algorithm: According to Floyd’s loop detection algorithm, if slow moving pointer and fast moving pointer meet at some common point then there is a loop in a linked list. Definition of slow moving pointer and fast moving pointer refers, when a pointer move to the next consecutive node, that is called slow moving pointer. When a pointer skip the next consecutive node and move to the next of next node, that is called fast moving pointer.
Below is the code snippet to detect loop in a linked list using Hashing and Floyd’s loop detection algorithm.
Node.java
package com.netSurfingZone.linkedList.misc;
public class Node<T> {
private T data ;
private Node<T> next;
public Node(T data) {
this.data = data;
}
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;
}
}
SinglyLinkedList.java
package com.netSurfingZone.linkedList.misc;
public class SinglyLinkedList<T>{
private int size = 0;
private Node<T> node;
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNext(newNode);
}
size++;
}
public void add(Node<T> newNode,int connectedNodes) {
if (newNode == null) {
return;
}
if (node == null) {
node = newNode;
} else {
Node<T> lastNode = getLastNode(node);
lastNode.setNext(newNode);
}
size=size + connectedNodes;
}
public Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> next(Node<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
public int size() {
return this.size;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNext() != null) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
}
SinglyCircularLinkedList.java
package com.netSurfingZone.linkedList.misc;
public class SinglyCircularLinkedList<T>{
private int size = 0;
private Node<T> rootNode;
private Node<T> lastNode;
/**
* Add element
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
/**
* if circular linked list is empty and trying to add data, newly created node will be the
* root node and root node and last node will be same.
*/
if (rootNode == null) {
rootNode = new Node<T>(data);
lastNode=rootNode;
// connect last node to root node
lastNode.setNext(rootNode);
} else {
Node<T> newNode = new Node<T>(data);
lastNode.setNext(newNode);
lastNode=newNode;
// Last node will again connected to first Node;
lastNode.setNext(rootNode);
}
size++;
}
public Node<T> getRootNode(){
return this.rootNode;
}
public int size() {
return this.size;
}
private Node<T> next(Node<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
}
LoopDetectionInLinkedListTest.java
package com.netSurfingZone.linkedList.misc;
import java.util.HashSet;
public class LoopDetectionInLinkedListTest {
public static void main(String[] args) {
SinglyLinkedList<String> singlyLinkedList=new SinglyLinkedList<String>();
singlyLinkedList.add("A");
singlyLinkedList.add("B");
singlyLinkedList.add("C");
SinglyCircularLinkedList<String> circularLinkedList=new SinglyCircularLinkedList<String>();
circularLinkedList.add("D");
circularLinkedList.add("E");
circularLinkedList.add("F");
circularLinkedList.add("G");
// Form composite linked list
singlyLinkedList.add(circularLinkedList.getRootNode(), circularLinkedList.size());
// A-->B-->C-->D-->E-->F-->G-->
// ^ |
// |______________|
boolean loopDetected=detectLoopByHashing(singlyLinkedList);
System.out.println("Loop Detected using Hashing: " +loopDetected);
System.out.println(" ");
System.out.println("**********FLOYD LOOP DETECTION**********");
int NoOfNodesPresentInLoop=detectLoopByFloydAlgo(singlyLinkedList);
System.out.println("Number of nodes present in Loop: "+ NoOfNodesPresentInLoop);
}
/**
* Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point.
* If slow_pointer and fast_pointer meet at some point then there is a loop
*
*/
private static int detectLoopByFloydAlgo(SinglyLinkedList<String> singlyLinkedList) {
if(singlyLinkedList.size()==0) {
System.out.println("No Loop Found");
return 0;
}
Node<String> head=singlyLinkedList.getNode(0);
Node slow_pointer=head;
Node fast_Pointer=head;
while(slow_pointer !=null && fast_Pointer !=null && fast_Pointer.getNext() !=null) {
slow_pointer=slow_pointer.getNext();
fast_Pointer=fast_Pointer.getNext().getNext();
// Loop found
if(slow_pointer !=null && fast_Pointer.getNext() !=null && slow_pointer == fast_Pointer) {
System.out.println("Loop Found");
return countNodes(slow_pointer);
}
}
System.out.println("No Loop Found");
return 0;
}
//Returns number of nodes present in loop.
private static int countNodes(Node n) {
int res = 1;
Node temp = n;
while (temp.getNext() != n)
{
res++;
temp = temp.getNext();
}
return res;
}
/**
* Put all the node addresses into HashSet and check if the node is exists in HashSet , if yes then loop found.
* if No , add the address in HashSet and check for next node.
*
*/
private static boolean detectLoopByHashing(SinglyLinkedList<String> singlyLinkedList) {
HashSet<Node> hash=new HashSet<>();
Node nextAddress=null;
if(singlyLinkedList.size()==0) {
return false;
}
Node<String> firstNode=singlyLinkedList.getNode(0);
if(firstNode!=null) {
hash.add(firstNode);
nextAddress=firstNode.getNext();
}
while(nextAddress != null) {
if(hash.contains(nextAddress)) {
return true;
}
else {
hash.add(nextAddress);
nextAddress=nextAddress.getNext();
}
}
return false;
}
}
Console Output:
Loop Detected using Hashing: true
**********FLOYD LOOP DETECTION**********
Loop Found
Number of nodes present in Loop: 4
Hope you liked this post. Please leave your comments or suggestions.
Cheers 🙂