لیست مرتبط با روبی – انجمن DEV

فهرست مطالب

1. درک لیست های پیوندی
2. پیاده سازی لیست پیوندی در روبی

2.1. روش print_list

2.2. روش ضمیمه

2.3. روش پاپ

2.4. روش prepend

2.5. روش شیفت

2.6. روش دریافت کنید

2.7. روش set_value

2.8. روش درج

2.9. روش معکوس

درک لیست های پیوندی

لیست پیوندی مجموعه ای از گره ها است که در آن هر گره حاوی یک مقدار و ارجاع به گره بعدی در دنباله است. اولین گره سر و آخرین گره دم نامیده می شود. اشاره گره دم به nil، که انتهای لیست را نشان می دهد.

در این پست وبلاگ، پیاده سازی ساده یک لیست پیوندی در روبی را بررسی می کنیم و هر روش را همراه با پیچیدگی زمانی آن مورد بحث قرار می دهیم.

پیاده سازی لیست پیوندی در روبی

بیایید با بررسی کد روبی ارائه شده که یک لیست پیوندی را پیاده سازی می کند، شروع کنیم. این LinkedList کلاس نشان دهنده لیست پیوندی است و هر گره با Node کلاس

class LinkedList
  attr_accessor :head, :tail, :length

  def initialize(value)
    new_node = Node.new(value)
    @head = new_node
    @tail = new_node
    @length = 1
  end

  # Other methods...
end

class Node
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

• این initialize متد سازنده LinkedList کلاس و Node کلاس
• یک نمونه جدید از لیست پیوندی با مقدار اولیه و یک نمونه جدید از گره ایجاد می کند.
• هنگامی که یک گره جدید ایجاد می شود، مقدار آن مقدار ارائه شده خواهد بود و گره بعدی خواهد بود nil.
• هنگامی که یک لیست پیوندی جدید ایجاد می شود، یک شی گره جدید با مقدار داده شده ایجاد می کند.
• این گره هم به عنوان سر و هم به عنوان انتهای لیست پیوندی تنظیم می شود.
• ویژگی length به 1 مقداردهی می شود زیرا در ابتدا فقط یک گره در لیست وجود دارد.

print_list روش

روش print_list از طریق لیست پیوندی تکرار می شود و مقدار هر گره را چاپ می کند.

def print_list
  temp = head
  while temp
    puts temp.value
    temp = temp.next
  end
end

• با شروع از گره سر، روش با دنبال کردن مرجع بعدی هر گره در لیست تکرار می شود.
• مقدار هر گره را چاپ می کند و تا زمانی که به انتهای لیست برسد (زمانی که دما می شود) ادامه می دهد nil).
• پیچیدگی زمانی print_list روش O(n) است که n طول لیست پیوند شده است.
• برای چاپ ارزش هر گره باید یک بار از آن بازدید کند.

append روش

متد append یک گره جدید با مقدار داده شده در انتهای لیست پیوند شده اضافه می کند.

def append(value)
  new_node = Node.new(value)
  if @head
    @tail.next = new_node
    @tail = new_node
  else
    @tail = new_node
    @head = new_node
  end
  @length += 1
  true
end

• ابتدا یک گره جدید با مقدار ارائه شده ایجاد می شود.
• اگر لیست پیوند شده خالی نباشد ( @head گره وجود دارد)، مرجع بعدی گره دم فعلی به گره جدید تنظیم می شود و دم به گره جدید به روز می شود. به این ترتیب، گره جدید به دنباله جدید تبدیل می شود.
• اگر لیست پیوندی خالی باشد، سر و دم هر دو روی گره جدید تنظیم می شوند.
• در نهایت طول را یک بار افزایش می دهیم
• پیچیدگی زمانی append روش O(1) است زیرا تعداد ثابتی از عملیات را بدون توجه به اندازه لیست پیوند شده انجام می دهد. مستقیماً به گره دم دسترسی پیدا کرده و به روز می کند.

pop روش

متد pop آخرین گره را از لیست پیوند شده حذف و برمی گرداند.

