پایتون

جلسه ۹۴:مقدمات و اضافه کردن در یک linked list حلقوی در پایتون

شما در این درس با linked list های حلقوی آشنا میشوید و یاد میگیرید که چگونه المان هایی را به این نوع linked list اضافه کنید.

مقدمه

اول از همه بررسی کنیم که linked list های حلقوی چه هستند. اینها خیلی شبیه به singly linked list ها هستند بجز اینکه آخرین نود به جای اینکه به None متصل باشد. به اولین نود متصل است. تصویر زیر به شما کمک میکند تا این نوع linked list ها را بهتر بشناسید:

همانطور که در تصویر بالا ملاحظه میکنید، linked list های حلقوی نود هایی همانند singly linked list ها دارند. نام حلقوی به این دلیل است که، آخرین نود به head اشاره دارد در حالی که در نوع قبلی به None اشاره داشت. اکنون آن را در پایتون پیاده‌سازی میکنیم:

class Node:
    def __init__(self, data):
      self.data = data
      self.next = None


class CircularLinkedList:
    def __init__(self):
      self.head = None 

    def prepend(self, data):
      pass

    def append(self, data):
      pass

    def print_list(self):
      pass

کلاس Node همانند قبلی است. همچنین تابع سازنده CircularLinedList مانند تابع سازنده LinkedList است. اما متدهای prepend append و print_list متفاوت است.

append

اضافه کردن یک نود به linked list حلقوی یعنی اینکه یک نود را بعد از نودی در linked list که به head اشاره دارد، اضافه میکنیم. اکنون به کد زیر توجه کنید که یک پیاده‌سازی از متد append است.

def append(self, data):
  if not self.head:
      self.head = Node(data)
      self.head.next = self.head
  else:
      new_node = Node(data)
      cur = self.head
      while cur.next != self.head:
          cur = cur.next
      cur.next = new_node
      new_node.next = self.head

یک موضوع این است که linked list ما خالی باشد. در این حالت، ما یک نود جدید به عنوان head این linked llist میسازیم، و مقدار next را به خودش نسبت میدهیم. بنابراین ما بررسی میکنیم که آیا linked list خالی است یا نه. اگر self.head برابر با None شود، در اینصورت عبارت شرطی خط ۲ True میشود و مقدار self.head را به نود جدید بر اساس پارامتر data تنظیم میکند. مقدار next در نود head را به خودش برمیگردانیم(خط ۴). اکنون به این موضوع میپردازیم که linked list خالی نباشد. در این موضوع، ما روی نودهای linked list حرکت میکنیم تا به نودی با مقدار next برابر head برسیم، این نود، نود آخر ما است و نود جدیدمان را بعد از این نود اضافه میکنیم. در خط ۶ مقدار new_node را با دادن data به سازنده کلاس Node تنظیم میکنیم. بعد ما باید یک موقعیت مناسب برای اضافه کردن new_node پیدا کنیم. برای اینکار، در خط ۷ مقدار cur را به self.head نسبت میدهیم و در خط ۸ یک حلقه while میسازیم و تا زمانی ادامه میابد که نود بعدی cur برابر self.head نشود. cur در هر تکرار حلقه به مقدار cur.next آپدیت میشود.(خط ۹) تا به ما کمک کند روی نود های linked list حرکت کنیم. بعد از اینکه یک while به اتمام رسید، cur نودی خواهد بود که به نود head اشاره میکند و ما new_node را بعد از cur اضافه میکنیم. بنابراین، ما مقدار cur.next را برابر new_node قرار میدهیم(خط ۱۰). برای اینکه این روش حلقوی ما تکمیل شود، ما مقدار new_node.next را هم به self.head نسبت میدهیم(خط ۱۱). این کار متد append ما را تکمیل میکند.

print_list

برای اینکه بتوانیم متدهایمان را ارزیابی کنیم نیاز داریم تا نودهای یک linked list را پرینت کنیم. اکنون بررسی میکنیم که چگونه این کار را میتوانیم انجام دهیم. به کد زیر توجه کنید:

def print_list(self):
  cur = self.head 

  while cur:
      print(cur.data)
      cur = cur.next
      if cur == self.head:
          break

