In Java, a linked list is a data structure consisting of a sequence of nodes, where each node stores a reference to an object and a reference to the next node in the list.
A loop in a linked list occurs when a node is visited more than once while traversing the list.
Detecting a loop in a linked list is an important task in data structure and algorithmic programming.
In this tutorial, we will discuss how to detect a loop in a linked list using Java programming.
The algorithm for detecting a loop in a linked list is called the “Floyd’s cycle-finding algorithm.”
This algorithm involves the use of two pointers, one that moves at a pace of one node per iteration (slow pointer) and another that moves at a pace of two nodes per iteration (fast pointer).
If the linked list contains a loop, the fast pointer will eventually catch up to the slow pointer.
If the linked list does not contain a loop, the fast pointer will reach the end of the list and the algorithm will terminate.
Here’s the Java code to implement the Floyd’s cycle-finding algorithm:
javaCopy codeclass Node { int data; Node next; Node(int d) { data = d; next = null; } } class LinkedList { Node head; // Function to detect loop in a linked list boolean detectLoop() { Node slow = head; Node fast = head; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; // If slow and fast pointers meet at some point // then there is a loop in the linked list if (slow == fast) { return true; } } return false; } // Function to add a new node at the beginning of the linked list void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } public static void main(String args[]) { LinkedList llist = new LinkedList(); // Creating a linked list with a loop llist.push(20); llist.push(4); llist.push(15); llist.push(10); // Creating a loop in the linked list llist.head.next.next.next.next = llist.head; boolean loop_present = llist.detectLoop(); System.out.println("Loop present: " + loop_present); } }
In this code, the Node
class represents a single node in the linked list, and the LinkedList
class represents the linked list itself.
The detectLoop()
function implements the Floyd’s cycle-finding algorithm to detect a loop in the linked list.
The push()
function adds a new node at the beginning of the linked list.
The main()
function creates a linked list with a loop and calls the detectLoop()
function to detect the loop.
In conclusion, detecting a loop in a linked list is a crucial operation in data structure and algorithmic programming.
The Floyd’s cycle-finding algorithm is an efficient and easy-to-implement algorithm to detect a loop in a linked list.
The Java code presented in this article demonstrates how to implement the Floyd’s cycle-finding algorithm to detect a loop in a linked list.