جلسه ۸۵: عوض کردن محل دو نود در پایتون

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

جلوتر برویم و نحوه حل این مشکل را نیز بیابیم. یک راه این است که روی یک linked list حرکت کنیم و یکسری داده و اطلاعاتی مشخص، که برای جابجایی میتواند مفید باشد، ذخیره کنیم.

الگوریتم

ما میتوانیم از نود اول شروع کنیم. این نود head خواهد بود و در حرکتمان هم نود قبلی و هم نود فعلی را نیاز داریم.

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

• Node1 و node2 نودهای head نیستند.
• Node1 یا Node2 یکیشان head باشد.

پیاده‌سازی

اکنون مقداری کد مینویسیم که به ما اجازه میدهد تا روی این linked list حرکت کنیم. البته مقدار نود فعلی و قبلی را هم برای key های داده شده به متد، ذخیره میکنیم.

def swap_nodes(self, key_1, key_2):

  if key_1 == key_2:
    return 

  prev_1 = None 
  curr_1 = self.head 
  while curr_1 and curr_1.data != key_1:
    prev_1 = curr_1 
    curr_1 = curr_1.next

  prev_2 = None 
  curr_2 = self.head 
  while curr_2 and curr_2.data != key_2:
    prev_2 = curr_2 
    curr_2 = curr_2.next

  if not curr_1 or not curr_2:
    return 

  if prev_1:
    prev_1.next = curr_2
  else:
    self.head = curr_2

  if prev_2:
      prev_2.next = curr_1
  else:
      self.head = curr_1

  curr_1.next, curr_2.next = curr_2.next, curr_1.next

