Java Program to Detect loop in a LinkedList

Introduction

Detecting a loop in a linked list is a common problem in computer science, often encountered in the context of algorithm design and data structure management. This issue is critical as it can lead to infinite loops and system crashes if not properly handled. Identifying loops effectively is therefore essential for robust software development.

In this article, you will learn how to detect a loop in a LinkedList in Java. Techniques discussed will include the use of Floyd’s Cycle-Finding Algorithm and a hashing approach. Through detailed examples, gain the proficiency to implement these methods in your Java programs to ensure integrity and performance in operations involving linked lists.

Detecting Loop with Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Understanding the Algorithm

Floyd's Cycle-Finding Algorithm, often called the Tortoise and Hare algorithm, uses two pointers at different speeds to determine if a cycle exists in the list.

Step-by-Step Implementation

1. Initialize two pointers, slow and fast. Initially, both point to the head of the linked list.

2. Move slow by one step and fast by two steps in each iteration of the loop.

3. If a loop exists, the fast pointer, eventually meets the slow pointer.

   java Copy

   public class LinkedList {
       static class Node {
           int data;
           Node next;
           Node(int data) {
               this.data = data;
               this.next = null;
           }
       }
   
       Node head;
   
       void detectLoop() {
           Node slow = head;
           Node fast = head;
           boolean loopExists = false;
   
           while (fast != null && fast.next != null) {
               slow = slow.next;       // move slow by 1
               fast = fast.next.next; // move fast by 2
   
               if (slow == fast) {
                   loopExists = true;
                   break;
               }
           }
   
           if (loopExists)
               System.out.println("Loop detected");
           else
               System.out.println("No Loop detected");
       }
   }
   

   In this example, if slow and fast meet, it confirms a loop in the LinkedList.

Detecting Loop Using Hashing

Understanding the Hashing Method

This approach involves tracking visited nodes using a set data structure. If a node reappears in the set, it indicates a cycle.

Step-by-Step Implementation

1. Initialize a hash set to keep track of visited nodes.

2. Traverse the linked list, checking each node’s presence in the set.

3. If a node is revisited, a loop is detected.

   java Copy

   import java.util.HashSet;
   import java.util.Set;
   
   public class LinkedList {
       static class Node {
           int data;
           Node next;
           Node(int data) {
               this.data = data;
               this.next = null;
           }
       }
   
       Node head;
   
       void detectLoopUsingHashing() {
           Set<Node> nodesSeen = new HashSet<>();
           Node current = head;
           while (current != null) {
               if (nodesSeen.contains(current)) {
                   System.out.println("Loop detected");
                   return;
               }
               nodesSeen.add(current);
               current = current.next;
           }
           System.out.println("No Loop detected");
       }
   }
   

   This code adds each traversed node to a hash set. Upon encountering a node that already exists in the set, it prints "Loop detected".

Conclusion

Detecting a loop in a LinkedList is an essential skill in Java programming, especially when dealing with complex data structures and algorithms. By implementing the Floyd's Cycle-Finding Algorithm or using a simple hash set for loop detection, maintain the integrity and performance of your applications. Continue practicing these techniques to develop a strong understanding of linked lists and related algorithms, ensuring both reliability and efficiency in your Java coding projects.