C++ में लिंक की गई सूची में लूप का पता लगाएं

एक लिंक की गई सूची का अंतिम नोड जिसमें एक लूप है, NULL के बजाय उसी सूची में एक और नोड को संदर्भित करेगा। यदि लिंक की गई सूची में एक नोड है जिसे अगले पॉइंटर का अनुसरण करके बार-बार एक्सेस किया जा सकता है, तो सूची को कहा जाता है एक चक्र है।

आमतौर पर, लिंक्ड लिस्ट का अंतिम नोड सूची के निष्कर्ष को दर्शाने के लिए एक NULL संदर्भ को संदर्भित करता है। हालाँकि, एक लूप के साथ एक लिंक की गई सूची में, सूची का अंतिम नोड एक प्रारंभ नोड, एक आंतरिक नोड या स्वयं को संदर्भित करता है। इसलिए, ऐसी परिस्थितियों में, हमें अगले नोड के संदर्भ को NULL पर सेट करके लूप को पहचानना और समाप्त करना चाहिए। लिंक की गई सूची में लूप का पता लगाने वाले भाग को इस आलेख में समझाया गया है।

सी ++ में, लिंक की गई सूची में लूप खोजने के कई तरीके हैं:

हैश टेबल-आधारित दृष्टिकोण : यह दृष्टिकोण विज़िट किए गए नोड्स के पतों को हैश तालिका में संग्रहीत करता है। लिंक की गई सूची में एक लूप मौजूद है यदि एक नोड पहले से ही हैश तालिका में मौजूद है जब इसे फिर से देखा जाता है।

फ्लोयड का चक्र दृष्टिकोण : 'कछुआ और खरगोश' एल्गोरिथ्म, जिसे आमतौर पर फ़्लॉइड के चक्र-खोज एल्गोरिथ्म के रूप में जाना जाता है: यह तकनीक दो पॉइंटर्स का उपयोग करती है, एक दूसरे की तुलना में अधिक धीमी गति से चलती है और दूसरी अधिक तेज़ी से चलती है। यदि लिंक की गई सूची में लूप है, तो लूप के अस्तित्व का खुलासा करने पर तेज़ पॉइंटर अंततः धीमे पॉइंटर से आगे निकल जाएगा।

पुनरावर्ती विधि : यह विधि बार-बार खुद को कॉल करके लिंक की गई सूची से गुजरती है। लिंक की गई सूची में एक लूप होता है यदि वर्तमान नोड पहले देखा जा चुका है।

स्टैक-आधारित दृष्टिकोण : यह दृष्टिकोण विज़िट किए गए नोड्स के पतों को स्टैक में संग्रहीत करता है। लिंक की गई सूची में एक लूप मौजूद होता है यदि एक नोड पहले से ही स्टैक में होता है जब इसे फिर से देखा जाता है।

आइए अवधारणा को समझने के लिए प्रत्येक दृष्टिकोण को विस्तार से समझाएं।

दृष्टिकोण 1: हैशसेट दृष्टिकोण

हैशिंग का उपयोग करना सबसे सीधा तरीका है। यहां, हम नोड पतों के साथ हैश तालिका रखते हुए सूची को एक-एक करके देखते हैं। इसलिए, एक लूप मौजूद है यदि हम कभी भी वर्तमान नोड के अगले पते पर दौड़ते हैं जो पहले से ही हैश तालिका में निहित है। अन्यथा, लिंक्ड लिस्ट में कोई लूप नहीं है अगर हम NULL में चलते हैं (यानी, लिंक्ड लिस्ट के अंत तक पहुँचते हैं)।

इस रणनीति को लागू करना काफी आसान होगा।

लिंक की गई सूची को पार करते समय, हम एक unordered_hashmap का उपयोग करेंगे और इसमें नोड जोड़ते रहेंगे।

अब, एक बार जब हम एक नोड भर में आते हैं जो पहले से ही मानचित्र में दिखाया गया है, तो हम जानेंगे कि हम लूप की शुरुआत में आ गए हैं।

