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

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

آموزش برنامه‌نویسی با بهترین هزینه توسط اساتید حرفه‌ای

تعریف لیست پیوندی به زبان ساده

بگذارید با یک مثال ساده، لیست پیوندی را تعریف کنیم. یک زنجیره از مهره ها را تصور کنید؛ این زنجیره همان لیست پیوندی (Linked List) است و هر مهره از این زنجیره در لیست پیوندی با نام “گره” شناخته می شود. هر گره از این زنجیره، از دو بخش اصلی تشکیل شده است.

• مقدار (پیوند یا Link): این بخش برای ذخیره داده (عنصر) است و این داده می تواند یک اسم یا عدد باشد.
• آدرس گره بعدی (اشاره گر یا Next): در این بخش آدرس گره بعدی ذخیره می شود.

به این ترتیب هر گره به گره بعد از خود اشاره کرده و در لیست پیوندی می توانید از گره اول شروع کرده و به گره های بعدی بروید. همچنین لازم به ذکر است که در لیست پیوندی، داده ها با نام “عنصر” شناخته می شوند.

اگر همچنان مفهوم لیست پیوندی برایتان گنگ است؛ پس مثال زیر را با دقت مطالعه کنید:

تصور کنید یک زنجیره دارید که از مهره های رنگی تشکیل شده و هر مهره عدد خاص خود را دارد؛ مانند:

• مهره اول: شماره 1
• مهره دوم: شماره 2
• مهره سوم: شماره 3

در زبان برنامه نویسی، این مهره ها را به شکل زیر می نویسیم:

[1] -> [2] -> [3] -> null

تعریف این ترتیب به صورت زیر است:

• [1]: مهره اول که به مهره دوم اشاره دارد.
• [2]: مهره دوم که به مهره سوم اشاره دارد.
• [3]: مهره سوم که به “null”  اشاره دارد.

Null: به معنی پایان زنجیره بوده و نشان می دهد که اینجا انتهای زنجیره است.

یک مفهوم دیگر که باید درباره لیست پیوندی بدانید؛ مفهوم “سر و دُم” است که آنها را اینطور تعریف می کنیم:

• گره سَر: اولین گره در لیست پیوندی، گره سَر نام دارد و از طریق این گره می توان به همه گره های موجود در این لیست، دسترسی پیدا کرد.
• گره دُم: آخرین گره در لیست پیوندی، گره دُم نام دارد. بخش اشاره گر در گره دُم به null اشاره می کند که نشان دهنده پایان یا انتهای لیست پیوندی است.

اگر تا اینجا به خوبی با مفهوم لیست پیوندی آشنا شده اید؛ پس به سراغ بخش های بعدی مقاله می رویم.

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

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

لیست پیوندی را می توان در چهار دسته اصلی، دسته بندی کرد که به شرح زیر هستند.

لیست پیوندی تک ‌جهته (Singly Linked List)

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

لیست پیوندی دو‌جهته (Doubly Linked List)

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

لیست پیوندی دایره‌ ای (Circular Linked List)

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

لیست پیوندی دایره ‌ای دو‌جهته (Doubly Circular Linked List)

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

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

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

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

ذخیره سازی عناصر متغیر

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

مدیریت و نظم دهی به داده های پویا

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

مدیریت و استفاده بهینه از حافظه

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

پیاده سازی گراف ها

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

پیاده سازی ساختارهای داده ای پیچیده تر

از لیست پیوندی می توان به عنوان پایه ای برای قرار دادن ساختارهای داده ای دیگر، مانند پشته (stack) و صف (queue) استفاده کرد.

مدیریت تاریخچه سرچ در مرورگر

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

مدیریت موجودیت ها در بازی

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

مدیریت صف های چاپ

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

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

مزایای لیست پیوندی

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

انعطاف پذیری بالا

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

تنوع در نوع داده ها

در یک لیست پیوندی می توانید انواع مختلف و متنوعی از داده ها را ذخیره کنید. به عنوان مثال در یک لیست پیوندی، قابلیت ذخیره سازی داده ها را به صورت عدد، اسم، شئ و غیره خواهید داشت.

سازماندهی داده ها

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

پیاده سازی ساختارهای داده ای

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

مطلب پیشنهادی: برنامه‌نویسی ماژولار چیست؟

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

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

نیازمند استفاده بیشتر از حافظه

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

دسترسی کند و زمان بَر به عناصر

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

نداشتن اندازه ثابت

این که لیست پیوندی از یک اندازه ثابت پشتیبانی نمی کند؛ می تواند هم مزیت باشد و هم عیب! عیب آن این است که در هر لحظه احتمال دارد این لیست نیازمند فضای بیشتری برای ذخیره سازی داده ها باشد.

نیازمند مدیریت دقیق اشاره گرها

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

عدم ذخیره سازی متوالی عناصر

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

پیچیدگی در پیاده سازی لیست پیوندی

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

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

کلام آخر

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