रूबी में प्रैक्टिकल लिंक्ड लिस्ट

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

तो लिंक की गई सूची क्या है?

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

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

यह एक सरणी से किस प्रकार भिन्न है?

लिंक्ड लिस्ट बनाम ऐरे

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

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

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

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

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

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

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

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

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

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

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

नोट :एक अंतर्निहित ऐरे#इन्सर्ट विधि भी है, लेकिन मैं आपको यह दिखाना चाहता था कि यह विधि कैसे काम करती है।

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

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

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

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

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

वास्तविक दुनिया के एप्लिकेशन खोज रहे हैं?

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

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

लिंक्ड सूची कार्यान्वयन

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

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

• जोड़ें (सूची के अंत में)
• परिशिष्ट_बाद
• हटाएं
• ढूंढें

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

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

यह विशेष कार्यान्वयन पूंछ का ट्रैक नहीं रखता है, यह एक नई वस्तु को जोड़ते समय पूंछ ढूंढता है। यह एपेंड ऑपरेशन को रैखिक समय बनाता है (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

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

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

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

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

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

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

वीडियो

सारांश

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

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

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