• • इसके अलावा, हमने प्रत्येक चरण पर दो संकेत रखे, हेडनोड वर्तमान नोड की ओर इशारा करते हुए और lastNode पुनरावृत्ति करते समय, वर्तमान नोड के पूर्व नोड की ओर इशारा करते हुए।
  • जैसा हमारा हेडनोड अब लूप के स्टार्ट नोड की ओर इशारा कर रहा है और as lastNode उस नोड की ओर इशारा कर रहा था जिस पर सिर इशारा कर रहा था (यानी, यह lastNode लूप का), हमारा हेडनोड वर्तमान में लूप के प्रारंभ नोड की ओर इशारा कर रहा है।
  • एल सेट करने से लूप टूट जाएगा astNode-> अगला == न्यूल .

ऐसा करने से, लूप के शुरुआती नोड को संदर्भित करने के बजाय एंडिंग लूप नोड, NULL की ओर इशारा करना शुरू कर देता है।

हैशिंग विधि का औसत समय और स्थान जटिलता O(n) है। पाठक को हमेशा पता होना चाहिए कि प्रोग्रामिंग भाषा में अंतर्निहित हैशिंग डेटा संरचना का कार्यान्वयन हैशिंग में टकराव की स्थिति में कुल समय की जटिलता को निर्धारित करेगा।

उपरोक्त विधि (हैशसेट) के लिए सी ++ प्रोग्राम कार्यान्वयन:

आउटपुट:

कोड की चरण-दर-चरण व्याख्या नीचे दी गई है:

1. 1. बिट्स/stdc++.h> हेडर फ़ाइल, जिसमें सभी सामान्य C++ लाइब्रेरी शामिल हैं, कोड में शामिल है।
   2. 'नोड' नामक एक संरचना का निर्माण किया गया है, और इसके दो सदस्य हैं: सूची में अगले नोड का एक संदर्भ और एक पूर्णांक जिसे 'मान' कहा जाता है।
   3. इसके इनपुट के रूप में एक पूर्णांक मान और 'अगला' सूचक NULL पर सेट होने के साथ, फ़ंक्शन 'newNode' उस मान के साथ एक नया नोड बनाता है।
   4. कार्यक्रम ' फंक्शन हैश मैप' परिभाषित किया गया है, जो इनपुट के रूप में लिंक की गई सूची के प्रमुख नोड के लिए एक संकेतक लेता है।
   5. के अंदर ' functionHashMap 'फंक्शन,' हैश_मैप' नाम का एक अनऑर्डरेड_मैप बनाया गया है, जिसका उपयोग हैश मैप डेटा स्ट्रक्चर को लागू करने के लिए किया जाता है।
   6. सूची के अंतिम नोड के लिए एक सूचक को NULL में प्रारंभ किया गया है।
   7. लिंक की गई सूची को पार करने के लिए थोड़ी देर लूप का उपयोग किया जाता है, जो हेड नोड से शुरू होता है और हेड नोड न्यूल होने तक जारी रहता है।
   8. यदि वर्तमान नोड (हेडनोड) हैश मैप में पहले से मौजूद नहीं है, तो लास्टनोड पॉइंटर को लूप के अंदर वर्तमान नोड में अपडेट किया जाता है।
   9. यदि मानचित्र में वर्तमान नोड पाया जाता है, तो इसका अर्थ है कि लिंक की गई सूची में एक लूप मौजूद है। लूप को हटाने के लिए, का अगला पॉइंटर lastNode इसके लिए सेट है व्यर्थ और जबकि लूप टूट गया है।
   10. लिंक्ड लिस्ट के हेड नोड का उपयोग 'डिस्प्ले' नामक फ़ंक्शन के इनपुट के रूप में किया जाता है, जो सूची में प्रत्येक नोड के मूल्य को शुरू से अंत तक आउटपुट करता है।
   11. में मुख्य फ़ंक्शन, एक लूप बनाना।
   12. फ़ंक्शन 'फ़ंक्शन हैश मैप' को इनपुट के रूप में हेडनोड पॉइंटर के साथ कहा जाता है, जो सूची से लूप को हटा देता है।
   13. संशोधित सूची 'प्रदर्शन' फ़ंक्शन का उपयोग करके प्रदर्शित की जाती है।

