جلسه ۹۶: تقسیم یک linked list به دو قسمت در پایتون

در این درس، شما یاد خواهید گرفت که چگونه یک linked list حلقوی را به دو قسمت تقسیم کنید.اول از همه باید مشخص شود که منظور ما از این کار دقیقا چه است.  برای شروع به اسلایدهای زیر توجه کنید:

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

()__len__

اکنون ببینیم که چگونه میتوان طول این linked list حلقوی را در پایتون محاسبه کرد:

def __len__(self):
  cur = self.head
  count = 0
  while cur:
    count += 1
    cur = cur.next
    if cur == self.head:
      break
  return count

توضیحات

متد __len__ با دو underline قبل و بعد از کلمه len تعریف شده است. این کار برای override شدن len برای کلاس linked list ما است.محاسبه طول یک linked list حلقوی به سادگی است. یک cur با مقدار اولیه self.head در خط ۲ تعریف کرده‌ایم تا نقطه شروع ما برای محاسبه باشد. مقدار count هم ۰ در نظر گرفته‌ایم(خط ۳). سپس روی این linked list حلقوی حرکت میکنیم این کار با استفاده از یک حلقه while که در خط ۴ تعریف شده‌است و در هر تکرار مقدار cur به مقدار cur.next نسبت داده میشود(خط ۶)، انجام می‌شود. در خط ۵ ما مقدار count را هم یکی افزایش میدهیم، این افزایش برای شمارش کردن تعداد نودهاییست که در linked list وجود دارد. در خطوط ۷ و ۸ اگر مقدار cur برابر self.head بشود، ما از حلقه خارج میشویم. و درنهایت در خط ۹ تعداد شمارش شده به عنوان خروجی این متد برگردانده میشود.همانطور که دیدید پیاده‌سازی متد طول به سادگی بود. اکنون سراغ متد split_list میرویم.

پیاده‌سازی

def split_list(self):
    size = len(self)    

    if size == 0:
        return None
    if size == 1:
        return self.head

    mid = size//2
    count = 0

    prev = None
    cur = self.head

    while cur and count < mid:
        count += 1
        prev = cur
        cur = cur.next
    prev.next = self.head 

    split_cllist = CircularLinkedList()
    while cur.next != self.head:
        split_cllist.append(cur.data)
        cur = cur.next
    split_cllist.append(cur.data)

    self.print_list()
    print("\n")
    split_cllist.print_list()

توضیحات

وقتی ما نقطه وسط را به کمک متد len محاسبه کردیم. ما روی نود های linked list حرکت میکنیم تا به نقطه مرکزی برسیم و سپس اشاره گر ها را تغییر میدهیم تا به دو linked list جدا در اینجا برسیم. در خط ۲، ما متد len را فراخوانی کرده ایم، که همانطور که دیدید طول یک linked list حلقوی را که این متد روی آن اجرا شده است، محاسبه میکند و مقدار خروجی آن را در متغیر size ذخیره میکنیم.سپس، یک عبارت شرطی داریم  که در خطوط ۷-۴ دو مورد را بررسی میکند. اگر size مقدار ۰ داشته باشد خروجی متد none خواهد شد و اگر size برابر یک شود، خروجی همان self.head فقط خواهد بود، چراکه در آن linked list فقط یک نود داریم. این دو مورد مشخص میکند که ما در این linked list  نمیتوانیم، تقسیم کنیم.در خط ۹، ما نقطه وسط را با تقسیم کردن طول بر ۲ و گرد سازی آن، می‌یابیم. این کار توسط عملگر // انجام میشود.اکنون سراغ بررسی قطعه کد زیر میرویم:

    count = 0

    prev = None
    cur = self.head

    while cur and count < mid:
        count += 1
        prev = cur
        cur = cur.next
    prev.next = self.head 

مقدار count در اینجا ۰ در نظر گرفته ایم(خط ۱۰). در خط ۱۲ و ۱۳ دو اشاره گر prev و cur با مقادیر اولیه None و self.head تعریف کرده ایم. این متغیرها در حین حرکت روی linked list مقادیر نود فعلی و نود قبلی را ذخیره میکنند. با استفاده از حلقه while ما روی linked list حرکت میکنیم تا زمانی که مقدار count برابر mid یا هم cur به None برسد. مقدار prev برابر با cur شده و خود cur هم به cur.next آپدیت میشود (خطوط ۱۸-۱۷). همچنین ما مقداز count را در خط ۱۶ یکی افزایش میدهیم تا به نقطه mid مدنظر برسیم. اینجا نقطه ‌ای است که میخواهیم عمل تقسیم انجام شود. برای تکمیل این تقسیم در linked list اول، مقدار prev.next را به self.head تغییر میدهیم تا بخش اول نیز به صورت linked list حلقوی تبدیل شود. در این نقطه ما قسمت اول از دو قسمت را پیدا کردیم، و نود اول برای قسمت دوم نیز اکنون در متغیر cur ذخیره شده است. اکنون به بخش زیر که مربوط به قسمت دوم linked list است توجه کنید.

split_cllist = CircularLinkedList()
    while cur.next != self.head:
        split_cllist.append(cur.data)
        cur = cur.next
    split_cllist.append(cur.data)

ما مقدار split_cllist را در خط ۲۱ به صورت خالی در نظر میگیریم. سپس روی نودهای linked list اصلی حرکت میکنیم تا به آخرین نود linked list اصلی برسیم که این نود به head اصلی هم اشاره دارد. در هر تکرار حلقه، ما cur.data را به linked list جدید(split_cllist) در خط ۲۳ اضافه میکنیم و مقدار cur را به cur.next آپدیت میکنیم تا به نود بعدی برود. درنهایت وقتی به انتهای linked list اصلی رسیدیم یعنی زمانی که cur.next برابر self.head بشود، از حلقه خارج میشویم و  cur را به split_cllist اضافه میکنیم. متد append که قبلا پیاده‌سازی کرده بودیم همه عملیات های اضافه کردن نود‌ها به linked list جدید، را بر عهده دارد. در نهایت ما قسمت بعدی از این تقسیم را هم خواهیم داشت.در خطوط ۲۹-۲۷، ما هردو linked list را پرینت کرده‌ایم تا نسخه قسمت شده linked list اصلی را ببینید.امیدواریم که این پیاده‌سازی برای شما قابل فهم و آسان بوده‌باشد.کد زیر یک پیاده‌سازی کامل به همراه یک مثال است که شما میتوانید این پیاده‌سازی را ارزیابی کنید و نمونه‌هایی دیگری را هم برای تست به آن اضافه کنید. به عنوان مثال این پیاده‌سازی را برای 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 __len__(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
            if cur == self.head:
                break
        return count

    def split_list(self):
        size = len(self)    

        if size == 0:
            return None
        if size == 1:
            return self.head

        mid = size//2
        count = 0

        prev = None
        cur = self.head

        while cur and count < mid: count += 1 prev = cur cur = cur.next prev.next = self.head split_cllist = CircularLinkedList() while cur.next != self.head: split_cllist.append(cur.data) cur = cur.next split_cllist.append(cur.data) self.print_list() print("\n") split_cllist.print_list() # A -> B -> C -> D -> ...
# A -> B -> ... and C -> D -> ...

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

cllist.split_list()

در درس بعدی نگاهی به مسئله Josephus می‌انداریم.