لیست پیوندی چیست؟

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

ساختار گره در لیست‌های پیوندی

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

گره‌ها دو جز دارند و آن دو جز Data و Next Pointer هستند:

• Data : این جز از گره، جایی است که اطلاعات واقعی در آن ذخیره می‌شود. این اطلاعات می‌تواند هر چیزی باشد، از یک عدد ساده تا یک شیء پیچیده. مثلاً در یک لیست پیوندی که برای ذخیره نام افراد استفاده می‌شود، قسمت داده هر گره نام یک نفر را نگه می‌دارد.
• Next Pointer: این قسمت از گره، آدرس گره بعدی در لیست را نگه می‌دارد. به‌عبارت‌دیگر، این اشاره‌گر به ما می‌گوید که گره بعدی در کجا قرار دارد. این اشاره‌گرها هستند که گره‌ها را به هم متصل می‌کنند و ساختار لیست‌های پیوندی را شکل می‌دهند.

گره‌ها به این صورت به یکدیگر متصل می‌شوند:

• Head : اولین گره در لیست، سرلیست یا Head نامیده می‌شود. یک اشاره‌گر به سرلیست، کل لیست را قابل‌دسترسی می‌کند.
• Tail: آخرین گره در لیست، Tail نامیده می‌شود. اشاره‌گر بعدی Tail معمولاً به مقدار null اشاره می‌کند تا نشان دهد که لیست به پایان رسیده است.

انجام پروژه‌ داده کاوی با بهترین هزینه توسط متخصصان حرفه‌ای

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

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

• لیست‌های پیوندی یک‌طرفه یا Singly Linked List

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

• لیست‌های پیوندی دوطرفه یا Doubly Linked List

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

• لیست‌های پیوندی حلقوی یا Circular Linked List

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

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

نوع مناسب لیست پیوندی بر اساس عوامل مختلفی انتخاب می‌شود؛ این عوامل عبارت‌اند از:

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

مطلب پیشنهادی: داده باز چیست؟

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

لیست‌ پیوندی ساختار داده‌ای قدرتمندی است که مزایا و معایبی دارد. در ادامه برخی از مهم‌ترین نکات مثبت و منفی استفاده از لیست‌های پیوندی را بیان کرده‌ایم.

مزایا

• لیست‌های پیوندی می‌توانند به راحتی رشد کنند یا جمع شوند. دلیل این امر این است که گره‌ها به صورت جداگانه به حافظه اختصاص داده شده‌اند و با اشاره‌گرها به هم متصل می‌شوند. در نتیجه، شما می‌توانید به راحتی عناصر را به ابتدای لیست، انتهای لیست یا وسط لیست اضافه یا آن‌ها را حذف کنید.
• درج یا حذف یک عنصر در ابتدای لیست پیوندی یا وسط به صورت کاملا بهینه‌ای رخ می‌دهد از آنجایی که نیازی به جابه‌جایی سایر عناصر برای ایجاد فضای خالی یا به هم ریختن لیست نیست، این رخداد کاملا کارآمد است.
• لیست‌های پیوندی در اندازه خود، محدودیتی ندارند. تا زمانی که حافظه در دسترس باشد، می‌توانید همچنان گره‌ها را به لیست اضافه کنید.

معایب

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

مطلب پیشنهادی: رمزنگاری چیست؟

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

در ادامه مطلب به بررسی برخی از مهم‌ترین کاربردهای لیست پیوندی اشاره می‌کنیم:

1- پیاده‌سازی ساختارهای داده‌ای انتزاعی:

در صف‌ ها  یا Queues، عناصر به ترتیب ورود اضافه و حذف می‌شوند. لیست‌های پیوندی یک انتخاب مناسب برای پیاده‌سازی صف‌ها هستند؛ زیرا اضافه کردن عنصر جدید به انتها و حذف عنصر از ابتدا به راحتی انجام می‌گیرد.

در پشته‌ها یا Stacks آخرین عنصر اضافه شده اولین عنصری است که حذف می‌شود. لیست‌های پیوندی نیز برای پیاده‌سازی پشته‌ها مناسب هستند؛ زیرا اضافه کردن و حذف عناصر از انتها به سادگی انجام می‌شود.

2- مدیریت حافظه:

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

3- پیاده‌سازی گراف‌ها:

یکی از روش‌های نمایش گراف‌ها، استفاده از لیست مجاورت است. در این روش، برای هر رأس یک لیست پیوندی از رأس‌های مجاور آن ایجاد می‌شود.

4- ویرایشگرهای متن:

در بسیاری از ویرایشگرهای متن، از لیست‌های پیوندی برای پیاده‌سازی عملکرد Undo/Redo استفاده می‌شود. هر عمل ویرایش به عنوان یک گره در لیست ذخیره می‌شود و در صورت نیاز می‌توان به حالت‌های قبلی بازگشت.

5- سیستم‌های عامل:

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

6- بازی‌ها:

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

7- شبکه‌های اجتماعی:

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

8- سیستم‌های توصیه‌گر:

سیستم‌های توصیه‌گر از لیست‌های پیوندی برای نگهداری لیست‌های توصیه شده به کاربران استفاده می‌کنند. این لیست‌ها به طور مداوم بر اساس رفتار کاربر به‌روز می‌شوند.

مطلب پیشنهادی: داده ساختار یافته چیست؟

مقایسه لیست‌های پیوندی و آرایه‌ها

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

آرایه‌ها

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

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

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

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

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

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

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

این مقاله را بخوانید: سری زمانی در داده کاوی

جمع‌بندی

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