दृष्टिकोण 2: फ्लोयड की साइकिल

फ्लोयड का चक्र पहचान एल्गोरिथ्म, जिसे अक्सर कछुआ और खरगोश एल्गोरिथ्म के रूप में जाना जाता है, एक लिंक की गई सूची में चक्रों का पता लगाने की इस पद्धति के लिए आधार प्रदान करता है। 'धीमा' सूचक और 'तेज़' सूचक, जो विभिन्न गति से सूची को पार करता है, इस तकनीक में उपयोग किए जाने वाले दो संकेत हैं। तेज सूचक दो कदम आगे बढ़ता है जबकि धीमा सूचक प्रत्येक पुनरावृत्ति में एक कदम आगे बढ़ता है। लिंक की गई सूची में एक चक्र मौजूद होता है यदि दो बिंदु आमने-सामने आते हैं।

1. लिंक्ड लिस्ट के हेड नोड के साथ, हम दो पॉइंटर्स को इनिशियलाइज़ करते हैं जिन्हें फास्ट और स्लो कहा जाता है।

2. अब हम लिंक की गई सूची में जाने के लिए एक लूप चलाते हैं। फास्ट पॉइंटर को प्रत्येक पुनरावृत्ति के चरण में धीमे पॉइंटर के सामने दो स्थानों पर ले जाना चाहिए।

3. लिंक की गई सूची में लूप नहीं होगा यदि फास्ट पॉइंटर सूची के अंत तक पहुंचता है (फास्टपोइंटर == न्यूल या फास्टपॉइंटर-> अगला == न्यूल)। यदि नहीं, तो तेज और धीमे संकेतक अंततः मिलेंगे, जिसका अर्थ है कि लिंक की गई सूची में एक लूप है।

उपरोक्त विधि के लिए C++ प्रोग्राम कार्यान्वयन (फ्लोयड साइकिल):

आउटपुट:

व्याख्या:

1. 1. प्रासंगिक शीर्षलेख, जैसे 'बिट्स/stdc++.h' और 'std::cout,' पहले शामिल किए गए हैं।
   2. 'नोड' संरचना, जो लिंक की गई सूची में एक नोड के लिए है, तब घोषित की जाती है। एक अगला सूचक जो सूची में निम्नलिखित नोड की ओर जाता है, प्रत्येक नोड में एक पूर्णांक डेटा फ़ील्ड के साथ शामिल किया गया है।
   3. फिर, यह 'deleteLoop' और 'detectAndDeleteLoop,' दो कार्यों को परिभाषित करता है। पहली विधि का उपयोग करके लिंक की गई सूची से एक लूप हटा दिया जाता है, और दूसरे फ़ंक्शन का उपयोग करके सूची में एक लूप का पता लगाया जाता है, जो तब लूप को हटाने के लिए पहली प्रक्रिया को कॉल करता है।
   4. मुख्य फ़ंक्शन में पांच नोड्स के साथ एक नई लिंक्ड सूची बनाई गई है, और अंतिम नोड के अगले पॉइंटर को तीसरे नोड पर सेट करके एक लूप स्थापित किया गया है।
   5. इसके बाद लिंक की गई सूची के हेड नोड को एक तर्क के रूप में पास करते हुए यह 'डिटेक्टएंडडिलीटलूप' विधि को कॉल करता है। लूप की पहचान करने के लिए, यह फ़ंक्शन 'स्लो एंड फास्ट पॉइंटर्स' दृष्टिकोण का उपयोग करता है। यह दो पॉइंटर्स को नियोजित करता है जो सूची के शीर्ष पर शुरू होते हैं, स्लोपीटीआर और फास्टपीटीआर। जबकि फास्ट पॉइंटर एक बार में दो नोड्स को स्थानांतरित करता है, धीमा पॉइंटर एक समय में केवल एक नोड को स्थानांतरित करता है। यदि सूची में एक लूप है, तो फास्ट पॉइंटर अंततः धीमे पॉइंटर से आगे निकल जाएगा, और दो बिंदु एक ही नोड पर टकराएंगे।
   6. फ़ंक्शन 'डिलीटलूप' फ़ंक्शन को आमंत्रित करता है यदि यह एक लूप पाता है, सूची के प्रमुख नोड की आपूर्ति करता है और इनपुट के रूप में धीमी और तेज़ पॉइंटर्स के चौराहे की आपूर्ति करता है। यह प्रक्रिया सूची के प्रमुख नोड के लिए दो पॉइंटर्स, ptr1 और ptr2 स्थापित करती है और लूप में नोड्स की संख्या की गणना करती है। उसके बाद, यह एक पॉइंटर k नोड्स को आगे बढ़ाता है, जहाँ k लूप में नोड्स की कुल संख्या है। फिर, जब तक वे लूप की शुरुआत में नहीं मिलते, यह एक समय में दोनों बिंदुओं को एक नोड के रूप में आगे बढ़ाता है। लूप के अंत में नोड के अगले पॉइंटर को NULL पर सेट करके लूप को तोड़ा जाता है।
   7. लूप को हटाने के बाद, यह लिंक की गई सूची को अंतिम चरण के रूप में प्रदर्शित करता है।

दृष्टिकोण 3: पुनरावर्तन

पुनरावर्तन मुद्दों को छोटे, आसान उप-समस्याओं में विभाजित करके हल करने की एक तकनीक है। सूची के अंत तक पहुँचने तक सूची में अगले नोड के लिए एक फ़ंक्शन को लगातार चलाकर एक लूप पाए जाने की स्थिति में एकल लिंक की गई सूची को पार करने के लिए पुनरावर्तन का उपयोग किया जा सकता है।

एकल रूप से लिंक की गई सूची में, एक लूप खोजने के लिए पुनरावर्तन का उपयोग करने के पीछे मूल सिद्धांत सूची के शीर्ष पर शुरू करना है, वर्तमान नोड को प्रत्येक चरण पर विज़िट के रूप में चिह्नित करना है, और फिर अगले नोड पर जाने के लिए फ़ंक्शन को फिर से शुरू करना है। वह नोड। विधि पूर्ण लिंक्ड सूची पर पुनरावृति करेगी क्योंकि इसे पुनरावर्ती कहा जाता है।

सूची में एक लूप होता है यदि एक नोड जिसे पहले विज़िट के रूप में चिह्नित किया गया है, फ़ंक्शन द्वारा सामना किया जाता है; इस मामले में, फ़ंक्शन सच हो सकता है। यदि यह किसी विज़िट किए गए नोड पर चलाए बिना सूची के अंत तक पहुँचता है, तो विधि गलत हो सकती है, जो इंगित करता है कि कोई लूप नहीं है।

यद्यपि एकल लिंक की गई सूची में एक लूप खोजने के लिए पुनरावर्तन का उपयोग करने की यह तकनीक उपयोग करने और समझने में सीधी है, यह समय और स्थान की जटिलता के मामले में सबसे प्रभावी नहीं हो सकती है।

उपरोक्त विधि (रिकर्सन) के लिए C++ प्रोग्राम कार्यान्वयन:

आउटपुट:

व्याख्या:

1. 1. कार्यक्रम डिटेक्टलूपलिंक्डलिस्ट () इस कार्यक्रम में लिंक की गई सूची के प्रमुख को इनपुट के रूप में स्वीकार करता है।
   2. लिंक की गई सूची में पुनरावृति करने के लिए फ़ंक्शन द्वारा पुनरावर्तन का उपयोग किया जाता है। पुनरावर्तन के मूल मामले के रूप में, यह निर्धारित करके शुरू होता है कि क्या वर्तमान नोड NULL है। यदि ऐसा है, तो विधि गलत हो जाती है, यह दर्शाता है कि कोई लूप मौजूद नहीं है।
   3. वर्तमान नोड की 'विज़िट की गई' संपत्ति का मान यह देखने के लिए जाँचा जाता है कि क्या यह पहले देखी गई है। यदि यह दौरा किया गया है तो यह सच हो जाता है, यह सुझाव देता है कि एक पाश पाया गया है।
   4. फ़ंक्शन वर्तमान नोड को विज़िट के रूप में चिह्नित करता है यदि इसकी 'विज़िट' प्रॉपर्टी को सही में बदलकर इसे पहले ही विज़िट किया जा चुका है।
   5. विज़िट किए गए चर के मान को यह देखने के लिए चेक किया जाता है कि वर्तमान नोड को पहले देखा गया है या नहीं। यदि इसे पहले इस्तेमाल किया गया है, तो एक लूप मौजूद होना चाहिए, और फ़ंक्शन सही हो जाता है।
   6. अंत में, फ़ंक्शन पास करके सूची में अगले नोड के साथ खुद को कॉल करता है हेडनोड-> अगला एक तर्क के रूप में। रिकर्सिवली , यह तब तक किया जाता है जब तक या तो एक लूप नहीं मिल जाता है या सभी नोड्स का दौरा नहीं किया जाता है। इसका मतलब है, फ़ंक्शन विज़िट किए गए चर को सही पर सेट करता है यदि लिंक की गई सूची में निम्नलिखित नोड के लिए पुनरावर्ती रूप से कॉल करने से पहले वर्तमान नोड का दौरा नहीं किया गया है।
   7. कोड तीन नोड्स बनाता है और उन्हें एक लिंक्ड सूची बनाने के लिए जोड़ता है मुख्य समारोह . प्रक्रिया डिटेक्टलूपलिंक्डलिस्ट () फिर सूची के प्रमुख नोड पर लागू किया जाता है। कार्यक्रम का उत्पादन ' लिंक की गई सूची में लूप काटा गया ' अगर डिटेक्टलूपलिंक्डलिस्ट () रिटर्न सच; अन्यथा, यह आउटपुट करता है ' लिंक की गई सूची में कोई लूप नहीं मिला '।
   8. कोड तब अंतिम नोड के अगले पॉइंटर को दूसरे नोड पर सेट करके लिंक की गई सूची में एक लूप सम्मिलित करता है। फिर, फ़ंक्शन के नतीजे के आधार पर, यह चलता है डिटेक्टलूपलिंक्डलिस्ट () फिर से और या तो पैदा करता है ' लिंक की गई सूची में लूप काटा गया ' या ' लिंक की गई सूची में कोई लूप नहीं मिला ।”

दृष्टिकोण 4: स्टैक का उपयोग करना

लिंक की गई सूची में लूप्स को स्टैक और 'डेप्थ-फ़र्स्ट सर्च' (DFS) विधि का उपयोग करके पाया जा सकता है। मौलिक अवधारणा लिंक की गई सूची के माध्यम से पुनरावृति करना है, प्रत्येक नोड को स्टैक पर धकेलना यदि यह पहले से ही नहीं देखा गया है। एक लूप को पहचाना जाता है यदि एक नोड जो पहले से ही ढेर पर है, फिर से सामना करना पड़ता है।

यहाँ प्रक्रिया का संक्षिप्त विवरण दिया गया है:

1. 1. विज़िट किए गए नोड्स को रिकॉर्ड करने के लिए एक खाली स्टैक और एक चर बनाएँ।
   2. लिंक की गई सूची को स्टैक पर पुश करें, शीर्ष से प्रारंभ करें। ध्यान दें कि सिर का दौरा किया गया है।
   3. सूची में अगला नोड स्टैक पर पुश करें। इस नोड में एक विज़िट मार्क जोड़ें।
   4. जैसा कि आप सूची को पार करते हैं, यह इंगित करने के लिए प्रत्येक नए नोड को स्टैक पर धकेलें कि यह दौरा किया गया है।
   5. यह देखने के लिए जांचें कि क्या कोई नोड जिसे पहले देखा जा चुका है, स्टैक के शीर्ष पर है यदि यह सामने आया है। यदि ऐसा है, तो एक लूप पाया गया है, और स्टैक में नोड्स द्वारा लूप की पहचान की जाती है।
   6. स्टैक से नोड्स को पॉप करें और कोई लूप नहीं मिलने पर सूची को ट्रेस करना जारी रखें।

उपरोक्त विधि के लिए C++ प्रोग्राम कार्यान्वयन (ढेर)

आउटपुट:

व्याख्या:

यह प्रोग्राम यह पता लगाने के लिए एक स्टैक का उपयोग करता है कि क्या एकल लिंक की गई सूची में लूप है।

• 1. इनपुट/आउटपुट स्ट्रीम लाइब्रेरी और स्टैक लाइब्रेरी दोनों पहली लाइन में मौजूद हैं।

  2. मानक नामस्थान दूसरी पंक्ति में शामिल है, जिससे हमें इनपुट/आउटपुट स्ट्रीम लाइब्रेरी के कार्यों को 'std::' के साथ उपसर्ग किए बिना एक्सेस करने की अनुमति मिलती है।

  3. निम्न पंक्ति स्ट्रक्चर नोड को परिभाषित करती है, जिसमें दो सदस्य होते हैं: एक पूर्णांक जिसे 'डेटा' कहा जाता है और एक अन्य नोड को 'अगला' कहा जाता है।

  4. लिंक की गई सूची का शीर्षक डिटेक्टलूपलिंक्डलिस्ट () विधि के लिए एक इनपुट है, जिसे अगली पंक्ति में परिभाषित किया गया है। फ़ंक्शन एक बूलियन मान उत्पन्न करता है जो इंगित करता है कि लूप मिला या नहीं।

  5. नोड पॉइंटर्स का एक स्टैक जिसे 'स्टैक' कहा जाता है और 'टेम्पनोड' नामक नोड के लिए एक पॉइंटर जिसे हेडनोड के मान के साथ आरंभ किया जाता है, दोनों को फ़ंक्शन के अंदर बनाया जाता है।

  6. फिर, जब तक कि टेम्पनोड एक अशक्त सूचक नहीं है, हम थोड़ी देर के लूप में प्रवेश करते हैं।

  (ए) स्टैक के शीर्ष तत्व को वर्तमान नोड से मेल खाना चाहिए ताकि हम यह निर्धारित कर सकें कि यह खाली नहीं है। यदि ऐसा होता है तो हम सही लौटते हैं क्योंकि एक लूप पाया गया है।

  (बी) यदि उपरोक्त स्थिति गलत है, तो वर्तमान नोड पॉइंटर को स्टैक पर धकेल दिया जाता है, और टेम्पनोड को लिंक की गई सूची में निम्नलिखित नोड पर सेट किया जाता है।

  7. हम लूप के बाद गलत लौटते हैं क्योंकि कोई लूप नहीं देखा गया था।

  8. हम तीन नोड ऑब्जेक्ट बनाते हैं और उन्हें main() फंक्शन में इनिशियलाइज़ करते हैं। चूंकि पहले उदाहरण में कोई लूप नहीं है, हम प्रत्येक नोड के 'अगले' पॉइंटर्स को ठीक से सेट करते हैं।

निष्कर्ष:

अंत में, लिंक की गई सूची में लूप का पता लगाने का सबसे अच्छा तरीका विशिष्ट उपयोग के मामले और समस्या की बाधाओं पर निर्भर करता है। हैश टेबल और फ्लोयड का चक्र-खोज एल्गोरिथ्म कुशल तरीके हैं और व्यवहार में इनका व्यापक रूप से उपयोग किया जाता है। ढेर और पुनरावर्तन कम कुशल तरीके हैं लेकिन वे अधिक सहज ज्ञान युक्त हैं।