پایتون

جلسه ۹۵: حذف node در پایتون

در این درس یاد خواهید گرفت که چگونه میتوان در پایتون یک نود را در یک linked list حلقوی حذف کرد.باید یک فرضیه را قبل از شروع به پیاده‌سازی در نظر بگیرید.
  • تکرار نود ها فقط یکبار است این یعنی اینکه هیچ نود تکراری و کپی در linked list، وجود ندارد.
این به این دلیل است که کدی که ما مینویسیم فقط اولین نودی که برابر دیتای مدنظر هست، حذف میگردد.

پیاده‌سازی

کارمان را با پیاده‌سازی کدهای این متد ادامه میدهیم:
def remove(self, key):
  if self.head:
    if self.head.data == key:
      cur = self.head 
      while cur.next != self.head:
        cur = cur.next 
      if self.head == self.head.next:
        self.head = None
      else:
        cur.next = self.head.next
        self.head = self.head.next
    else:
      cur = self.head 
      prev = None 
      while cur.next != self.head:
        prev = cur 
        cur = cur.next
        if cur.data == key:
          prev.next = cur.next 
          cur = cur.next

توضیحات

کدهای ما به دو بخش تقسیم میشوند. یک بخش زمانی است که نودی که باید حذف گردد خود یک head است و حالت دیگر نودی که head نخواهد بود.شرطی که در خط ۲ وجود دارد اگر False بشود، نشان دهنده این است که با یک linked list خالی طرف هستیم و از متد در این شرایط خارج میشویم. در حالت دیگر شرط، به خط ۳ میرویم.اکر قرار باشد که یک نود head را حذف کنیم، در اینصورت شرط موجود در خط ۳، True خواهد شد و ادامه مسیر در خط ۴ خواهد بود. در اینجا مقدار cur را به self.head نسبت میدهیم. برای حذف نود head، ما باید نودی که head به آن اشاره دارد و نودی که به head اشاره دارد را آپدیت کنیم. برای اینکار، ما یک حلقه while در خط ۵ داریم که فقط  زمانی اجرا میگردد که cur.next به self.head اشاره کند. در هر حلقه ما cur را به cur.next در خط ۶ آپدیت میکنیم. بعد از اینکه while به اتمام برسد، cur در نود انتهایی خواهد بود و به head اشاره میکند.در این زمان، باید این را هم در نظر بگیریم که self.head تنها المان موجود در linked list باشد. اگر این تنها المان باشد، self.head به خودش اشاره میکند. بنابراین در خط ۷ این موضوع را بررسی میکنیم و در صورت وجود این شرایط، مقدار self.head را None خواهیم کرد. در حالت دیگر، اگر تنها المان موجود نباشد و المان های دیگری هم وجود داشته باشد که بتوان با head جایگزین شود، در این صورت cur.next را برابر self.head.next در خط ۱۰ قرار میدهیم. ما در واقع نودی که قبلا به head اشاره داشت را اپدیت میکنیم. در خط بعدی نیز مقدار self.headرا به self.head.next آپدیت میکنیم که با این کار head قبلی به طور کامل از بین خواهد رفت.اکنون در خط ۱۲ به بخش دیگر ماجرا، یعنی موردی که ما قرار است نودی که head نیست را حذف کنیم، میپردازیم. برای حرکت کردن روی نود و همچنین ذخیره داشتن نود فعلی و قبلی، ما مقدار cur را self.head تنظیم میکنیم و مقدار prev را None(خطوط ۱۴-۱۳). در خطوط ۱۶ و ۱۷، ما مقدار prev را به cur آپدیت کرده و مقدار cur را هم به cur.next آپدیت میکنیم تا عملیات حرکت روی نود‌های Linked list انجام شود. سپس با استفاده از عبارت شرطی خط ۱۸، بررسی میکنیم که  این نودی فعلی، همان نود مدنظر ما است یا نه. اگر نودی که باید حذف گردد پیدا شود، مقدار next از نود قبلی یعنی prev.next را به مقدار cur.next نسبت میدهیم.(خط۱۹) و سپس مقدار cur را به cur.next تغییر میدهیم(خط ۲۰) تا روی نود ها در ادامه حرکت کند.کدهای زیر پیاده‌سازی کل این متد در کلاس linked listحلقوی ،ساخته شده در درس‌های قبلی، است.
class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None


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

    def prepend(self, data):
        new_node = Node(data)
        cur = self.head 
        new_node.next = self.head

        if not self.head:
            new_node.next = new_node
        else:
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
        self.head = new_node

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
        else:
            new_node = Node(data)
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
            new_node.next = self.head

    def print_list(self):
        cur = self.head 

        while cur:
            print(cur.data)
            cur = cur.next
            if cur == self.head:
                break

    def remove(self, key):
        if self.head:
            if self.head.data == key:
                cur = self.head 
                while cur.next != self.head:
                    cur = cur.next 
                if self.head == self.head.next:
                    self.head = None
                else:
                    cur.next = self.head.next
                    self.head = self.head.next
            else:
                cur = self.head 
                prev = None 
                while cur.next != self.head:
                    prev = cur 
                    cur = cur.next
                    if cur.data == key:
                        prev.next = cur.next 
                        cur = cur.next


cllist = CircularLinkedList()
cllist.append("A")
cllist.append("B")
cllist.append("C")
cllist.append("D")

cllist.remove("A")
cllist.remove("C")
cllist.print_list()
در درس بعدی شما با یک مسئله دیگر که مربوط به linked list های حلقوی است، آشنا میشوید.

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

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

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

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