दैनिक कोडिंग समस्या: एक बार में लिंक की गई सूची से k-वें इंडेक्स को हटा दें

एक बार में लिंक्ड सूची से k-th इंडेक्स हटाना

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

शुरू करने से पहले, सामान्य अस्वीकरण:

• ये समस्याएँ अद्भुत न्यूज़लेटर डेली कोडिंग प्रॉब्लम द्वारा प्रदान की जाती हैं, जिसकी आप सदस्यता ले सकते हैं यहाँ . इसे जांचें, और अपनी चुनौतियों को भी हल करने का प्रयास करें!

• मैं कोई विशेषज्ञ प्रोग्रामर नहीं हूं: बस एक व्यक्ति हूं जो अपने शॉट्स साझा करना पसंद करता है! यदि आपके पास किसी एल्गोरिदम के लिए बेहतर या तेज़ समाधान है, तो कृपया इसे टिप्पणियों में सबमिट करें! मुझे इसके बारे में कुछ और जानना अच्छा लगेगा!

  
  

बहुत हो गया शोर; चलिए समस्या पर आते हैं!

यह समस्या शुरुआत में अमेज़न द्वारा पूछी गई थी

एक लिंक की गई सूची और पूर्णांक k देखते हुए, सूची के अंत से k-वें नोड को हटा दें और सूची का शीर्ष वापस कर दें।

k सूची की लंबाई से छोटा होने की गारंटी है।

इसे एक बार में करें.

ठीक है, आइए थोड़ा समझाएं कि यहां क्या हो रहा है: हमें सूची से हटाने के लिए एक लिंक की गई सूची और एक इंडेक्स तत्व k दिया गया है। उसके बाद, हमें लिंक की गई सूची का शीर्ष वापस कर देना चाहिए।

अंत में, हमें यह सब केवल एक बार में करना होगा, जिसका अर्थ है कि हम सूची को एक से अधिक बार लूप नहीं कर सकते हैं।

हमें यह भी गारंटी दी जाती है कि सूचकांक k सूची में समाहित है, इसलिए हमें सूची की वास्तविक लंबाई से आगे जाने के लिए इसकी जांच करने की आवश्यकता नहीं है।

हम आज एल्गोरिदम बनाने के लिए गो का उपयोग करेंगे क्योंकि इसका सिंटैक्स इस तरह के काम के लिए अद्भुत है, और साथ ही, इसे समझना काफी सरल है।

आइए शुरुआत से शुरू करें: एक सरल लिंक्ड सूची बनाना।

लिंक्ड सूची

लिंक की गई सूची के पीछे की अवधारणा बहुत सरल है: यह ऑब्जेक्ट्स (आमतौर पर नोड्स कहा जाता है) से बनी एक सूची है, और प्रत्येक नोड में कम से कम दो गुण होने चाहिए: एक मान (वास्तव में नोड द्वारा निहित कुछ) और अगले नोड के लिए एक लिंक ।

आमतौर पर, एक पॉइंटर का उपयोग एक नोड से दूसरे नोड पर जाने के लिए लिंक के रूप में किया जाता है।

साथ ही, सूची के पहले नोड को आमतौर पर सूची का प्रमुख कहा जाता है, जो वह नोड भी है जिसे समस्या द्वारा हमें वापस लौटने के लिए कहा जाता है।

यहाँ एक ग्राफिकल उदाहरण है:

बाईं ओर पहला नोड सूची का प्रमुख है, जिसमें इसका मान v₀ और एक मेमोरी पॉइंटर P(n₁) होता है जो सूची को अगले नोड n₁ पर रीडायरेक्ट करता है। निम्नलिखित नोड n₁ में इसका मान और अगले नोड के लिए एक सूचक P(n₂) होगा, इत्यादि।

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

आइए एक बनाने के लिए कोड देखें!

कोड बहुत सरल है: हम दो संरचनाएँ बनाते हैं, एक आंतरिक नोड के लिए और एक लिंक की गई सूची के लिए।

• नोड, जैसा कि हमने अभी देखा है, में दो गुण होंगे, अर्थात् संपत्ति Value और संपत्ति Next , जो अगले नोड के सूचक के रूप में *Node प्रकार रखता है।

• लिंक की गई सूची, लिंक की गई सूची को "प्रारंभिक" करने के लिए एक संरचना है, जिसमें केवल एक संपत्ति होगी, सूची का Head ।

  
  

उसके बाद, हम बस मुख्य फ़ंक्शन में सूची को प्रारंभ करते हैं और उसके शीर्ष को 10 के यादृच्छिक मान के साथ एक नोड देते हैं।

लिंक की गई सूची को समझने के पीछे कुंजी यह है कि अब हेड नोड, चूंकि Node प्रकार का है , Head स्वाभाविक रूप से एक Next संपत्ति होगी , जिसमें अगला नोड होगा। इस अंतिम नोड के पास अगले नोड पर कूदने के लिए उसकी Next संपत्ति होगी, इत्यादि।

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

नोड्स जोड़ना: भेष में परिवर्तनीय सूची