def pop
  return if @length.zero?

  temp = @head
  pre = @head

  while temp.next
    pre = temp
    temp = temp.next
  end

  @tail = pre
  @tail.next = nil

  @length -= 1

  return temp unless @length.zero?

  @head = nil
  @tail = nil

  temp
end

• برای حذف آخرین گره، روش در لیست تکرار می شود تا زمانی که به گره دوم به آخر برسد.
• این pre متغیر گره قبلی را در حالی که temp متغیر به جلو حرکت می کند
• پس از رسیدن به آخرین گره، دم را به گره دوم به آخرین به روز می کند، ارجاع به آخرین گره را حذف می کند و طول لیست را کاهش می دهد.
• اگر لیست پس از حذف آخرین گره خالی شود، سر و دم هر دو روی تنظیم می شوند nil.
• پیچیدگی زمانی pop روش O(n) است که n طول لیست پیوند شده است.
• باید فهرست را طی کند تا به گره دوم تا آخر برای حذف برسد.

prepend روش

متد prepend یک گره جدید با مقدار داده شده در ابتدای لیست پیوند شده اضافه می کند.

def prepend(value)
  new_node = Node.new(value)
  new_node.next = @head
  @head = new_node
  @tail = new_node if @length.zero?
  @length += 1
  true
end

• ابتدا یک گره جدید با مقدار ارائه شده ایجاد می شود.
• مرجع بعدی گره جدید به گره سر فعلی تنظیم می شود.
• سپس، هد به گره جدید به روز می شود.
• اگر لیست پیوند شده در ابتدا خالی بود (طول صفر بود)، دم نیز روی گره جدید تنظیم می شود زیرا تنها گره در لیست است.
• در نهایت طول را یک بار افزایش می دهیم
• پیچیدگی زمانی prepend روش O(1) است زیرا تعداد ثابتی از عملیات را بدون توجه به اندازه لیست پیوند شده انجام می دهد.
• این به طور مستقیم به گره سر دسترسی پیدا کرده و به روز می کند.

shift روش

متد shift اولین گره را از لیست پیوند شده حذف و برمی گرداند.

def shift
  return if @length.zero?

  temp = @head
  @head = temp.next
  temp.next = nil
  @tail = nil if @length == 1
  @length -= 1
  temp
end

• این روش با به‌روزرسانی هد به گره بعدی، گره سر را حذف می‌کند.
• همچنین مرجع بعدی گره حذف شده را به روز می کند nil برای جدا کردن آن از لیست
• اگر لیست پس از حذف خالی شود (طول در ابتدا یک بود)، دم روی تنظیم می شود nil.
• در نهایت طول را یک بار کاهش می دهیم.
• پیچیدگی زمانی shift روش O(1) است زیرا تعداد ثابتی از عملیات را بدون توجه به اندازه لیست پیوند شده انجام می دهد.
• این به طور مستقیم به گره سر دسترسی پیدا کرده و به روز می کند.

get روش

متد get گره را در نمایه مشخص شده در لیست پیوند شده برمی گرداند.

def get(index)
  return if index >= @length || index.negative?

  temp = @head
  (0...index).each do |_i|
    temp = temp.next
  end
  temp
end

• روش ابتدا بررسی می کند که آیا شاخص ارائه شده معتبر است (در محدوده لیست).
• اگر شاخص معتبر نباشد (بیشتر یا مساوی طول یا منفی)، باز می گردد nil.
• در غیر این صورت، از طریق لیست تکرار می شود تا به شاخص مورد نظر برسد و گره مربوطه را برمی گرداند.
• پیچیدگی زمانی get روش O(n) است که n طول لیست پیوند شده است.
• برای رسیدن به شاخص مورد نظر باید لیست را طی کند.

set_value روش

متد set_value مقدار گره را در شاخص مشخص شده در لیست پیوند شده تنظیم می کند.

def set_value(index, value)
  temp = get(index)

  if temp
    temp.value = value
    true
  else
    false
  end
end

