রুবিতে ব্যবহারিক লিঙ্কড তালিকা

এটি "রুবিতে ব্যবহারিক কম্পিউটার বিজ্ঞান" সিরিজের 3য় এন্ট্রি! আজ আমরা লিঙ্ক করা তালিকা সম্পর্কে কথা বলতে যাচ্ছি।

তাহলে লিঙ্ক করা তালিকা কি?

নাম অনুসারে, একটি লিঙ্ক করা তালিকা হল একটি তালিকা বিন্যাসে ডেটা সংরক্ষণ করার একটি উপায় (ধন্যবাদ, ক্যাপ্টেন স্পষ্ট!)।

"লিঙ্ক করা" অংশটি এই সত্য থেকে আসে যে ডেটা একটি নোডে সংরক্ষণ করা হয় এবং এই নোডগুলি পরস্পরের সাথে ধারাবাহিকভাবে লিঙ্ক করা হয়।

এটি কিভাবে একটি অ্যারের থেকে আলাদা?

লিঙ্ক করা তালিকা বনাম অ্যারে

একটি সংযুক্ত তালিকার একটি অ্যারের থেকে ভিন্ন কর্মক্ষমতা বৈশিষ্ট্য আছে। এটি একটি কারণ কেন আপনি একটিকে অন্যটিকে বেছে নিতে চাইতে পারেন।

এর মানে হল যে একটি সংযুক্ত তালিকা একটি অ্যারের চেয়ে নির্দিষ্ট কাজের জন্য আরও দক্ষ হতে পারে৷

একটি লিঙ্ক করা তালিকায় কোনও সূচী নেই, কোনও এলোমেলো অ্যাক্সেস নেই, যার অর্থ হল আপনি তালিকার মাঝখানে একটি আইটেমের জন্য যোগাযোগ করতে পারবেন না .

আপনাকে তালিকার "হেড" থেকে শুরু করতে হবে এবং আপনার পছন্দসই নোডটি খুঁজে না পাওয়া পর্যন্ত বা তালিকার শেষ না হওয়া পর্যন্ত লিঙ্কগুলি অনুসরণ করতে হবে৷

লিঙ্ক করা তালিকার মাঝখানে থেকে একটি আইটেম সরানো (বা যোগ করা) অনেক দ্রুত .

আপনাকে যা করতে হবে তা হল একটি নোডের জন্য "পরবর্তী" পয়েন্টার পরিবর্তন করুন৷

কিন্তু যদি আপনি একটি অ্যারের মাঝখানে থেকে একটি উপাদান মুছে ফেলতে চান তবে আপনি একটি ফাঁক রেখে যাবেন এবং সেই ফাঁকটি বন্ধ করতে আপনাকে মুছে ফেলা উপাদানটির ডানদিকে সমস্ত উপাদান সরাতে হবে৷

খুব দক্ষ নয় যদি আপনাকে প্রায়ই এটি করতে হয়!

যদি আমরা একটি অ্যারের মাঝখানে সন্নিবেশ করতে চাই তবে একটি খালি স্থান তৈরি করতে আমাদের সমস্ত অ্যারের উপাদানগুলিকে সরাতে হবে৷

একটি কোড উদাহরণ দেখি :

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

এটি একটি মৌলিক "একক-লিঙ্কড তালিকা" বাস্তবায়ন।

আপনার কাছে অন্য ধরনের লিঙ্ক করা তালিকাও আছে :

• ডবল-লিঙ্কড তালিকা
• বৃত্তাকার লিঙ্কযুক্ত তালিকা

দ্বিগুণ-সংযুক্ত তালিকায় প্রতিটি নোডের দুটি পয়েন্টার রয়েছে:একটি পরবর্তী নোডের দিকে এবং আরেকটি আগের নোড-এ .

এটি তালিকা অনুসন্ধান করার সময় আরও নমনীয়তার অনুমতি দেয়, তবে তালিকায় পরিবর্তন করার সময় অতিরিক্ত পরিশ্রমের প্রয়োজন হয়৷

একটি বৃত্তাকার লিঙ্কযুক্ত তালিকা দ্বিগুণ লিঙ্কযুক্ত তালিকার চেয়ে একই, তবে শেষ নোডটি হেড নোডের সাথে সংযুক্ত৷

ভিডিও

সারাংশ

আপনি লিঙ্ক করা তালিকা সম্পর্কে শিখেছেন, একটি ডেটা স্ট্রাকচার যা আপনি বিবেচনা করতে পারেন যদি আপনি অ্যারের মাঝখানে অনেক উপাদান যোগ এবং অপসারণ করছেন।

এটি একটি কোডিং ইন্টারভিউতেও আসতে পারে, তাই এটি শুধুমাত্র সেই জন্য হলেও এটি শেখার উপযুক্ত৷

এই পোস্টটি শেয়ার করতে ভুলবেন না নীচের বোতামগুলি ব্যবহার করে যাতে আরও বেশি লোক এই জ্ঞান থেকে উপকৃত হতে পারে 🙂