इस लेख में, हम समझेंगे कि LinkedList में लूप कैसे डिटेक्ट करें। एक लिंक्ड लिस्ट डेटा स्ट्रक्चर्स का एक क्रम है, जो लिंक्स के माध्यम से एक साथ जुड़े होते हैं। लिंक्ड लिस्ट लिंक्स का एक क्रम है जिसमें आइटम्स होते हैं। प्रत्येक लिंक में दूसरे लिंक का कनेक्शन होता है।
नीचे इसका प्रदर्शन है:
मान लीजिए हमारा इनपुट है:
प्रोग्राम चलाएं
वांछित आउटपुट होगा:
लिंक्ड लिस्ट में लूप मौजूद है
एल्गोरिदम
चरण 1 - शुरू चरण 2 - घोषित करें चरण 3 - मान परिभाषित करें चरण 4 - संबंधित मेंबर्स के साथ क्लास परिभाषित करें चरण 5 - क्लास का इंस्टेंस बनाएं, और नोड्स इनिशियलाइज़ करें चरण 6 - चेक करने के लिए फंक्शन्स परिभाषित करें कि क्या यह लूप है चरण 7 - इसके लिए, एक HashSet बनाएं, और टॉपमोस्ट नोड में एलिमेंट्स जोड़ें चरण 8 - हर इटरेशन के बाद नोड को अगले एलिमेंट पर पॉइंट करें चरण 9 - मेन मेथड में, इंस्टेंस बनाएं और 'push' मेथड का उपयोग करके लिस्ट में एलिमेंट्स जोड़ें चरण 10 - 'check_loop' मेथड कॉल करें, और कंसोल पर प्रासंगिक संदेश प्रदर्शित करें चरण 11 - रुकें
उदाहरण 1: HashSet दृष्टिकोण
यहाँ, हम लूप खोजने के लिए ट्रैवर्सल मेथड का उपयोग करते हैं।
import java.util.*;
public class Demo {
static Node head;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
static public void push(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
static boolean check_loop(Node head) {
HashSet s = new HashSet();
while (head != null) {
if (s.contains(head))
return true;
s.add(head);
head = head.next;
}
return false;
}
public static void main(String[] args) {
System.out.println("आवश्यक पैकेज आयात किए गए हैं");
Demo input_list = new Demo();
input_list.push(45);
input_list.push(60);
input_list.push(75);
input_list.push(90);
input_list.head.next.next.next.next = input_list.head;
if (check_loop(head))
System.out.println("लिंक्ड लिस्ट में लूप मौजूद है");
else
System.out.println("लिंक्ड लिस्ट में लूप मौजूद नहीं है");
}
}
आउटपुट
आवश्यक पैकेज आयात किए गए हैं लिंक्ड लिस्ट में लूप मौजूद है
उदाहरण 2: फ्लॉयड का साइकिल-फाइंडिंग एल्गोरिदम (टॉर्टॉइज़ और हेयर)
यहाँ, हम ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग प्रदर्शित करने के लिए ऑपरेशन्स को फंक्शन्स में एनकैप्सुलेट करते हैं।
public class Demo {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public boolean check_loop() {
Node first_node = head;
Node second_node = head;
while (first_node != null && first_node.next != null) {
first_node = first_node.next.next; // तेज़ पॉइंटर (2 कदम)
second_node = second_node.next; // धीमा पॉइंटर (1 कदम)
if (first_node == second_node) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Demo input_list = new Demo();
input_list.head = new Node(45);
Node second_node = new Node(60);
Node third_node = new Node(75);
Node fourth_node = new Node(90);
input_list.head.next = second_node;
second_node.next = third_node;
third_node.next = fourth_node;
fourth_node.next = second_node; // लूप बनाता है
System.out.print("लिंक्ड लिस्ट के एलिमेंट्स हैं: ");
int i = 1;
while (i <= 4) {
System.out.print(input_list.head.value + " ");
input_list.head = input_list.head.next;
i++;
}
boolean loop = input_list.check_loop();
if (loop) {
System.out.println("\nलिंक्ड लिस्ट में लूप है।");
} else {
System.out.println("\nलिंक्ड लिस्ट में लूप नहीं है।");
}
}
}
आउटपुट
आवश्यक पैकेज आयात किए गए हैं लिंक्ड लिस्ट में लूप मौजूद है
दोनों दृष्टिकोणों की तुलना
| पहलू | HashSet दृष्टिकोण | फ्लॉयड का एल्गोरिदम |
|---|---|---|
| समय जटिलता | O(n) | O(n) |
| स्पेस जटिलता | O(n) | O(1) |
| लूप की शुरुआत ढूंढना | आसान | अतिरिक्त चरणों की आवश्यकता |
| कार्यान्वयन | सरल | थोड़ा जटिल |
सिफारिश: स्पेस एफिशिएंसी के लिए फ्लॉयड का एल्गोरिदम पसंद किया जाता है।
