پایتون

جلسه ۸۸: حرف کپی‌ها در Linked list در پایتون

در این درس، یاد میگیریم که چگونه کپی ها را از یک linked list حذف کنیم. در این درس، ما با استفاده از جداول Hash همه المان های کپی را در یک single linked list حذف میکنیم. اگر به عنوان مثال single linked list شما به صورت زیر باشد:

۱ - ۶ - ۱ - ۴ - ۲ - ۲ - ۴

در نتیجه انجام این عملیات،  linked list زیر را برای ما به وجود میاورد:

۱ - ۶ - ۴ - ۲

اکنون در مثال زیر مفاهیم حدف المان های کپی را، تصویری ببینید:

الگوریتم

راهکار کلی برای حل این مسئله این است که یک بار روی یک linked list حرکت کنیم و تمام داده‌هایی که در یک نود وجود دارد را بررسی و ردیابی کنیم. میتوانیم از جداول hash یا دیکشنری ها برای شمارش داده‌های المان ها استفاده کنیم. به عنوان مثال، اگر داده ۶ را بشماریم، ما آن را به دیکشنری یا جدول hash اضافه میکنیم و جلو میرویم. اگر در ادامه به ۶ دیگری برخوردیم، آن را در دیکشنری یا حدول Hash بررسی میکنیم، که در اینصورت متوجه میشویم که یک ۶ در جدول وجود دارد، پس این نود کپی است و باید حذف گردد.

پیاده‌سازی

اکنون کد زیر را برای راهکار بالا، ارائه میدهیم و بررسی میکنیم:

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

توضیحات

در متد remove_duplicates، ما اول از همه دو متغیر میسازیم، یکی cur و یکی هم prev و به آن ها ترتیب مقدار اولیه self.head و None میدهیم. در خط ۴، یک دیکشنری میسازیم و اسم آن را dup_values می‌نامیم. اکنون باید به کمک یک حلقه while در خط ۶ روی این linked list حرکت کنیم. همانطور که دیدید، این حلقه تا زمانی که به مقدار None برسیم ادامه پیدا میکند. سپس بررسی میکنیم که آیا cur.data در dup_values وجود دارد یا نه. اول بررسی میکنیم که اگر وجود نداشت به بخش else (خط ۱۸)در این شرط میرویم و یک المان جدید در دیکشنری با مقدار key برابر cur.data  و با مقدار ۱ میسازیم(خط ۱۳). همچنین در خط ۱۴، باید مقدار prev را با cur آپدیت کنیم. حال حالتی را بررسی میکنیم که cur.data در دیکشنری dup_values وجود داشته باشد، اینجا زمانیست که ما یک مقدار کپی را پیدا کرده‌ایم. اکنون باید این بخش کپی را از linked list حذف کنیم. برای اینکار مقدار prev.next را به cur.next (خط ۹) نسبت میدهیم(point). در ادامه برای حذف کامل cur آن را برابر با None در خط ۱۰ قرار میدهیم. در خط ۱۵ ما مقدار cur را prev.next قرار میدهیم تا به  حرکت روی linked list ادامه دهیم. ما متد remove_duplicates را ساختیم، اکنون آن را به کلاس 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)

    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

llist = LinkedList()
llist.append(1)
llist.append(6)
llist.append(1)
llist.append(4)
llist.append(2)
llist.append(2)
llist.append(4)

print("Original Linked List")
llist.print_list()
print("Linked List After Removing Duplicates")
llist.remove_duplicates()
llist.print_list()

امیدواریم راهکاری که در این درس ارائه شد را یاد گرفته باشید. منتظر شما همچنان در درس بعدی هستیم!

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

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

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

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