جلسه ۸۰: معرفی linked-list در پایتون

شما در این درس یادمی‌گیرید که لیست‌های پیوندی (singly linked list) چه هستند و چگونه میتوانیم آن را در پایتون پیاده‌سازی کنیم. به حاطر این دوره، ما چند نوع مختلف linked list ها را بررسی میکنیم و آن ها را نیز در پایتون پیاده‌سازی میکنیم.

1. Singly Linked Lists
2. Doubly Linked Lists
3. Circular Linked List

در زیر تصویر ساده ای از یک singly linked list را به صورت جداگانه میبینید.

ساختار

هر linked llist ای از نود هایی ساخته شده است، که در تصویر بالا هم این موضوع را میبینید. هر نود هم دو بخش دارد:

• Data
• Next

بخش Data  این امکان را به linked list ها در نود میدهد که در خود داده ای را هم ذخیره کنند. این داده میتواند از هر نوع داده string, Character, number یا هر نوع داده دیگری باشد. در تصویر بالا داده های ما A , B و C هستند که از نوع کاراکتر میباشند. جزو دیگر یک linked list اشاره‌گر آن است. که هر نود را به نود بعدی اشاره میدهد و به هم وصل میکند. شروع در هر linked list ای با head است. head یک اشاره‌گر(pointer) است که به اولین عضو linked list اشاره دارد و ما را به آن متصل میکند. بنابراین اگر ما بخواهیم یک المان از linked list را داشته باشیم چه دسترسی و چه تغییر دادن باید از head شروع کنیم. عضو آخر یک singly linked list هم همیشه null است. این ایده null ساختار linked list ما را به انتها میرساند و از آن خارج میشود. آخرین نود در singly linked list ها هم به آن null اشاره میکند، و به شما میگوید که اینجا انتهای linked list ما است.

آرایه‌ها دربرابر linked list

اضافه کردن/حذف کردن

اضافه یا حذف کردن یک مقدار، عملیاتی است که برای اضافه یا حذف کردن داده‌ای در ابتدای یک آرایه استفاده میشود و هزینه پیچیدگی  [این علامت قرار داده نشد] را به همراه دارد. اکنون فرض کنید میخواهیم یک مقدار را به ابتدای یک آرایه اضافه کنیم. برای اضافه کردن باید همه اعضای یک آرایه را به راست شیفت بدهیم. این کار یک مکان خالی در ابتدای آرایه برای اضافه کردن مقدار جدید به وجود میآورد. بر اساس این شیفت مقدار پیچیدگی این عملیات [این علامت قرار داده نشد] بدست آمده‌است. این مسیر برای حذف یک المان از ابتدای آرایه هم وجود دارد. دوباره، همه اعضای آرایه را به عقب به اندازه یک index شیفت میدهیم. بنابراین این عملیات هم، پیچیدگی و هزینه [این علامت قرار داده نشد] را دارد. اضافه کردن یک نود به head یک linked-list هزینه ای به اندازه، یک زمان کوتاه برای تغییر چند اشاره‌گر (pointer) است. اگر هم اشاره‌گر مشخصی به ما داده شود و قرار باشد یک نود بعد از آن اضافه کنیم، این کار هم یک کار با زمان کوتاه خواهد بود.

دسترسی به المان ‌ها

دسترسی به یک المان با توجه به index داده شده در آرایه‌ها کار بهتری نسبت به linked-list ها است.  اگر یک آرایه به همراه یک index به ما داده شود، میتواند به سرعت المانی که در آن index ذخیره شده است را به ما بدهد. این به این دلیل است که آرایه‌ها، مجاور و به هم پیوسته هستند. هزینه دسترسی به nامین المان در linked-list ها با توجه به اینکه به head هم دسترسی دارد، [این علامت قرار داده نشد] است. اگر نیاز به دسترسی به المانی داشته باشیم باید از head شروع کنیم و در linked-list بر اساس اشاره‌گر ها حرکت کنیم تا به محل المان مدنظر برسیم.

حافظه مجاور

آرایه‌ها در حافظه ها مجاور هم قرار میگیرند که امکان دسترسی به اعضای آرایه را به سرعت فراهم میکند. در حالی که در linked list ها، شما چیزی به اسم حافظه های مجاور ندارید. شما باید جدول بالا را هر زمان که نیاز باشد تا بین این دو یکی را انتخاب کنید، باید به خاطر بیاورید. اگر شما مسئله‌ای داشتید و دنبال این بودید که آیا آرایه ها مناسب هستند یا نه، برای اینکار شما نیاز دارید تا معایب و مزیت های این دو را کنار هم در نظر بگیرید.

پیاده‌سازی

اکنون سراغ ساخت کلاس های مدنظر در پایتون میرویم:

• کلاس node
• کلاس LinkedList

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

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

ما یک کلاس به اسم Node ساخته‌ایم. در سازنده این کلاس، در خط ۲ آرگومان های self و data را میدهیم. هر نود از data و next تشکیل شده است. ما self.data را  در خط ۳ برابر data که ورودی سازنده این شی از کلاس است، گذاشتیم. مقدار self.next را هم در خط ۴ برابر none قرار دادیم. این چیزی است که بعدا کاملش میکنیم ولی اکنون مقدار none به آن میدهیم. این تمام چیزی است که برای یک node نیاز داریم. در خط ۶ کلاس linkedList را داریم و در سازنده این کلاس هم آرگومان self را داده‌ایم. در خط ۸ اشاره گر head را تعریف کرده‌ایم، که به اولین نود یک linked-list اشاره دارد. اما برای شروع مقدار آن را None قرار میدهیم. اکنون ما کلاس ها را در برنامه پیاده‌سازی کردیم، در درس بعدی یاد میگیریم که چگونه المان هایی را به این linked list اضافه کنیم.