پایتون

جلسه ۱۰۰: اضافه کردن نود قبل‌از/بعد‌از در پایتون

آرگومان های self key data به متد add_before_node داده میشود. key یک مقداریست که نودی که این مقدار را داشته باشد قبل از نود جدید ما که بر اساس ورودی data ساخته میشود، قرار خواهد گرفت. cur نیز به مقدار self.head نسبت داده میشود(خط۲). سپس ما یک حلقه while داریم در خط ۳ که در آخر در هر حلقه مقدار cur به مقدار cur.next آپدیت میشود(خط ۱۵). اینکار تا زمانی انتفاق می‌افتد که cur به None برسد. حال باید بررسی کنیم که آیا مقدار نود قبلی در cur برابر None است یا خیر. اگر این شرط برقرار بود ما متد prepend را که در درس های قبلی پیاده‌سازی کرده‌ایم، فراخوانی میکنیم. چراکه این متد یک نود جدید قبل از head ما اضافه میکند و این چیزی است که در این بخش میخواهیم. اکر خواسته باشیم یک نود جدید را قبل از نود دیگری به غیر از head اضافه کنیم، برنامه به خط ۸ میرود. اولین کاری که باید انجام دهیم ساخت یک new_node بر اساس data ورودی متد است. در خط ۹ ما مقدار prev از نود فعلی را در متغیر prev ذخیره میکنیم. اکنون نیاز داریم تا همه اشاره‌گر را برای اضافه کردن نود جدید آپدیت کنیم. بنابراین در خط ۱۰ ما مقدار next در نود prev را به new_node آپدیت کرده و باید new_node را هم قبل از cur قرار دهیم، پس مقدار cur.prev را new_node در خط ۱۱ قرار میدهیم. اکنون باید اشاره‌گر های next و prev را برای new_node هم آپدیت کنیم. مقدار next از new_node به cur در خط ۱۲ اشاره دارد و مقدار new_node.prev به prev اشاره خواهد داشت(خط ۱۳). در خط ۱۴ بعد از موفقیت آمیز بودن اضافه کردن نود، از متد خارج میشویم. این همه چیزی بود که در مورد اضافه کردن المان در یک linked list مضاعف بود. در کدهای زیر شما مثالی از استفاده‌ی این متدهای پیاده‌سازی را میبینید:

class Node:
  def __init__(self, data):
    self.data = data 
    self.next = None
    self.prev = None


class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def append(self, data):
    if self.head is None:
      new_node = Node(data)
      self.head = new_node 

    else:
      new_node = Node(data)
      cur = self.head 
      while cur.next:
          cur = cur.next 
      cur.next = new_node 
      new_node.prev = cur 

  def prepend(self, data):
    if self.head is None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    else:
        new_node = Node(data)
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

  def add_after_node(self, key, data):
    cur = self.head
    while cur:
      if cur.next is None and cur.data == key:
        self.append(data)
        return
      elif cur.data == key:
        new_node = Node(data)
        nxt = cur.next 
        cur.next = new_node
        new_node.next = nxt
        new_node.prev = cur 
        nxt.prev = new_node
        return
      cur = cur.next

  def add_before_node(self, key, data):
    cur = self.head 
    while cur:
      if cur.prev is None and cur.data == key:
        self.prepend(data)
        return
      elif cur.data == key:
        new_node = Node(data)
        prev = cur.prev
        prev.next = new_node
        cur.prev = new_node
        new_node.next = cur
        new_node.prev = prev
        return
      cur = cur.next

  def print_list(self):
    cur = self.head 
    while cur:
      print(cur.data)
      cur = cur.next


dllist = DoublyLinkedList()

dllist.prepend(0)
dllist.append(1)
dllist.append(2)
dllist.append(3)
dllist.append(4)
dllist.prepend(5)
dllist.add_after_node(3,6)
dllist.add_before_node(4,9)

dllist.print_list()

اکنون ما متدهای مختلفی از اضافه کردن المان به یک linked list مضاعف را ارائه کرده‌ایم. اکنون یاد میگیریم که چگونه میتوان المان هایی را از یک linked list مضاف حذف کرد.