توضیحات: ما یک متد ساخته ایم به نام swap_nodes، که دو پارامتر key_1 و key_2 را به عنوان ورودی میگیرد. اول از همه، در خط ۳ بررسی میکنیم که این دو ورودی با هم برابر هستند یا نه. اگر برابر بودند از متد در خط ۴ خارج میشویم. در خطوط ۶ و ۷ متغیرهای prev_1 و curr_1 را را به ترتیب None و self.head قرار میدهیم. ما حلقه ای را روی linked list با استفاده از while در خط ۸ اجرا میکنیم.  این حلقه تازمانی که curr1  به انتهای لیست نرسد ویا مقدارش برابر key_1 نباشد، ادامه پیدا میکند. در حلقه while ما مقادیر prev_1 را برابر curr_1 قرار میدهیم و  curr_1 هم به نود‌بعدی نسبت میدهیم.در یک راه مشابه، بررسی میکنیم که key_2 هم در linked list وجود دارد یا نه. مقدار prev_2 را در ابتدا برابر None و مقدار curr_2 هم برابر head در linked list ثبت میکنیم. سپس دوباره اگر curr_2 مقدار None نداشته باشد و curr_2.data برابر key_2 نباشد، مقادیر prev_2 و curr_2 را در هر حرکت آپدیت میکنیم.در خطوط ۱۸ و ۹ بررسی میکنیم که حتما مقادیر مدنظر پیدا شده باشند یعنی curr_1 و curr_2 وجود دارند یا خیر. اگر در این رابطه not curr_1 یا not curr_2 مقدار true نباشد مشخص میشود که یکی از آن ها در linked list ما وجود ندارد. اگر هیچکدام یا حتی یکی فقط در linked list باشد، در این صورت نمیتوان جابجایی را انجام داد. بنابراین از متد خارج می‌شویم.دو موردی که در بالاتر در مورد الگوریتم صحبت کردیم را به یاد آورید. فرض کنید که یکی از curr_1 و curr_2 مقدارشان head نباشد. اگر هردوی نود موجود مقدار نود قبلی داشته باشد، نشان دهنده این است که آن یک نود head نیست. بنابراین بررسی میکنیم که نود قبلی در هر نود فعلی، وجود دارد یا نه. اگر وجود نداشته باشند و None باشد. آنی که مقدار نود قبلی آن None باشد، مشخص است که head است.در خط ۲۱، ما بررسی میکنیم که آیا prev_1 وجود دارد یا نه. اگر وجود داشته باشد مقدار next در prev_1 را به curr_2 تبدیل میکنیم تا بجابجایی انجام شود. همانطور که گفتیم مقدار prev_1.next به curr_1 اشاره دارد اما در خط ۲۲، ما آن را به curr_2 اشاره میدهیم. در حالت دیگر، اگر prev1 وجود نداشته باشد، مشخص کننده این است که curr_1 یک نود head است . مقدار self.head را به مقدار جدیدش یعنی curr_2 تبدیل میکنیم.مراحل بالا را در خطوط ۲۹-۲۶ برای prev_2 و curr_2 تکرار میکنیم و مقادیر مدنظر و اشاره‌گرها را آپدیت به curr_1 میکنیم.اکنون ما نود های قبلی را بررسی کردیم و آن ها را به نودهای جدید متصل کردیم. اکنون جایجایی بین مقدار next از curr_1 و مقدار next از curr_2 خواهیم داشت. در خط ۳۱ این عملیات جابجایی را به کمک پایتون انجام داده‌ایم.امیدواریم که توضیحات بالا را متوجه شده باشد. به هرحال اگر دنبال کردن کدها سخت است، شما میتوانید مقادیر curr_1 curr_2 prev_1 prev_2 را در هر حلقه print کنید تا متوجه ماجرا بشوید. اکنون ادامه میدهیم و کد زیر را میتوانید برای بررسی مشاهده کنید:

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


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

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

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def prepend(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

    def insert_after_node(self, prev_node, data):

        if not prev_node:
            print("Previous node does not exist.")
            return 

        new_node = Node(data)

        new_node.next = prev_node.next
        prev_node.next = new_node

    def delete_node(self, key):

        cur_node = self.head

        if cur_node and cur_node.data == key:
            self.head = cur_node.next
            cur_node = None
            return

        prev = None 
        while cur_node and cur_node.data != key:
            prev = cur_node
            cur_node = cur_node.next

        if cur_node is None:
            return 

        prev.next = cur_node.next
        cur_node = None

    def delete_node_at_pos(self, pos):
        if self.head:
            cur_node = self.head

            if pos == 0:
                self.head = cur_node.next
                cur_node = None
                return

            prev = None
            count = 1
            while cur_node and count != pos:
                prev = cur_node 
                cur_node = cur_node.next
                count += 1

            if cur_node is None:
                return 

            prev.next = cur_node.next
            cur_node = None

    def len_iterative(self):

        count = 0
        cur_node = self.head

        while cur_node:
            count += 1
            cur_node = cur_node.next
        return count

    def len_recursive(self, node):
        if node is None:
            return 0
        return 1 + self.len_recursive(node.next)


    def swap_nodes(self, key_1, key_2):

        if key_1 == key_2:
            return 

        prev_1 = None 
        curr_1 = self.head 
        while curr_1 and curr_1.data != key_1:
            prev_1 = curr_1 
            curr_1 = curr_1.next

        prev_2 = None 
        curr_2 = self.head 
        while curr_2 and curr_2.data != key_2:
            prev_2 = curr_2 
            curr_2 = curr_2.next

        if not curr_1 or not curr_2:
            return 

        if prev_1:
            prev_1.next = curr_2
        else:
            self.head = curr_2

        if prev_2:
            prev_2.next = curr_1
        else:
            self.head = curr_1

        curr_1.next, curr_2.next = curr_2.next, curr_1.next

        
llist = LinkedList()
llist.append("A")
llist.append("B")
llist.append("C")
llist.append("D")

print("Original List")
llist.print_list()


llist.swap_nodes("B", "C")
print("Swapping nodes B and C that are not head nodes")
llist.print_list()

llist.swap_nodes("A", "B")
print("Swapping nodes A and B where key_1 is head node")
llist.print_list()

llist.swap_nodes("D", "B")
print("Swapping nodes D and B where key_2 is head node")
llist.print_list()

llist.swap_nodes("C", "C")
print("Swapping nodes C and C where both keys are same")
llist.print_list()

این مقدار برای این درس کافیست. swap_node یک متد حساس است، چراکه نکات ریزی دارد که ممکن است خیلی واضح نباشند.امیدواریم که این مطالب برای شما مفید باشد. منتظر شما در درس بعدی هستیم.