جلسه ۸۹: nامین عنصر مانده به اخرین نود در پایتون

در این درس یاد خواهیم گرفت که چگونه  n امین نود باقی مانده به انتهای linked list را پیدا کنیم.

اول از همه، ما مشخص میکنیم که منظور از n امین عنصر مانده به آخر، چیست:

همانطور که در تصویر بالا ملاحظه میکنید، اگر n برابر دو باشد، یعنی میخواهیم به نود دوم از انتهای linked list دسترسی پیدا کنیم.

برای حل این مسئله، دو راهکار ارائه میدهیم.

راهکار اول

این راهکار را ما به دو بخش تقسیم میکنیم:

• محاسبه طول یک linked list
• شمارش معکوس از کل طول تا اینکه به عدد n برسیم.

برای مثال، اگر ما یک linked list با اندازه ۴ داشته باشیم، از head شروع میکنیم و از مقدار طول linked list یکی یکی، طی هر حرکت، کم میکنیم تا به عدد مدنظر برسیم.

پیاده‌سازی

این راهکار را بدین صورت در پایتون پیاده‌سازی میکنیم:

def print_nth_from_last(self, n):
  total_len = self.len_iterative()
  
  cur = self.head 
  while cur:
    if total_len == n:
      print(cur.data)
      return cur.data
    total_len -= 1
    cur = cur.next
  if cur is None:
    return  

توضیحات

متد print_nth_from_last فقط یک پارامتر n را به عنوان ورودی میگیرد. از درس های قبلی شما یاد گرفته‌اید که چگونه میتوان طول یک linked list را پیدا کرد. ما از متد self.len_iterative برای محاسبه طول یک linked list و ذخیره آن در متغیر total_len در خط ۲ استفاده می‌کنیم.

تا اینجا مرحله اول از راهکار اول را پیاده‌سازی کردیم. اکنون به سراغ مرحله دوم میرویم. cur مقدار اولیه self.head در خط ۴ دارد. سپس ما یک حلقه while هم در خط ۵ تعریف میکنیم که روی linked list حرکت خواهد کرد و تا جایی که مدنظر ما هست این حرکت اتفاق می‌افتد. در بدنه while ما بررسی میکنیم که اگر total_len برابر n بشود، شرایط مدنظر ما بوجود آمده است. اگر total_len برابر n باشد، ما مقدار data از از نود فعلی یعنی cur، به عنوان خروجی این متد برمیگردانیم. در غیر اینصورت ما یکی از total_len در خط ۹ کم میکنیم، و مقدار cur را با نود بعدی آپدیت میکنیم تا حرکت روی linked list ادامه پیدا کند.

اگر به هر دلیلی به اتنهای linked list رسیدیم اما total_len هیچ وقت برابر n نشود، این موضوع را در خطوط ۱۲-۱۱ بررسی میکنیم. در این مورد، ما بررسی میکنیم که آیا cur به مقدار None رسیده‌است و در این اینصورت از متد خارج میشویم.

راهکار دوم

اینهایی که گفته شد مربوط به راهکار اول بودند. اکنون سراغ راهکار دوم میرویم، که میتواند به صورت زیر معرفی شود:

اینجا ما دو اشاره‌گر p و q داریم:

• p به نود head اشاره دارد.
• q به n نود دورتر از head مربوط است

سپس، این اشاره‌گرها را در طول linked list نود به نود جلو میبریم. زمانی که q به None برسد، بررسی میکنیم که p در کجا قرار دارد. آنجا محل نود مدنظر ما است.

پیاده‌سازی

اکنون این موضوع را با پیاده‌سازی کد زیر بررسی میکنیم:

def print_nth_from_last(self, n):
    p = self.head
    q = self.head

    if n > 0:
        count = 0
        while q:
            count += 1
            if(count>=n):
                break
            q = q.next
            
        if not q:
            print(str(n) + " is greater than the number of nodes in list.")
            return

        while p and q.next:
            p = p.next
            q = q.next
        return p.data
    else:
        return None

توضیحات

ما مقادیر پیش فرض p و q را self.head در خط ۲ و ۳ قرار میدهیم. اگر n از صفر بزرگتر نباشد، در نتیجه تایع باید مقدار None زا برگرداند، چراکه نمیتوان با آن از انتها شمارش کرد. اگر n بزرگتر از ۰ باشد، ادامه کار را انجام میدهیم.

بر اساس این الگوریتم، ما باید q را به n نود بعد از head نسبت بدهیم. بنابراین ما در خط ۶ مقدار اولیه count را ۰ در نظر گرفته و با استفاده از while در خط ۷، مقدار q را به نود بعدی(خط ۱۱) آپدیت میکنیم تا به مقدار n یا بزرگتر از آن برسد. مقدار count در هر مرحله تکرار یکی به آن اضافه میشود. همچنین حلقه while زمانی به اتمام میرسد که q به None برسد. برای بررسی این موضوع، ما یک عبارت شرطی در خط ۱۳ قرار دادیم که بررسی میکند آیا q برابر None شده است یا نه. اگر q برابر None باشد، میتوان نتیجه گرفت که که مقدار n از طول linked list داده شده بیشتر است. پس امکان پذیر نیست که به n امین نود از انتها دسترسی داشته باشیم. در این حالت از متد خارج میشویم(خط ۱۵).

اکنون به قسمت اصلی از پیاده‌سازی مان برمیگردیم. در حلقه while در خط ۱۷، ما مقدار p و q را به نود های بعدی آپدیت میکنیم. این حلقه هم زمانی به انتها میرسد که p یا q.next مقدار None داشته باشند. به عنوان نتیجه خروجی در این حالت p.data خروجی مدنظر ما به عنوان n امین نود ماقبل انتها، به خروجی تابع برمیگردانیم.

هر دو راهکار در کد زیر در کنار کلاس LinkedList پیاده‌سازی شده اند. شما میتوانید هر کدام از اینها را بر اساس اینکه ورودی تابع print_nth_from_last در بخش method یک باشد یا دو، انتخاب کنید. با تغییر دادن این کدها و تغییر نوع راهکار استفاده شده، متدهای LinkedList را ارزیابی کنید.

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

    def print_helper(self, node, name):
        if node is None:
            print(name + ": None")
        else:
            print(name + ":" + node.data)

    def reverse_iterative(self):

        prev = None 
        cur = self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            
            self.print_helper(prev, "PREV")
            self.print_helper(cur, "CUR")
            self.print_helper(nxt, "NXT")
            print("\n")

            prev = cur 
            cur = nxt 
        self.head = prev

    def reverse_recursive(self):

        def _reverse_recursive(cur, prev):
            if not cur:
                return prev

            nxt = cur.next
            cur.next = prev
            prev = cur 
            cur = nxt 
            return _reverse_recursive(cur, prev)

        self.head = _reverse_recursive(cur=self.head, prev=None)

    def merge_sorted(self, llist):
    
        p = self.head 
        q = llist.head
        s = None
    
        if not p:
            return q
        if not q:
            return p

        if p and q:
            if p.data <= q.data:
                s = p 
                p = s.next
            else:
                s = q
                q = s.next
            new_head = s 
        while p and q:
            if p.data <= q.data: s.next = p s = p p = s.next else: s.next = q s = q q = s.next if not p: s.next = q if not q: s.next = p return new_head def remove_duplicates(self): cur = self.head prev = None dup_values = dict() while cur: if cur.data in dup_values: # Remove node: prev.next = cur.next cur = None else: # Have not encountered element before. dup_values[cur.data] = 1 prev = cur cur = prev.next def print_nth_from_last(self, n, method): if method == 1: #Method 1: total_len = self.len_iterative() cur = self.head while cur: if total_len == n: #print(cur.data) return cur.data total_len -= 1 cur = cur.next if cur is None: return elif method == 2: # Method 2: p = self.head q = self.head if n > 0:
                count = 0
                while q:
                    count += 1
                    if(count>=n):
                        break
                    q = q.next
                    
                if not q:
                    print(str(n) + " is greater than the number of nodes in list.")
                    return

                while p and q.next:
                    p = p.next
                    q = q.next
                return p.data
            else:
                return None

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

print(llist.print_nth_from_last(4,1))
print(llist.print_nth_from_last(4,2))

امیدواریم که هر دو راهکار برای شما واضح و روشن بوده‌باشد. اکنون سراغ یک مسئله دیگر در singly linked list ها میرویم. البته در درس بعدی!