پایتون

جلسه ۸۴: طول linked list در پایتون

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

الگوریتم

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

پیاده‌سازی تکراری

الگوریتمی که در بالا صحبت شد، به ما کمک میکند تا روش تکراری را برای محاسبه طول یک linked list استفاده کنیم. اکنون کار را ادامه میدهیم و یک متد len_iterative را میسازیم.

def len_iterative(self):
    count = 0
    cur_node = self.head
    while cur_node:
        count += 1
        cur_node = cur_node.next
    return count 

این متد اگر درون کلاس تنظیم شود ورودی self خواهد داشت. ما از ابتدای یک linked list شروع میکنیم و  ما مقدار cur_node را برابر head آن linked list در خط ۳ قرار میدهیم. سپس روی نود ها حرکت میکنیم تا به None برسیم، که در اینصورت حلقه while در خط ۴ به اتمام میرسد. در این مسیر ما یک شمارنده ای به نام count داریم که تعداد نود ها را نیز میشمارد. دقت شود که، در خط ۲ این متغیر count ابتدا ۰ در نظر گرفته شده‌است. این شمارش تازمانی که cur_node به None برسد ادامه پیدا میکند(۵). اکنون کار را ادامه میدهیم و کد زیر را بررسی میکنیم:

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):

        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


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


print(llist.len_iterative())

در کد بالا یک شی linked list داریم با نام llist و ۴ عضو را به آن اضافه کرده‌ایم(خطوط ۱۰۳-۱۰۰). عبارتی که در خط ۱۰۶ وجود دارد به ما خروجی ۴ میدهد که نشان دهنده‌، درست بودن پیاده‌سازی ما هست.

پیاده‌سازی بازگشتی

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

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

در پیاده‌سازی len_recursice ما یک نود را به متد میدهیم. اکنون اگر بخواهیم طول یک linked list را محاسبه کنیم، باید مقدار شروع linked list را به عنوان پارامتر این متد در خط ۱ بدهیم. در خط ۴ یک فراخوانی بازگشتی از این متد داریم که node.next را به آن میدهیم. اکنون، اگر یک تابع بازگشتی داشته باشیم، ما به حالت پایه نیاز داریم. برای متد len_recursive، حالت پایه ممکن است انتهای linked list باشد. اگر به انتهای یک linked list برسیم، node مقدار  None دارد و سپس در خط ۳ مقدار صفر را به عنوان خروجی میدهیم. اگر هم none نبود، در خط ۴ دوباره این تابع را با ورودی next نود فعلی فراخونی میکنیم. همچنین در خط ۴ مقدار ۱ را به علاوه داده‌ای که خروجی میدهد میکنیم. اکنون این متد را در یک روش شبیه روش تکراری فراخوانی میکنیم. اما نودی که مربوط به head در این linked list است را به آن متد میدهیم.

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)


llist = LinkedList()
print("The length of an empty linked list is:")
print(llist.len_recursive(llist.head))
llist.append("A")
llist.append("B")
llist.append("C")
llist.append("D")

print("The length of the linked list calculated recursively after inserting 4 elements is:")
print(llist.len_recursive(llist.head))
print("The length of the linked list calculated iteratively after inserting 4 elements is:")
print(llist.len_iterative())

همانطور که از کدهای بالا میبینید، خروجی ۴ را دوباره دریافت کردیم اما این بار با متد len_recursive. اگر linked list ورودی خالی باشد مقدار صفر به عنوان خروجی به ما میدهد. در نتیجه، اهمیتی ندارد که طول یک linked list را به صورت تکراری یا بازگشتی محاسبه کنیم، همیشه یک جواب یکسان خواهیم داشت. امیدوارم که شما از این درس لذت برده باشید. در درس بعدی، یاد میگیریم که چگونه جای دو نود را با هم عوض کنیم!

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

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

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

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