در این درس یاد میگیرید که چگونه یک نود را، قبل یک نود و بعد از یک نود مشخص دیگر اضافه کنید. ابتدا مفاهیم آن را بررسی میکنیم و سپس آن را در پایتون پیاده‌سازی میکنیم. راهکار کلی برای حل این مسئله این است که روی نود ها در linked list مضاعف حرکت کنیم و دنبال key مدنظر بگردیم تا بتوانیم قبل یا بعد آن اضافه کنیم. وقتی به key مدنظر رسیدیم، اشاره‌گرها را تغییر میدهیم تا یک مکان خالی برای نود جدید بسازیم و نود جدید را بر اساس موقعیت داده شده، اضافه میکنیم.

اضافه کردن نود بعد از 

این سناریو را در دو بخش بررسی میکنیم:

  • نودی که باید بعد از آن نود جدید اضافه کنیم، آخرین نود در linked list داده شد باشد. بنابراین مقدار next برای نود جدید None  خواهد بود.

در این بخش، ما در واقع یک فراخوانی از متد append که در درس قبل گفته شد خواهیم داشت. append همه چیزی که در اینجا میخواهیم را به درستی پیاده‌سازی میکند یعنی یک نود را بعد از آخرین نود اضافه خواهد کرد.

  • نودی که باید بعد از آن نود جدید اضافه شود، آخرین نود linked list نیست.

به شکل زیر توجه کنید، نشان میدهد که چگونه میتوان این کار را در linked list داده شده انجام داد.

امیدواریم که تصاویر بالا برای فهم کار کافی باشد. اکنون سراغ کدنویسی این الگوریتم در پایتون میرویم که کدها را در باکس زیر میبینید:

def add_after_node(self, key, data):
  cur = self.head
  while cur:
    if cur.next is None and cur.data == key:
      self.append(data)
      return
    elif cur.data == key:
      new_node = Node(data)
      nxt = cur.next 
      cur.next = new_node
      new_node.next = nxt
      new_node.prev = cur 
      nxt.prev = new_node
      return
    cur = cur.next

ورودی key در متد add_after_node همان نودی است که ما میخواهیم یک نود جدید با داده data بعد از آن قرار دهیم. در خط ۲، ما مقدار cur را self.head در نظر گرفته‌ایم و به سراغ حلقه while در خط ۳ میرویم. این حلقه تازمانی که cur برابر None بشود ادامه پیدا میکند. از آنجایی که ما الگوریتم را به دو قسمت تقسیم کردیم، باید یک شرطی وجود داشته باشد که این دو مسیر را در حلقه  while از هم جدا کند. شرط موجود در خط ۴ بررسی میکند که آیا key با مقدار داده‌ی آخرین نود برابر است یعنی جایی که cur.next برابر None باشد. اگر این کار اتفاق افتاد در خط ۶ ما متد append را فراخوانی میکنیم تا داده‌جدید را به انتهای linked list اضافه کند. در حالت دیگر، اگر شرط موجود در خط ۷ برقرار باشد، مورد دوم الگوریتم باید اجرا گردد. اگر به نودی برخوردیم که باید بعد آن مقدار نود جدید را اضافه کنیم، و این نود آخرین نود linked list نباشد، برنامه به خط شماره ۸ میرود. new_node بر اساس data ای که به عنوان ورودی این متد add_after_node ساخته شده است. سپس مقدار next در cur را در یک متغیر موقت nxt ذخیره میکنیم(خط ۹). از آنجایی که میخواهیم، new_node را بعد از cur اضافه کنیم، در خط ۱۰ مقدار cur.next به نود new_node نسبت داده میشود. در خط ۱۱، مقدار new_node.next هم به nxt نسبت داده میشود. در این زمان، ما همه اشاره گر های next را تنظیم کرده ایم و باید اشاره‌گرهای prev را آپدیت کنیم. از انجایی که new_node را بعد از cur اضافه کردیم، مقدار prev در new_node به cur باید اشاره کند(خط ۱۲). nxt نیز نود بعد از new_node است پس مقدار prev در nxt را نیز به new_node آپدیت میکنیم(خط ۱۳). بعد از این مرحله ما از متد در خط ۱۴ خارج میشویم. بعد از عبارت شرطی گفته شده، مقدار cur نیز به cur.next اپدیت میشود تا بتوانیم ادامه حرکت روی linked list را داشته باشیم(خط ۱۵).

اضافه کردن نود قبل از

اکنون در این مورد صحبت مبکنیم که چگونه یک نود را قبل از نودی مشخص قرار دهیم. ما این مسئله را نیز به دو سناریو تقسیم میکنیم:

  • اضافه کردن یک نود قبل از نود head

  • اضافه کردن نود قبل از نودی که، نود head نیست.