برای پرینت کردن همه اعضای یک linked list، ما مقدار cur را self.head در خط ۲ به عنوان نقطه شروع، قرار میدهیم. سپس یک حلقه while در خط ۴ تعریف میکنیم که تازمانی که cur به مقدار none برسد ادامه پیدا میکند. در حلقه while، ما به سادگی مقدار cur.data را در خط ۵ پرینت میکنیم و سپس مقدار cur را به cur.next آپدیت میکنیم تا به نود بعدی در تکرار حلقه برویم(خط ۶). توجه کنید که در یک linked list هیچ نودی به None اشاره نمیکند. درعوض آخرین نود به head اشاره میکند. برای اینکه حلقه while در انتها به اتمام برسد، باید بررسی کنیم که ایا به head آن linked list رسیده‌ایم یا نه که این کار در خط ۷ با عبارت شرطی نوشته شده، تعیین میگردد. اگر این شرایط به وجود آمد در خط ۸ به کمک break از حلقه خارج میشویم. همانظور که ملاحظه کردید، متد print_list  کاملا کار ساده‌ای بود. اکنون به سراغ متد بعدی یعنی prepend میرویم.

Prepend

برای prepend کردن یک نود در یک linked list، باید آن را به عنوان head قرار دهیم. اکنون کد زیر را ببینید که چگونه میتوان این موضوع را در پایتون پیاده‌سازی کرد:

def prepend(self, data):
  new_node = Node(data)
  cur = self.head 
  new_node.next = self.head

  if not self.head:
      new_node.next = new_node
  else:
      while cur.next != self.head:
          cur = cur.next
      cur.next = new_node
  self.head = new_node

در خط ۲، مقدار new_node با یک شی جدید از کلاس Node و ورودی data، تعیین شده است. این نود جدید باید به عنوان head این linked list تعیین گردد. در حالی که head فعلی باید یک نود به جلو برود. بنابراین ما مقدار new_node.next را به self.head نسبت داده‌ایم(خط ۴). که در اینصورت مقدار next نود جدید به head قبلی ما لینک میشود. مقدار cur نیز به self.head در خط ۲ نسبت داده میشود. سپس، مانند کاری که در append انجام دادیم، باید بررسی کنیم که آیا این linked list ما، خالی است یا نود هایی دارد. اگر self.head برابر None بشود، ما به سادگی مقدار new_node.next به new_node در خط ۷ نسبت میدهیم تا عملیات حلقوی ما نیز کامل بشود. اما اگر مقدار self.head برابر None نشود، بخش else از عبارت شرطی اجرا خواهد شد. در بخش else، ما یک حلقه while در خط ۹ میسازیم که در آن مقدار cur به cur.next در هر  تکرار حلقه اپدیت میشود(خط ۱۰). این حلقه تا زمانی که مقدار cur.next برابر self.head بشود ادامه پیدا میکند. این یعنی اینکه حلقه while تازمانی ادامه پیدا میکند، که cur آخرین نود بشود، بعد از این کار ما در خط ۱۱، مقدار cur.next را برابر new_node قرار میدهیم تا بخش حلقوی linked list ما نیز تکمیل گردد. در نهایت، مقدار self.head را نیز new_node قرار میدهیم(خط ۱۲). که این کار آن را به عنوان head این linked list تعیین میکند. ما همه سه متدی که از ابتدای این درس یادگرفتیم را اکنون تست خواهیم کرد. کد زیر را بررسی کنید:

class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.head = None 

    def prepend(self, data):
        new_node = Node(data)
        cur = self.head 
        new_node.next = self.head

        if not self.head:
            new_node.next = new_node
        else:
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
        self.head = new_node

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
        else:
            new_node = Node(data)
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
            new_node.next = self.head

    def print_list(self):
        cur = self.head 

        while cur:
            print(cur.data)
            cur = cur.next
            if cur == self.head:
                break


cllist = CircularLinkedList()
cllist.append("C")
cllist.append("D")
cllist.prepend("B")
cllist.prepend("A")
cllist.print_list()

در این درس شما با مقدمات linked list های حلقوی و پیاده‌سازی ابتدایی آن آشنا شدید. —. در درس های آینده، مسائل دیگری که به linked list های حلقوی مربوط است را بررسی خواهیم کرد.

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

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

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

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