रूबी में लिंक्ड लिस्ट्स में महारत: एक व्यावहारिक मार्गदर्शिका

यह "रूबी में व्यावहारिक कंप्यूटर विज्ञान" श्रृंखला में तीसरी प्रविष्टि है! आज हम लिंक्ड लिस्ट के बारे में बात करने जा रहे हैं।

तो लिंक्ड लिस्ट क्या है?

नाम के अनुसार, लिंक्ड लिस्ट डेटा को सूची प्रारूप में संग्रहीत करने का एक तरीका है (धन्यवाद, कैप्टन ऑब्वियस!)।

"लिंक्ड" भाग इस तथ्य से आता है कि डेटा एक नोड में संग्रहीत होता है और ये नोड्स एक क्रमिक तरीके से एक दूसरे से जुड़े होते हैं।

यह सरणी से कैसे अलग है?

लिंक्ड लिस्ट बनाम सरणी

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

इसका मतलब है कि कुछ कार्यों के लिए लिंक्ड लिस्ट सरणी की तुलना में अधिक कुशल हो सकती है।

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

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

लिंक्ड लिस्ट के बीच से किसी आइटम को हटाना (या जोड़ना) बहुत तेज़ होता है।

आपको बस एक नोड के लिए "नेक्स्ट" पॉइंटर को बदलना होगा।

लेकिन अगर आप सरणी के बीच से किसी तत्व को हटाना चाहते हैं तो आप एक गैप छोड़ देंगे और उस गैप को बंद करने के लिए आपको हटाए गए तत्व के दाईं ओर के सभी तत्वों को स्थानांतरित करना होगा।

यदि आपको यह अक्सर करना पड़े तो यह बहुत कुशल नहीं है!

अगर हम सरणी के बीच में डालना चाहते हैं तो हमें खाली जगह बनाने के लिए सभी सरणी तत्वों को स्थानांतरित करना होगा।

आइए एक कोड उदाहरण देखें:

 a = [1,2,3,4,5,6,7,8] def insert(arr, item, pos) tmp = arr[pos] arr[pos] = item arr.replace(arr[0..pos] + [tmp] + arr[pos+1..-1]) end insert(a, 99, 3) p a 

नोट: एक बिल्ट-इन Array#insert मेथड भी है, लेकिन मैं आपको दिखाना चाहता था कि यह मेथड कैसे काम करता है।

सूची के बीच में एक आइटम डालने का प्रदर्शन प्रभाव क्या है?

यहां एक बेंचमार्क है:

 Comparison: LinkedList: 1815407.9 i/s Array: 18090.3 i/s - 100.35x slower 

यहां बड़ा अंतर है, लेकिन यह LinkedList के आकार पर भी बहुत निर्भर करता है क्योंकि हमें नोड खोजने के लिए खोजना पड़ता है।

दो डेटा संरचनाओं की तुलना करने का एक और तरीका समय जटिलता तालिका देखना है (यह मानता है कि आपको सम्मिलन और विलोपन के लिए नोड खोजने की आवश्यकता नहीं है):

वास्तविक दुनिया के अनुप्रयोगों की तलाश है?

यहां हारून पैटरसन द्वारा एक पुल रिक्वेस्ट है जहां वह लिंक्ड लिस्ट का उपयोग करके रूबी जेम्स को गति देता है:

https://github.com/rubygems/rubygems/pull/1188

लिंक्ड लिस्ट कार्यान्वयन

रूबी में LinkedList क्लास शामिल नहीं है इसलिए हमें अपना खुद का बनाना होगा।

हम निम्नलिखित ऑपरेशन उपलब्ध कराना चाहते हैं:

• append (सूची के अंत में)
• append_after
• delete
• find

यहां एक संभावित कार्यान्वयन है:

 class LinkedList def initialize @head = nil end def append(value) if @head find_tail.next = Node.new(value) else @head = Node.new(value) end end def find_tail node = @head return node if !node.next return node if !node.next while (node = node.next) end def append_after(target, value) node = find(target) return unless node old_next = node.next node.next = Node.new(value) node.next.next = old_next end def find(value) node = @head return false if !node.next return node if node.value == value while (node = node.next) return node if node.value == value end end def delete(value) if @head.value == value @head = @head.next return end node = find_before(value) node.next = node.next.next end def find_before(value) node = @head return false if !node.next return node if node.next.value == value while (node = node.next) return node if node.next && node.next.value == value end end def print node = @head puts node while (node = node.next) puts node end end end 

यह विशेष कार्यान्वयन टेल को ट्रैक नहीं रखता, यह एक नया आइटम जोड़ते समय टेल को ढूंढता है। यह append ऑपरेशन को रैखिक समय (O(n)) बनाता है। नीचे दिए गए वीडियो में मैं आपको एक और कार्यान्वयन दिखाता हूं जहां मैं तत्वों को सामने जोड़ता हूं।

और यहां हमारी नोड क्लास है:

 class Node attr_accessor :next attr_reader :value def initialize(value) @value = value @next = nil end def to_s "Node with value: #{@value}" end end 

हम इसका उपयोग इस तरह कर सकते हैं:

 list = LinkedList.new list.append(10) list.append(20) list.append(30) list.append_after(10, 15) list.append_after(20, 25) list.print 

यह एक बुनियादी "सिंगली-लिंक्ड लिस्ट" कार्यान्वयन है।

आपके पास लिंक्ड लिस्ट के अन्य प्रकार भी हैं:

• डब्ली-लिंक्ड लिस्ट
• सर्कुलर लिंक्ड लिस्ट

डब्ली-लिंक्ड लिस्ट में हर नोड के दो पॉइंटर्स होते हैं: एक अगले नोड के लिए और दूसरा पिछले नोड के लिए।

यह सूची खोजते समय अधिक लचीलापन देता है, लेकिन सूची में बदलाव करते समय अतिरिक्त काम भी करना पड़ता है।

एक सर्कुलर लिंक्ड लिस्ट डब्ली-लिंक्ड लिस्ट के समान ही होती है, लेकिन अंतिम नोड हेड नोड से जुड़ा होता है।

वीडियो

सारांश

आपने लिंक्ड लिस्ट्स के बारे में सीखा, एक डेटा संरचना जिस पर आप विचार कर सकते हैं यदि आप सरणी के बीच में बहुत सारे तत्व जोड़ और हटा रहे हैं।

यह कोडिंग इंटरव्यू में भी आ सकता है, इसलिए यह सीखने लायक है भले ही सिर्फ उसके लिए ही हो।

नीचे दिए गए बटनों का उपयोग करके इस पोस्ट को शेयर करना न भूलें ताकि अधिक लोग इस ज्ञान से लाभ उठा सकें 🙂