भले ही आपके पास प्रोग्रामिंग का बहुत कम अनुभव हो, लगभग हर प्रोग्रामिंग भाषा में, पहली अवधारणाओं में से एक जिसके बारे में आपने सुना होगा वह परिवर्तनशील और अपरिवर्तनीय सूचियों के बीच का अंतर है।

जैसा कि उनके नाम से पता चलता है, परिवर्तनशील सूचियाँ वे सूचियाँ हैं जिनमें आप हेरफेर कर सकते हैं और तत्वों को जोड़ सकते हैं । इसके बजाय, अपरिवर्तनीय वस्तुओं का एक निश्चित आकार होता है और उन्हें नए तत्वों के साथ नहीं जोड़ा जा सकता है । परन्तु ऐसा क्यों?

अपरिवर्तनीय सूचियाँ मेमोरी में सन्निहित होती हैं, जिसका अर्थ है कि उनके तत्व मेमोरी में क्रमिक रूप से संग्रहीत होते हैं: 3 तत्वों की सूची के लिए, यदि पहला तत्व 0x00 पर संग्रहीत है, तो दूसरा 0x01 पर और अंतिम 0x02 पर संग्रहीत होगा।

यही कारण है कि पायथन में एक निश्चित सरणी, एक अपरिवर्तनीय सूची, या टुपल पर पुनरावृति करना इतना तेज़ है क्योंकि सीपीयू केवल मेमोरी इंडेक्स को एक-एक करके याद करता है।

दूसरी ओर, परिवर्तनीय सूचियाँ केवल पहली बार आरंभ होने पर ही स्मृति में सन्निहित होती हैं: उस बिंदु पर, यदि तत्व जोड़े जाते हैं, तो वे अब अनुक्रमिक नहीं रहेंगे। तो हम उन पर कैसे लूप कर सकते हैं?

ठीक है, क्योंकि पहले आरंभ के अंतिम तत्व में एक संकेतक होगा कि उसके बाद जोड़ा गया तत्व , जो हमें जोड़े गए तत्व में लाएगा, इत्यादि। तो हाँ, परिवर्तनशील सूचियाँ वास्तव में अक्सर भेष में जुड़ी हुई सूचियाँ होती हैं!

अब, आइए कोड देखें:

हमने अपनी लिंक की गई सूची के तरीकों में AddNode विधि जोड़ी है। नोड जोड़ने की प्रक्रिया इस प्रकार है:

• सबसे पहले, हम Head वैल्यू को करंट नामक current में संग्रहीत करते हैं

• इसके बाद, हम हर बार अगले नोड के साथ current वैरिएबल को अपडेट करते हुए लिंक की गई सूची पर लूप करते हैं, जब तक कि अगला नोड शून्य न हो जाए। एक बार जिस नोड पर हम वर्तमान में हैं, उसमें एक शून्य सूचक होता है, हम जानते हैं कि हम सूची के अंतिम नोड पर हैं।

• अंत में, हम इस अंतिम नोड को एक नए नोड और एक नए मान के साथ अपडेट करते हैं (यदि हम इसे खाली छोड़ देते हैं तो इस नए नोड का Next पॉइंटर शून्य के रूप में सेट हो जाएगा)

  
  

ग्राफ़िक रूप से, यह प्रक्रिया कुछ इस प्रकार है:

हम लिंक की गई सूची में नोड्स के मानों को प्रिंट करके मुख्य फ़ंक्शन में इस विधि की सही कार्यप्रणाली की जांच कर सकते हैं।

नोड को हटाना

अब अंतिम भाग और हमारी समस्या के समाधान के लिए: सही सूचकांक के साथ एक नोड को हटाना। सबसे पहले, किसी लिंक की गई सूची से किसी नोड को हटाने का क्या मतलब है? यदि हम इसके बारे में सोचें, तो लिंक की गई सूची में एक नोड केवल तभी मौजूद होता है जब वह पिछले नोड से जुड़ा हो , है ना?

उदाहरण के लिए, यदि हम n-1ᵗʰ को null का Next मान देते हैं, तो हम सूची से nᵗʰ मान को अलग कर सकते हैं।

यदि जिस तत्व को हम हटाना चाहते हैं वह अंतिम नहीं है तो क्या होगा? खैर, हम पिछले तत्व को अगले वाले से जोड़कर तत्व को अनलिंक कर सकते हैं!

इसलिए kᵗʰ तत्व को हटाने के लिए, हमें k-1ᵗʰ तत्व ढूंढना होगा और इसे k+1ᵗʰ नोड से जोड़ना होगा। हमें पिछले नोड (k-1ᵗʰ) को स्टोर करने की आवश्यकता होगी।

जाहिर है, हम सीधे सूची को अनुक्रमित नहीं कर सकते हैं : linkedlist[n] जैसा कुछ प्रयास करें, बस एक त्रुटि उत्पन्न होगी। हालाँकि, इसे देखते हुए, हम सूची के शीर्ष को सूचकांक 0 और उसके अगले नोड को सूचकांक 1 के रूप में मान सकते हैं, और इसी तरह, और हम नोड्स पर लूप भी कर सकते हैं, जैसा कि हमने पहले किया है।

