پایتون

جلسه ۹۹: append و prepend در linkedlist های doubly در پایتون

در این درس، شما یاد میگیرید که چگونه یک linked list از نوع doubly را پیاده‌سازی کنیم و المان هایی را به آن اضافه کنیم.شما با مقدمات linked list های مضاعف آشنا شده و یک پیاده‌سازی از آن را هم یاد خواهید گرفت.بعد از این مورد، بررسی میکنیم که چگونه میتوانیم متد های append (یعنی اضافه کردن یک المان به انتهای آن) و prepend (اضافه کردن المان به ابتدا)را پیاده سازی کنیم.در نهایت هم یک متد print مینویسیم تا بتوانیم متدها را ارزیابی کنیم.

همانطور که در تصویر میبینید، linked list های مضاعف خیلی شبیه linked list های singly هستند. اما با این تفاوت که که این‌ها اشاره‌گر برای نود قبلی هم دارند. در یک linked list مضاعف سه بخش زیر را در هر  نود داریم:
  • data
  • Next (اشاره به نود بعدی)
  • Prev (اشاره به نود قبلی)
همانطور که در تصویر میبینید، مقدار prev برای نود head مقدار None خواهد بود و همچنین مقدار Next برای اخرین نود هم None است.کار را با پیاده‌سازی یک 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):
        pass

    def prepend(self, data):
        pass

    def print_list(self):
        pass
ما دو کلاس در این پیاده‌سازی داریم:
  • Node
  • DoublyLinkedList
نقطه تفاوت در کلاس Node نسبت به دوبخش گذشته این است که ما یک بخش جدید در Node داریم. prev برای کلاس Node در این بخش در نظر گرفته شده است. prev به نود قبلی، در یک  linked list اشاره دارد.ما همچنین کلاس DoublyLinkedList را هم تعریف کردیم و مقدار head آن را برای شروع None در نظر گرفته ایم. در این درس سه متدی که در این کلاس مشخص شده اند را به مرور تکمیل و پیاده‌سازی میکنیم.appendابتدا پیاده‌سازی تابع append را ببینید:
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
ما دو مورد را در پیاده‌سازی append بررسی مکنیم:
  • linked list مضاعف خالی باشد.
  • linked list مضاعف خالی نباشد.
اگر linked list مضاعف خالی باشد، به عبارت دیگر self.head مقدار None داشته باشد، برنامه به خط ۳ میرود و یک نود new_node بر اساس data ورودی متد میسازد. از آنجایی که new_node تنها نود ما در linked list هست، آن را در خط ۴ به عنوان head انتخاب میکنیم.اکنون به سراغ مورد دوم میرویم. در خط ۶ ما new_node را با استفاده از تابع سازنده کلاس Node و مقدار ورودی data میسازیم. سپس برای اضافه کردن نود جدید به موقعیت مناسب آن نیاز داریم. بنابراین، مقدار cur را در خط ۷ نود head قرار میدهیم تا بتوانیم روی نود های linked list حرکت کرده تا نود آخر را هم بیابیم. این کار با استفاده از یک حلقه while که در آن cur به cur.next نسبت داده میشود انجام میگردد. این حلقه زمانی به اتمام میرسد که مقدار cur.next برابر None بشود.(خطوط ۹-۸). اگر حلقه while به اتمام رسید، ما مقدار next در cur را به new_node نسبت میدهیم(خط ۱۰). اکنون ما نود new_node را به linked list اضافه میکنیم. ما همچنین نیاز داریم که در مورد بخش prev در new_node هم بحش کنیم. که اکنون این مقدار در خط ۱۱ به cur نسبت داده میشود.

print_list

ما راهی را نیاز داریم که بتوانیم متدهایمان را ارزیابی کنیم. اینکار را با متد print_list انجام میدهیم:
def print_list(self):
  cur = self.head
  while cur:
    print(cur.data)
    cur = cur.next
متد print_list بسیار ساده است. cur را در ابتدا به self.head نسبت میدهیم(خط ۲) و سپس دیتای آن را پرینت کرده(خط ۴) مقدار آن را به cur.next آپدیت میکنیم(خط ۵) تا بتوانیم روی این نود ها حرکت کنیم.

prepend

اکنون زمان آن است که تد prepend از کلاس DoublyLinkedList را پیاده‌سازی کنیم. کد زیر را بررسی کنید:
def prepend(self, data):
  if self.head is None:
    new_node = Node(data)
    self.head = new_node
  else:
    new_node = Node(data)
    self.head.prev = new_node
    new_node.next = self.head
    self.head = new_node
کدهایی که در خطوط ۴-۲ وجود دارند مانند کدهای متد append است. اکنون به خط ۶ میرویم جایی که میدانیم linked list خالی نیست. در خط ۶، ما یک new_node با ورودی data که به این متد داده شده است، میسازیم. اکنون نیازمند آن هستیم تا آن را در ابتدای linked list قرار دهیم. از آنجایی که نود جدید را باید قبل از نود head کنونی قرار دهیم و موقعیت head را به نود جدید با این کار میدهیم و مقدار prev نود(نودی که قبلا head بوده) را به new_node نسبت میدهیم. این کار در خط ۷ انجام شده است. در خط ۸ نیز مقدار next از new_node هم به نودی که قبلا head بوده است، نسبت میدهیم یعنی تبدیل new_node.next به self.head. در نهایت در خط ۹، مقدار self.head را به new_node تبدیل میکنیم. این کارها عملیات ما را برای این متد در linked list های مضاعف انجام میدهد.در کدهای زیر شما کل پیاده‌سازی DoublyLinkedList را همراه همه متدهای تعریف شده میبینید که به همراه یک مثال نیز است.
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)
            self.head = new_node
        else:
            new_node = Node(data)
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node

    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.print_list()
در درس بعدی، ما سراغ متدهای دیگری برای اضافه کردن به linked list های مضاعف میرویم.

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

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

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

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