جلسه ۸۳: حذف براساس موقعیت در پایتون

در این درس یاد میگیریم که چگونه میتوانیم یک نود را بر اساس یک موقعیت داده شده، حذف کنیم. ما این مسئله را در یک مسیری مشابه مسیری که در درس قبلی انجام دادیم، حل خواهیم کرد.

مواردی که باید بررسی شوند

دوباره ما دو مورد زیر را برای پیاده‌سازی جداگانه بررسی میکنیم.

• حذف یک نود در موقعیت ۰
• حذف یک نود که در موقعیت ۰ نباشد.

پیاده‌سازی

بدون هیچ زحمتی سراغ پیاده‌سازی میرویم.

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 = 0
    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

توضیحات

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

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 = 0
            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


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

llist.delete_node_at_pos(0)

llist.print_list()

این ها همه روش‌های حذف نود ها در یک singly linked list بود. در درس بعدی یاد میگیریم که چگونه طول یک linked list را بیابیم.