اکنون سراغ بخش برنامه نویسی پایتون آن میرویم:

def add_before_node(self, key, data):
  cur = self.head 
  while cur:
    if cur.prev is None and cur.data == key:
      self.prepend(data)
      return
    elif cur.data == key:
      new_node = Node(data)
      prev = cur.prev
      prev.next = new_node
      cur.prev = new_node
      new_node.next = cur
      new_node.prev = prev
      return 
    cur = cur.next

آرگومان های self key data به متد add_before_node داده میشود. key یک مقداریست که نودی که این مقدار را داشته باشد قبل از نود جدید ما که بر اساس ورودی data ساخته میشود، قرار خواهد گرفت. cur نیز به مقدار self.head نسبت داده میشود(خط۲). سپس ما یک حلقه while داریم در خط ۳ که در آخر در هر حلقه مقدار cur به مقدار cur.next آپدیت میشود(خط ۱۵). اینکار تا زمانی انتفاق می‌افتد که cur به None برسد. حال باید بررسی کنیم که آیا مقدار نود قبلی در cur برابر None است یا خیر. اگر این شرط برقرار بود ما متد prepend را که در درس های قبلی پیاده‌سازی کرده‌ایم، فراخوانی میکنیم. چراکه این متد یک نود جدید قبل از head ما اضافه میکند و این چیزی است که در این بخش میخواهیم. اکر خواسته باشیم یک نود جدید را قبل از نود دیگری به غیر از head اضافه کنیم، برنامه به خط ۸ میرود. اولین کاری که باید انجام دهیم ساخت یک new_node بر اساس data ورودی متد است. در خط ۹ ما مقدار prev از نود فعلی را در متغیر prev ذخیره میکنیم. اکنون نیاز داریم تا همه اشاره‌گر را برای اضافه کردن نود جدید آپدیت کنیم. بنابراین در خط ۱۰ ما مقدار next در نود prev را به new_node آپدیت کرده و باید new_node را هم قبل از cur قرار دهیم، پس مقدار cur.prev را new_node در خط ۱۱ قرار میدهیم. اکنون باید اشاره‌گر های next و prev را برای new_node هم آپدیت کنیم. مقدار next از new_node به cur در خط ۱۲ اشاره دارد و مقدار new_node.prev به prev اشاره خواهد داشت(خط ۱۳). در خط ۱۴ بعد از موفقیت آمیز بودن اضافه کردن نود، از متد خارج میشویم. این همه چیزی بود که در مورد اضافه کردن المان در یک linked list مضاعف بود. در کدهای زیر شما مثالی از استفاده‌ی این متدهای پیاده‌سازی را میبینید:

class Node:
  def __init__(self, data):
    self.data = data 
    self.next = None
    self.prev = None


class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def append(self, data):
    if self.head is None:
      new_node = Node(data)
      self.head = new_node 

    else:
      new_node = Node(data)
      cur = self.head 
      while cur.next:
          cur = cur.next 
      cur.next = new_node 
      new_node.prev = cur 

  def prepend(self, data):
    if self.head is None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    else:
        new_node = Node(data)
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

  def add_after_node(self, key, data):
    cur = self.head
    while cur:
      if cur.next is None and cur.data == key:
        self.append(data)
        return
      elif cur.data == key:
        new_node = Node(data)
        nxt = cur.next 
        cur.next = new_node
        new_node.next = nxt
        new_node.prev = cur 
        nxt.prev = new_node
        return
      cur = cur.next

  def add_before_node(self, key, data):
    cur = self.head 
    while cur:
      if cur.prev is None and cur.data == key:
        self.prepend(data)
        return
      elif cur.data == key:
        new_node = Node(data)
        prev = cur.prev
        prev.next = new_node
        cur.prev = new_node
        new_node.next = cur
        new_node.prev = prev
        return
      cur = cur.next

  def print_list(self):
    cur = self.head 
    while cur:
      print(cur.data)
      cur = cur.next


dllist = DoublyLinkedList()

dllist.prepend(0)
dllist.append(1)
dllist.append(2)
dllist.append(3)
dllist.append(4)
dllist.prepend(5)
dllist.add_after_node(3,6)
dllist.add_before_node(4,9)

dllist.print_list()

اکنون ما متدهای مختلفی از اضافه کردن المان به یک linked list مضاعف را ارائه کرده‌ایم. اکنون یاد میگیریم که چگونه میتوان المان هایی را از یک linked list مضاف حذف کرد.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا