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

एक बार में लिंक्ड सूची से k-th इंडेक्स हटाना एक और समस्या के समाधान के साथ आपका पुनः स्वागत है! आज, हम लिंक्ड सूचियों और उनके तत्वों को हटाने से निपट रहे हैं। हम इस बारे में थोड़ी चर्चा करेंगे कि लिंक की गई सूचियाँ क्या हैं, हम एक बनाएंगे, और देखेंगे कि इसमें से तत्वों को कैसे हटाया जाए। शुरू करने से पहले, सामान्य अस्वीकरण: ये समस्याएँ अद्भुत न्यूज़लेटर डेली कोडिंग प्रॉब्लम द्वारा प्रदान की जाती हैं, जिसकी आप सदस्यता ले सकते हैं . इसे जांचें, और अपनी चुनौतियों को भी हल करने का प्रयास करें! यहाँ मैं कोई विशेषज्ञ प्रोग्रामर नहीं हूं: बस एक व्यक्ति हूं जो अपने शॉट्स साझा करना पसंद करता है! यदि आपके पास किसी एल्गोरिदम के लिए बेहतर या तेज़ समाधान है, तो कृपया इसे टिप्पणियों में सबमिट करें! मुझे इसके बारे में कुछ और जानना अच्छा लगेगा! बहुत हो गया शोर; चलिए समस्या पर आते हैं! यह समस्या शुरुआत में अमेज़न द्वारा पूछी गई थी देखते हुए, सूची के अंत से k-वें नोड को हटा दें और सूची का शीर्ष वापस कर दें। एक लिंक की गई सूची और पूर्णांक k सूची की लंबाई से छोटा होने की गारंटी है। k इसे एक बार में करें. ठीक है, आइए थोड़ा समझाएं कि यहां क्या हो रहा है: हमें सूची से हटाने के लिए एक लिंक की गई सूची और एक इंडेक्स तत्व दिया गया है। उसके बाद, हमें लिंक की गई सूची का शीर्ष वापस कर देना चाहिए। k अंत में, हमें यह सब केवल एक बार में करना होगा, जिसका अर्थ है कि हम सूची को एक से अधिक बार लूप नहीं कर सकते हैं। हमें यह भी गारंटी दी जाती है कि सूचकांक सूची में है, इसलिए हमें सूची की वास्तविक लंबाई से आगे जाने के लिए इसकी जांच करने की आवश्यकता नहीं है। k समाहित हम आज एल्गोरिदम बनाने के लिए गो का उपयोग करेंगे क्योंकि इसका सिंटैक्स इस तरह के काम के लिए अद्भुत है, और साथ ही, इसे समझना काफी सरल है। आइए शुरुआत से शुरू करें: एक सरल लिंक्ड सूची बनाना। लिंक्ड सूची लिंक की गई सूची के पीछे की अवधारणा बहुत सरल है: यह ऑब्जेक्ट्स (आमतौर पर कहा जाता है) से बनी एक सूची है, और प्रत्येक नोड में कम से कम दो गुण होने चाहिए: एक (वास्तव में नोड द्वारा निहित कुछ) और अगले नोड के लिए एक । नोड्स मान लिंक आमतौर पर, एक उपयोग एक नोड से दूसरे नोड पर जाने के लिए लिंक के रूप में किया जाता है। पॉइंटर का साथ ही, सूची के पहले नोड को आमतौर पर सूची का कहा जाता है, जो वह नोड भी है जिसे समस्या द्वारा हमें वापस लौटने के लिए कहा जाता है। प्रमुख यहाँ एक ग्राफिकल उदाहरण है: बाईं ओर पहला नोड सूची का प्रमुख है, जिसमें इसका मान v₀ और एक मेमोरी पॉइंटर होता है जो सूची को अगले नोड निम्नलिखित नोड में इसका मान और अगले नोड के लिए एक सूचक होगा, इत्यादि। P(n₁) n₁ पर रीडायरेक्ट करता है। n₁ P(n₂) निस्संदेह, अंतिम नोड के पास इंगित करने के लिए कुछ भी नहीं होगा, इसलिए इसके सूचक का मान होगा। शून्य आइए एक बनाने के लिए कोड देखें! https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true कोड बहुत सरल है: हम दो संरचनाएँ बनाते हैं, एक आंतरिक नोड के लिए और एक लिंक की गई सूची के लिए। नोड, जैसा कि हमने अभी देखा है, में दो गुण होंगे, अर्थात् संपत्ति और संपत्ति , जो अगले नोड के सूचक के रूप में प्रकार रखता है। Value Next *Node लिंक की गई सूची, लिंक की गई सूची को "प्रारंभिक" करने के लिए एक संरचना है, जिसमें केवल एक संपत्ति होगी, सूची का । Head उसके बाद, हम बस मुख्य फ़ंक्शन में सूची को प्रारंभ करते हैं और उसके शीर्ष को 10 के यादृच्छिक मान के साथ एक नोड देते हैं। लिंक की गई सूची को समझने के पीछे कुंजी यह है कि अब नोड, चूंकि , स्वाभाविक रूप से एक , जिसमें अगला नोड होगा। इस अंतिम नोड के पास अगले नोड पर कूदने के लिए उसकी संपत्ति होगी, इत्यादि। हेड Node प्रकार का है Head Next संपत्ति होगी Next एक बार जब हम सूची में कुछ नोड्स जोड़ देंगे तो सब कुछ अधिक स्पष्ट हो जाएगा, तो चलिए इसे करते हैं! हमारे पास दो विकल्प हैं: या तो हम इसे मैन्युअल रूप से करें, यह कठिन काम है, या हम कुछ और नोड्स जोड़ने के लिए लिंक की गई सूची वर्ग के लिए एक विधि लिखते हैं। चलो पता करते हैं! वास्तव में नोड्स जोड़ना: भेष में परिवर्तनीय सूची भले ही आपके पास प्रोग्रामिंग का बहुत कम अनुभव हो, लगभग हर प्रोग्रामिंग भाषा में, पहली अवधारणाओं में से एक जिसके बारे में आपने सुना होगा वह और सूचियों के बीच का अंतर है। परिवर्तनशील अपरिवर्तनीय जैसा कि उनके नाम से पता चलता है, । इसके बजाय, अपरिवर्तनीय वस्तुओं का एक । परन्तु ऐसा क्यों? परिवर्तनशील सूचियाँ वे सूचियाँ हैं जिनमें आप हेरफेर कर सकते हैं और तत्वों को जोड़ सकते हैं निश्चित आकार होता है और उन्हें नए तत्वों के साथ नहीं जोड़ा जा सकता है अपरिवर्तनीय सूचियाँ हैं, जिसका अर्थ है कि उनके तत्व हैं: 3 तत्वों की सूची के लिए, यदि पहला तत्व 0x00 पर संग्रहीत है, तो दूसरा 0x01 पर और अंतिम 0x02 पर संग्रहीत होगा। मेमोरी में सन्निहित होती मेमोरी में क्रमिक रूप से संग्रहीत होते यही कारण है कि पायथन में एक निश्चित सरणी, एक अपरिवर्तनीय सूची, या टुपल पर पुनरावृति करना इतना तेज़ है क्योंकि सीपीयू केवल मेमोरी इंडेक्स को एक-एक करके याद करता है। दूसरी ओर, परिवर्तनीय सूचियाँ केवल पहली बार आरंभ होने पर ही स्मृति में सन्निहित होती हैं: उस बिंदु पर, यदि तत्व जोड़े जाते हैं, तो वे अब अनुक्रमिक नहीं रहेंगे। तो हम उन पर कैसे लूप कर सकते हैं? , जो हमें जोड़े गए तत्व में लाएगा, इत्यादि। ठीक है, क्योंकि पहले आरंभ के अंतिम तत्व में एक संकेतक होगा कि उसके बाद जोड़ा गया तत्व तो हाँ, परिवर्तनशील सूचियाँ वास्तव में अक्सर भेष में जुड़ी हुई सूचियाँ होती हैं! अब, आइए कोड देखें: https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true हमने अपनी लिंक की गई सूची के तरीकों में विधि जोड़ी है। नोड जोड़ने की प्रक्रिया इस प्रकार है: AddNode सबसे पहले, हम वैल्यू को करंट नामक में संग्रहीत करते हैं Head current इसके बाद, हम हर बार अगले नोड के साथ वैरिएबल को अपडेट करते हुए लिंक की गई सूची पर लूप करते हैं, जब तक कि अगला नोड शून्य न हो जाए। current एक बार जिस नोड पर हम वर्तमान में हैं, उसमें एक शून्य सूचक होता है, हम जानते हैं कि हम सूची के अंतिम नोड पर हैं। अंत में, हम इस अंतिम नोड को एक नए नोड और एक नए मान के साथ अपडेट करते हैं (यदि हम इसे खाली छोड़ देते हैं तो इस नए नोड का पॉइंटर शून्य के रूप में सेट हो जाएगा) Next ग्राफ़िक रूप से, यह प्रक्रिया कुछ इस प्रकार है: हम लिंक की गई सूची में नोड्स के मानों को प्रिंट करके मुख्य फ़ंक्शन में इस विधि की सही कार्यप्रणाली की जांच कर सकते हैं। नोड को हटाना अब अंतिम भाग और हमारी समस्या के समाधान के लिए: सही सूचकांक के साथ एक नोड को हटाना। सबसे पहले, किसी लिंक की गई सूची से किसी नोड को हटाने का क्या मतलब है? यदि हम इसके बारे में सोचें, , है ना? तो लिंक की गई सूची में एक नोड केवल तभी मौजूद होता है जब वह पिछले नोड से जुड़ा हो उदाहरण के लिए, यदि हम n-1ᵗʰ को null का मान देते हैं, तो हम सूची से nᵗʰ मान को अलग कर सकते हैं। Next यदि जिस तत्व को हम हटाना चाहते हैं वह अंतिम नहीं है तो क्या होगा? खैर, हम सकते हैं! पिछले तत्व को अगले वाले से जोड़कर तत्व को अनलिंक कर इसलिए kᵗʰ तत्व को हटाने के लिए, हमें k-1ᵗʰ तत्व ढूंढना होगा और इसे k+1ᵗʰ नोड से जोड़ना होगा। हमें स्टोर करने की आवश्यकता होगी। पिछले नोड (k-1ᵗʰ) को जाहिर है, : जैसा कुछ प्रयास करें, बस एक त्रुटि उत्पन्न होगी। हालाँकि, इसे देखते हुए, हम सूची के शीर्ष को सूचकांक 0 और उसके अगले नोड को सूचकांक 1 के रूप में मान सकते हैं, और इसी तरह, और हम नोड्स पर लूप भी कर सकते हैं, जैसा कि हमने पहले किया है। हम सीधे सूची को अनुक्रमित नहीं कर सकते हैं linkedlist[n] फिर हम जो कर सकते हैं वह उस नोड पर नज़र रखने के लिए एक लागू करना है जिस पर हम हैं! काउंटर चलिए फिर इसे कोड करते हैं। https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true आइए फ़ंक्शन को देखें जो एक विशेषता स्वीकार करता है। उसके बाद, हम तीन वेरिएबल प्रारंभ करते हैं: RemoveNode index , जो पिछले नोड को धारण करेगा previousNode , जो लूप के दौरान उस नोड को होल्ड करेगा जिस पर हम हैं current , प्रारंभ में 0 के बराबर है, जो सूची में हमारी स्थिति बनाए रखेगा counter आइए फिलहाल पहले if ब्लॉक को छोड़ दें और इसके बजाय लूप पर ध्यान केंद्रित करें। हम तब तक लूप करना शुरू करते हैं जब तक कि हमारा वैरिएबल हमारे से बिल्कुल छोटा न हो जाए: प्रत्येक लूप तब counter index पिछले नोड को वर्तमान नोड के साथ अपडेट करेगा और वर्तमान नोड और काउंटर को अपडेट करने के लिए आगे बढ़ेगा। इसका मतलब है कि जब लूप टूट जाता है, तो हम अपने वांछित सूचकांक से ठीक पहले नोड पर हैं: हमें बस पिछले नोड के पॉइंटर को अपडेट करना होगा, prev.Next , इस सूची में अगले नोड के साथ हम जिस पर हैं, current.Next होगा.अगला . अंत में, हम लिंक की गई सूची का शीर्ष लौटाते हैं। अब क्या होता है यदि हटाया जाने वाला सूचकांक शीर्ष है, जिसका सूचकांक 0 है? लूप कभी भी शुरू नहीं होगा क्योंकि यह और से शुरू होगा, और स्थिति तुरंत झूठी होगी। हम इस पहले मामले को शीर्ष पर if ब्लॉक के साथ प्रबंधित कर सकते हैं। counter = 0 index = 0 मूल रूप से, यदि सूचकांक 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 । मुख्य फ़ंक्शन में, हम विधि में कॉल जोड़ते हैं, उदाहरण के लिए, और को कॉल करते हुए, और हम परिणाम की जांच कर सकते हैं जहां नोड 0 और नोड 2 गायब होंगे। ll.RemoveNode(0) ll.RemoveNode(2) निष्कर्ष हमने इसे अंत तक बना लिया है! यदि आपने यहां तक पढ़ा है, तो मेरा पूरा आभार आपके प्रति है। यदि आप एक या दो लाइक छोड़ना और लेख साझा करना चाहते हैं, तो यह मेरा दिन बना देगा और मुझे ये लेख लिखना जारी रखने में मदद मिलेगी! अगले लेख में मिलते हैं, और, हमेशा की तरह, पढ़ने के लिए धन्यवाद। निकॉला