डेटा संरचना और एल्गोरिदम - लिंक की गई सूची

एक लिंक की गई सूची डेटा संरचनाओं का एक अनुक्रम है, जो लिंक के माध्यम से एक साथ जुड़े हुए हैं।

लिंक की गई सूची उन लिंक का एक क्रम है जिसमें आइटम शामिल हैं। प्रत्येक लिंक में दूसरे लिंक का कनेक्शन होता है। लिंक की गई सूची सरणी के बाद दूसरी सबसे अधिक उपयोग की जाने वाली डेटा संरचना है। लिंक्ड लिस्ट की अवधारणा को समझने के लिए महत्वपूर्ण शर्तें निम्नलिखित हैं।

  • Link - लिंक की गई सूची के प्रत्येक लिंक में एक तत्व नामक एक डेटा संग्रहीत किया जा सकता है।

  • Next - लिंक्ड लिस्ट के प्रत्येक लिंक में नेक्सट नामक अगली लिंक का लिंक होता है।

  • LinkedList - एक लिंक्ड लिस्ट में पहले नाम की पहली लिंक का कनेक्शन होता है।

लिंक्ड सूची प्रतिनिधित्व

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

उपरोक्त उदाहरण के अनुसार, निम्नलिखित महत्वपूर्ण बिंदुओं पर विचार किया जाना है।

  • लिंक्ड लिस्ट में एक लिंक एलिमेंट होता है जिसे पहले कहा जाता है।

  • प्रत्येक लिंक एक डेटा फ़ील्ड (ओं) को ले जाता है और एक लिंक फ़ील्ड जिसे अगला कहा जाता है।

  • प्रत्येक लिंक अपने अगले लिंक का उपयोग करके अपने अगले लिंक के साथ जुड़ा हुआ है।

  • अंतिम लिंक सूची के अंत को चिह्नित करने के लिए अशक्त के रूप में एक लिंक करता है।

लिंक्ड सूची के प्रकार

लिंक की गई सूची के विभिन्न प्रकार निम्नलिखित हैं।

  • Simple Linked List - आइटम नेविगेशन केवल आगे है।

  • Doubly Linked List - आइटम को आगे और पीछे नेविगेट किया जा सकता है।

  • Circular Linked List - अंतिम आइटम में पहले तत्व का लिंक होता है और अगले तत्व में पिछले तत्व का लिंक होता है।

मूलभूत क्रियाएं

एक सूची द्वारा समर्थित मूल संचालन निम्नलिखित हैं।

  • Insertion - सूची की शुरुआत में एक तत्व जोड़ता है।

  • Deletion - सूची की शुरुआत में एक तत्व को हटाता है।

  • Display - पूरी सूची प्रदर्शित करता है।

  • Search - दिए गए कुंजी का उपयोग करके एक तत्व खोजता है।

  • Delete - दिए गए कुंजी का उपयोग करके एक तत्व को हटाता है।

निवेशन ऑपरेशन

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

कल्पना कीजिए कि हम एक नोड सम्मिलित कर रहे हैं B (न्यूनोड), के बीच A (वामनोड) और C(RightNode)। फिर B.next to C - को इंगित करें।

NewNode.next −> RightNode;

यह इस तरह दिखना चाहिए -

अब, बाईं ओर अगला नोड नए नोड को इंगित करना चाहिए।

LeftNode.next −> NewNode;

यह दोनों के बीच में नया नोड रखेगा। नई सूची इस तरह दिखनी चाहिए -

यदि सूची की शुरुआत में नोड डाला जा रहा है तो इसी तरह के कदम उठाए जाने चाहिए। इसे अंत में सम्मिलित करते समय, सूची के दूसरे अंतिम नोड को नए नोड को इंगित करना चाहिए और नया नोड NULL को इंगित करेगा।

विलोपन ऑपरेशन

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

लक्ष्य नोड के बाएं (पिछले) नोड को अब लक्ष्य नोड के अगले नोड को इंगित करना चाहिए -

LeftNode.next −> TargetNode.next;

यह उस लिंक को हटा देगा जो लक्ष्य नोड को इंगित कर रहा था। अब, निम्न कोड का उपयोग करते हुए, हम उस लक्ष्य नोड को हटा देंगे जो इंगित कर रहा है।

TargetNode.next −> NULL;

हमें हटाए गए नोड का उपयोग करने की आवश्यकता है। हम इसे स्मृति में रख सकते हैं अन्यथा हम केवल मेमोरी को हटा सकते हैं और लक्ष्य नोड को पूरी तरह से मिटा सकते हैं।

रिवर्स ऑपरेशन

यह ऑपरेशन एक संपूर्ण है। हमें अंतिम नोड को हेड नोड द्वारा इंगित करने और संपूर्ण लिंक की गई सूची को उलटने की आवश्यकता है।

सबसे पहले, हम सूची के अंत तक चलते हैं। यह NULL को इंगित होना चाहिए। अब, हम इसे इसके पिछले नोड की ओर इंगित करेंगे -

हमें यह सुनिश्चित करना होगा कि अंतिम नोड अंतिम नोड नहीं है। तो हमारे पास कुछ अस्थायी नोड होंगे, जो अंतिम नोड की ओर इशारा करते हुए सिर के नोड की तरह दिखता है। अब, हम सभी बाईं ओर के नोड्स को उनके पिछले नोड्स को एक-एक करके इंगित करेंगे।

हेड नोड द्वारा इंगित नोड (पहला नोड) को छोड़कर, सभी नोड्स को अपने पूर्ववर्ती को इंगित करना चाहिए, जिससे उन्हें अपना नया उत्तराधिकारी बनाया जा सके। पहला नोड NULL को इंगित करेगा।

हम अस्थायी नोड का उपयोग करके हेड नोड बिंदु को नए पहले नोड में बनाएंगे।

लिंक की गई सूची अब उलट है। सी प्रोग्रामिंग भाषा में लिंक्ड सूची कार्यान्वयन को देखने के लिए, कृपया यहां क्लिक करें ।