• روش ابتدا از get روشی برای بازیابی گره در شاخص مشخص شده.
• اگر گره وجود داشته باشد، مقدار خود را با مقدار ارائه شده به روز می کند و true را برمی گرداند.
• در غیر این صورت، false برمی گردد.
• پیچیدگی زمانی set_value روش O(n) است که n طول لیست پیوند شده است.
• از آن استفاده می کند get روشی که پیچیدگی زمانی O(n) برای بازیابی گره در شاخص مشخص شده دارد.

insert روش

متد insert یک گره جدید با مقدار داده شده در شاخص مشخص شده در لیست پیوند شده درج می کند.

def insert(index, value)
  return if index >= @length || index.negative?

  return prepend(value) if index.zero?

  return append(value) if index == @length - 1

  temp = get(index - 1)

  new_node = Node.new(value)

  new_node.next = temp.next

  temp.next = new_node
  @length += 1
  true
end

• ابتدا بررسی می کند که آیا شاخص ارائه شده معتبر است یا خیر. اگر نه، برمی گردد nil.
• اگر شاخص صفر باشد، از آن استفاده می کند prepend روش اضافه کردن گره جدید در ابتدا.
• اگر شاخص برابر با طول منهای یک باشد، از عدد استفاده می کند append روش اضافه کردن گره جدید در پایان.
• در غیر این صورت، گره را در شاخص قبلی (شاخص – 1) با استفاده از بازیابی می کند get روش.
• سپس، یک گره جدید با مقدار ارائه شده ایجاد می کند و با به روز رسانی مراجع بعدی، آن را در لیست قرار می دهد.
• در نهایت طول را یک بار افزایش می دهیم
• پیچیدگی زمانی insert روش O(n) است که n طول لیست پیوند شده است.
• از آن استفاده می کند get روشی که پیچیدگی زمانی O(n) برای بازیابی گره در شاخص مشخص شده دارد.

remove روش

متد remove گره را در فهرست مشخص شده در لیست پیوند شده حذف و برمی گرداند.

def remove(index)
  return if index >= @length || index.negative?

  return shift if index.zero?

  return pop if index == @length - 1

  prev = get(index - 1)
  temp = prev.next
  prev.next = temp.next
  temp.next = nil
  @length -= 1

  temp
end

• روش ابتدا بررسی می کند که آیا شاخص ارائه شده معتبر است یا خیر. اگر نه، برمی گردد nil.
• اگر شاخص صفر باشد، از آن استفاده می کند shift روش حذف و برگرداندن گره سر.
• اگر شاخص برابر با طول منهای یک باشد، از عدد استفاده می کند pop روش حذف و برگرداندن گره دم.
• در غیر این صورت، گره را در شاخص قبلی (شاخص – 1) با استفاده از بازیابی می کند get روش.
• مراجع بعدی را به روز می کند تا گره را در فهرست مشخص شده از لیست جدا کند.
• در نهایت طول را یک بار کاهش می دهیم.
• پیچیدگی زمانی remove روش O(n) است که n طول لیست پیوند شده است.
• از آن استفاده می کند get روشی که پیچیدگی زمانی O(n) برای بازیابی گره در شاخص مشخص شده دارد.

reverse روش

روش معکوس با تغییر ترتیب گره ها، فهرست پیوندی را معکوس می کند.

def reverse
  temp = @head
  @head = @tail
  @tail = temp
  after = temp.next
  before = nil

  (0...@length).each do |_i|
    after = temp.next
    temp.next = before
    before = temp
    temp = after
  end
end

• این روش با تعویض گره های سر و دم شروع می شود.
• سپس، از طریق لیست تکرار می شود و مراجع بعدی هر گره را معکوس می کند.
• از سه متغیر (temp، before، و after) برای پیگیری معکوس شدن گره ها.
• حلقه ادامه می یابد تا زمانی که همه گره ها معکوس شوند.
• پیچیدگی زمانی reverse روش O(n) است که n طول لیست پیوند شده است.
• برای معکوس کردن گره ها باید یک بار لیست را طی کند.