لیست پیوندی Linked List

لیست پیوندی یا Linked List چیست؟

لیست پیوندی (Linked List) مجموعه‌ای از عناصر داده‌ای است که در آن هر عنصر به عنصر بعدی خود اشاره می‌کند. این عناصر که در کنار یکدیگر تشکیل یک دنباله می‌دهند گره (Node) نامیده می‌شوند و در ساده‌ترین فرم (لیست یک طرفه)، هرکدام شامل یک فیلد داده و یک فیلد اشاره‌گر (ارجاع یا لینک) به گره بعدی خود می‌باشند. این اشاره‌گر با عناوینی چون Next Pointer یا Next Link نیز شناخته می‌شود.

از این ساختمان داده برای پیاده‌سازی لیست، پشته، صف، آرایه انجمنی و … استفاده می‌شود. معمولا برای دسترسی به یک لیست پیوندی از اشاره‌گری به اولین گره لیست استفاده می‌شود که به آن head (یا front) گفته می‌شود. در لیست‌های پیوندی ساده، معمولا اشاره‌گر گره آخر برابر با null (تهی) خواهد بود. در برخی موارد برای تسهیل افزودن گره به انتهای لیست، اشاره‌گری به نام tail درنظر گرفته می‌شود که به آخرین گره لیست اشاره می‌کند.

اعمال رایج لیست‌های پیوندی

اعمال رایجی که روی لیست‌های پیوندی انجام می‌شود عبارتست از: حذف نود از ابتدا و انتهای لیست، حذف نود پس از یک نود مشخص، پیمایش لیست (به منظور خواندن یا انجام عملی دیگر با استفاده از داده گره‌ها)، افزودن نود به ابتدا و انتهای لیست، افزودن نود پس از یک نود مشخص و یافتن نود با داده‌ای معین.

برای نمونه فرض کنید می‌خواهیم در لیست پیوندی یک طرفه شکل زیر، گره جدیدی با داده B پس از گره اول درج کنیم.

در صورتی که خصوصیات گره اول را داشته باشیم این کار به آسانی تنها با دو عمل انجام می‌شود. به این ترتیب که ابتدا اشاره‌گر گره جدید به گره بعدی گره A اشاره می‌کند و سپس اشاره‌گر گره A به گره جدید اشاره می‌کند.

شبه کد زیر نحوه انجام این کار را به زبان ساده بیان می‌کند. nodeA گرهی است که می‌خواهیم nodeB را پس از آن درج کنیم و next متغیر اشاره‌گر گره است:

function insertAfter(Node nodeA, Node nodeB)
     nodeB.next := nodeA.next
     nodeA.next := nodeB

انواع لیست‌های پیوندی

برای افزایش کارایی لیست‌های پیوندی یک طرفه (Singly Linked List)، گونه‌های مختلفی بر اساس همین ساختار شکل گرفته‌اند که از رایج‌ترین آن‌ها می‌توان به لیست پیوندی دو طرفه (Doubly Linked List) و لیست پیوندی دایره‌ای یا حلقوی (Circular Linked List) اشاره نمود.

در لیست پیوندی دو طرفه، هر نود علاوه بر یک اشاره‌گر به نود بعدی (Next) دارای یک اشاره‌گر به نود قبلی (Prev) نیز می‌باشد. به این ترتیب امکان پیمایش لیست در هر دو سمت فراهم می‌شود. در لیست‌های حلقوی، گره آخر به جای آنکه دارای ارجاع null باشد به گره ابتدایی (یا head) اشاره می‌کند. نوع دیگری که از ترکیب این دو مدل به دست می‌آید لیست پیوندی دوطرفه حلقوی نامیده می‌شود.

مزایا و معایب لیست‌های پیوندی

لیست پیوندی، ساختمان داده‎ای پویا (Dynamic) می‌باشد و برخلاف آرایه‌ها افزودن یا حذف عنصر در هر موقعیتی از آن بدون تغییر ساختار کنونی و جابجایی عناصر امکان‌پذیر است. به علاوه طبیعتا لازم نیست در ابتدای ایجاد یک لیست پیوندی، ظرفیت آن را مشخص کنید. در لیست‌های پیوندی از نظر فیزیکی الزاما گره‌ها به طور پیوسته و در کنار یکدیگر روی حافظه قرار نگرفته‌اند.

از آنجا که در لیست‌های پیوندی برای هر گره، ارجاعی به گره بعدی نیز درنظر گرفته می‌شود این ساختمان داده در مقایسه با آرایه‌ها نیازمند حافظه‌ای بیشتر برای نگه‌داری داده‌هاست. به علاوه در لیست‌های پیوندی ساده امکان دسترسی تصادفی به داده‌ها وجود ندارد و انجام اعمالی نظیر یافتن گرهی با داده مشخص و در برخی موارد تعیین محلی که گره جدید باید درج شود (مانند زمانی که می‌خواهیم گره جدید پس از گرهی که دارای یک داده مشخص است درج شود) نیازمند پویش تعدادی از گره‌ها (و در بدترین حالت تمامی گره‌ها) خواهد بود.

هم‌چنین در لیست‌های پیوندی یک طرفه امکان پیمایش معکوس لیست دشوارتر خواهد بود. هرچند این مشکل در لیست‌های پیوندی دوطرفه برطرف شده است اما این لیست‌ها هم به خاطر داشتن اشاره‌گر به گره قبلی نیازمند حافظه بیشتری هستند.