फिर हम जो कर सकते हैं वह उस नोड पर नज़र रखने के लिए एक काउंटर लागू करना है जिस पर हम हैं!

चलिए फिर इसे कोड करते हैं।

आइए RemoveNode फ़ंक्शन को देखें जो एक index विशेषता स्वीकार करता है। उसके बाद, हम तीन वेरिएबल प्रारंभ करते हैं:

• previousNode , जो पिछले नोड को धारण करेगा

• current , जो लूप के दौरान उस नोड को होल्ड करेगा जिस पर हम हैं

• counter , प्रारंभ में 0 के बराबर है, जो सूची में हमारी स्थिति बनाए रखेगा

  
  

आइए फिलहाल पहले if ब्लॉक को छोड़ दें और इसके बजाय लूप पर ध्यान केंद्रित करें। हम तब तक लूप करना शुरू करते हैं जब तक कि हमारा counter वैरिएबल हमारे index से बिल्कुल छोटा न हो जाए: प्रत्येक लूप तब पिछले नोड को वर्तमान नोड के साथ अपडेट करेगा और वर्तमान नोड और काउंटर को अपडेट करने के लिए आगे बढ़ेगा।

जब लूप टूट जाता है, तो इसका मतलब है कि हम अपने वांछित सूचकांक से ठीक पहले नोड पर हैं: हमें बस पिछले नोड के पॉइंटर को अपडेट करना होगा, prev.Next , इस सूची में अगले नोड के साथ हम जिस पर हैं, current.Next होगा.अगला . अंत में, हम लिंक की गई सूची का शीर्ष लौटाते हैं।

अब क्या होता है यदि हटाया जाने वाला सूचकांक शीर्ष है, जिसका सूचकांक 0 है? लूप कभी भी शुरू नहीं होगा क्योंकि यह counter = 0 और index = 0 से शुरू होगा, और स्थिति तुरंत झूठी होगी। हम इस पहले मामले को शीर्ष पर if ब्लॉक के साथ प्रबंधित कर सकते हैं।

मूल रूप से, यदि सूचकांक 0 है, तो हम सीधे लिंक की गई सूची के शीर्ष को उसके आगे के नोड के साथ अपडेट कर सकते हैं, और इसे वापस कर सकते हैं। मैं आपका ध्यान आकर्षित करना चाहता हूं, विशेष रूप से पंक्ति 31 पर: गो, कई अन्य भाषाओं की तरह, फ़ंक्शन के गुणों को मान के आधार पर पास करता है , जिसका अर्थ है कि फ़ंक्शन पास किए गए ऑब्जेक्ट की एक प्रति रखता है, न कि उस वास्तविक ऑब्जेक्ट की जिसे आप पास कर रहे हैं .

इस अवधारणा को इस उदाहरण में स्पष्ट रूप से देखा जा सकता है:

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

हम एक विशेषता के रूप में पारित मूल्य के मेमोरी पते को प्रिंट करने के लिए एक फ़ंक्शन बनाते हैं। फिर, मुख्य फ़ंक्शन में, हम एक वेरिएबल a बनाते हैं और उसका मेमोरी एड्रेस प्रिंट करते हैं। फिर हम उसी वेरिएबल को फ़ंक्शन में पास करते हैं और उसका मेमोरी एड्रेस प्रिंट करते हैं।

जैसा कि आप देख सकते हैं, यदि आप प्रयास करते हैं, तो परिणाम अलग-अलग होंगे: ऐसा इसलिए है क्योंकि विशेषताओं को फ़ंक्शन में मान के रूप में पास किया जाता है, जिसका अर्थ है कि a की एक प्रति केवल फ़ंक्शन में पास करने के उद्देश्य से बनाई गई है।

अपनी लिंक की गई सूची पर वापस, हमें उपरोक्त समस्या का वास्तविक समाधान पाने के लिए पॉइंटर्स का उपयोग करना चाहिए। तो "वास्तविक" ll.Node तक पहुंचने के लिए हमें इसके सूचक, *ll.Node याद रखना होगा और इसे *ll.Node = *ll.Node.Next के साथ आगे बढ़ाना होगा ।

मुख्य फ़ंक्शन में, हम विधि में कॉल जोड़ते हैं, उदाहरण के लिए, ll.RemoveNode(0) और ll.RemoveNode(2) को कॉल करते हुए, और हम परिणाम की जांच कर सकते हैं जहां नोड 0 और नोड 2 गायब होंगे।

निष्कर्ष

हमने इसे अंत तक बना लिया है!

यदि आपने यहां तक पढ़ा है, तो मेरा पूरा आभार आपके प्रति है। यदि आप एक या दो लाइक छोड़ना और लेख साझा करना चाहते हैं, तो यह मेरा दिन बना देगा और मुझे ये लेख लिखना जारी रखने में मदद मिलेगी!

अगले लेख में मिलते हैं, और, हमेशा की तरह, पढ़ने के लिए धन्यवाद।

निकॉला