جلسه ۸۹: 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
ها میرویم. البته در درس بعدی!