لیست‌های پیوندی (Linked Lists)
لیست پیوندی: گره‌ها و اشاره‌گرها، انواع singly و doubly، پیاده‌سازی کامل و مقایسه با آرایه
لیست پیوندی چیست؟
لیست پیوندی (Linked List) زنجیره‌ای از گره‌ها (Node) است؛ هر گره داده + آدرس گره بعدی را نگه می‌دارد. برخلاف آرایه، خانه‌ها پشت‌سرهم نیستند و با اشاره‌گر به هم وصل‌اند.
[داده | بعدی] -> [داده | بعدی] -> [داده | None]
head tailمثل گنجینه: هر برگه یک سرنخ دارد که می‌گوید سرنخ بعدی کجاست. برای رسیدن به گره ۵۰ام باید از اول بروید!
انواع لیست پیوندی
- تک‌پیوندی (Singly): هر گره فقط به بعدی اشاره می‌کند — یک‌طرفه
- دوپیوندی (Doubly): هر گره به قبل و بعد اشاره می‌کند — دوطرفه
- حلقوی (Circular): آخرین گره به اول برمی‌گردد
پیاده‌سازی گره
class Node:
def __init__(self, data):
self.data = data # داده
self.next = None # اشاره‌گر به گره بعدیعملیات و پیچیدگی‌ها
| عملیات | پیچیدگی | توضیح |
|---|---|---|
| دسترسی به گره iام | O(n) | باید از head قدم‌به‌قدم رفت |
| جستجو | O(n) | پیمایش ترتیبی |
| درج در ابتدا | O(1) | فقط دو اشاره‌گر عوض می‌شود! |
| حذف با اشاره‌گر به گره قبلی | O(1) | اتصال را دور می‌زنیم |
مقایسه آرایه و لیست پیوندی
| ویژگی | آرایه | لیست پیوندی |
|---|---|---|
| دسترسی اندیسی | O(1) ✓ | O(n) |
| درج/حذف ابتدا | O(n) | O(1) ✓ |
| حافظه | فشرده | سربار اشاره‌گر |
| محلیتی حافظه (Cache) | عالی ✓ | ضعیف |
| اندازه | ثابت (یا کپی در پویا) | رشد نرم ✓ |
کجا لیست پیوندی می‌درخشد؟
- صف‌های اولویت‌دار و صف‌های میانی سیستم‌عامل
- پیاده‌سازی پشته و صف
- برنامه‌هایی که درج/حذف مکرر در ابتدا دارند (مثل لیست پخش موسیقی)
- ساختارهای پیشرفته‌تر: گراف (لیست همسایگی)، هش جدول (زنجیره)
نکته: در پایتون، collections.deque در واقع لیست پیوندی + آرایه ترکیبی است و append/pop از هر دو طرف O(1) دارد — برای صف و پشته ایده‌آل!
تکنیک‌های رایج لیست پیوندی
- اشاره‌گر کند و تند (slow/fast): پیدا کردن وسط لیست یا تشخیص حلقه
- معکوس‌کردن لیست: تغییر جهت اشاره‌گرها (سؤال کلاسیک مصاحبه!)
- گره ساختگی (dummy): ساده‌سازی عملیات روی head
جمع‌بندی
- گره = داده + اشاره‌گر؛ خانه‌ها پراکنده در حافظه
- درج/حذف ابتدا O(1) اما دسترسی اندیسی O(n)
- مکمل آرایه است: هر کدام برای الگوی عملیاتی متفاوت بهینه
- پایه ساختارهای پیشرفته‌تر مثل گراف و هش زنجیره‌ای
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.