لیست پیوندی چیست؟ – در ساختمان داده و به زبان ساده

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

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

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

فیلم آموزش ساختمان داده ها با پایتون در فرادرس

کلیک کنید

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

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

چه نیازی به ساختمان داده لیست های پیوندی داریم؟

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

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

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

مثال

فرض کنید که درون سیستمی لیست منظمی از شماره‌های شناسایی را مانند id[] = [1000, 1010, 1050, 2000, 2040]  ذخیره کرده‌ایم.

اگر بخواهیم که id  جدیدی را به این ترتیب منظم وارد کنیم، به عنوان مثال 1005  ، برای حفظ نظم و ترتیب صف باید همه عناصر بعد از 1000  را حرکت دهیم.

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

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

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

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

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

• فیلم آموزش ساختمان داده ها با فرادرس
• فیلم آموزش طراحی الگوریتم با فرادرس
• فیلم آموزش ساختمان داده ها همراه با مرور و تست کنکور ارشد با فرادرس
• فیلم آموزش ساختمان داده ها و پیاده سازی در C++‎ با فرادرس
• فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته همراه با مرور و تست کنکور ارشد در فرادرس

در صورت نیاز به مشاهده فیلم‌های بیشتر می‌توانید بر روی تصویر بالا کلیک کرده و به صفحه اصلی این مجموعه آموزشی مراجعه کنید.

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

به‌طور کلی لیست‌های پیوندی به سه نوع اصلی تقسیم می‌شوند.

1. لیست‌های پیوندی یک‌طرفه
2. لیست‌های پیوندی دوطرفه
3. لیست‌های پیوندی حلقوی

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

در این بخش انواع لیست‌های پیوندی را با تکنیک‌های مربوط به هر کدام مورد بررسی دقیق قرار داده‌ایم.

لیست پیوندی یک‌طرفه

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

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

ویژگی های لیست های پیوندی یک‌طرفه

این بخش را به بحث درباره اینکه ویژگی‌های کلی این نوع از لیست‌های پیوندی چیست پرداخته‌ایم.

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

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

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

• «مدیریت حافظه» (Memory Management): لیست‌های پیوندی یک‌طرفه می‌توانند برای پیاده‌سازی «استخر حافظه» (Memory Pool) به‌کار روند. استخر حافظه، تقسیم منطقی از حافظه اصلی یا فضای ذخیره‌سازی داده‌ها است که برای پردازش فعالیتی یا گروه خاصی از فعالیت‌ها رزرو شده است.
• «ایندکس‌گذاری پایگاه داده» (Database Indexing): لیست‌های پیوندی یک‌طرفه برای پیاده‌سازی لیست‌های پیوندی درون پایگاه های داده نیز به‌کار برده‌ می‌شوند. این کار باعث سریع‌تر شدن عملیات مربوط به ورود و حذف داده‌ها می‌شود.
• نمایش چندجمله‌ای‌ها و «ماتریس های خلوت» (Sparse Matrices) یا اسپارس: در جایی که اکثر عناصر، صِفر هستند می‌توان از لیست‌های پیوندی یک‌طرفه برای نمایش چند جمله‌ای‌ها و ماتریس‌های اسپارس به صورت کارآمدی استفاده کرد.
• سیستم‌های عامل: از لیست‌های پیوندی یک‌طرفه در سیستم های عامل برای انجام وظایفی مانند زمان‌بندی نوبت اجرای پردازش‌ها و مدیریت منابع سیستم استفاده می‌شود.

مزایای لیست های پیوندی یک‌طرفه

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

1. «تخصیص حافظه پویا» (Dynamic Memory Allocation | DMA): لیست‌های پیوندی یک‌طرفه از مزیت تخصیص حافظه پویا بهره‌مند هستند. به این معنا که اندازه لیست در زمان اجرای برنامه با حذف شدن یا اضافه شدن داده‌های لیست به‌ صورت پویا کم یا زیاد می‌شود.
2. «مناسب برای کار با کش» (Cache Friendliness): از آنجا که گره‌ها را می‌توان در صف‌های جداگانه‌ای در کش‌ ذخیره کرد، لیست‌های پیوندی یک‌طرفه برای کار با حافظه کش گزینه مناسبی هستند. این کار احتمال از درست رفتن داده‌ها در کش را کاهش داده و کارایی سیستم را افزایش می‌دهد.
3. «کارآمدی در فضای حافظه» (Space-Efficient): لیست‌های پیوندی یک‌طرفه در استفاده از فضای ذخیره‌سازی بسیار کارآمد هستند. زیرا این لیست‌ها به‌جای اینکه فضای پیوسته و بزرگی از حافظه را اشغال کنند، برای هر عنصر فقط به ذخیره آدرس گره بعدی نیاز دارند.

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

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

1. کارایی ضعیف در دسترسی تصادفی: برای دسترسی به هر مقداری در لیست‌های پیوندی یک‌طرفه باید از سمت سر لیست تا رسیدن به گره حاوی مقدار مورد نظر پیمایش کنیم. این نوع از دسترسی، لیست پیوندی یک‌طرفه را برای اجرای عملیات دسترسی تصادفی نسبت به آرایه‌ها بسیار ضعیف‌تر می‌کند.
2. افزایش سربار حافظه: لیست‌های پیوندی یک‌طرفه نیاز به حافظه اضافی برای ذخیره آدرس گره بعدی یا نشانگر در هر گره دارند. این کار باعث می‌شود که در مقایسه با آرایه‌ های برنامه نویسی هزینه بیشتری را بر روی حافظه سیستم وارد کنند.
3. آسیب‌پذیر بودن در مقابل از دست رفتن داده‌ها: در لیست‌های پیوندی یک‌طرفه، اگر اشاره‌گر گره‌‌ای حذف یا خراب شود دیگر امکان پیمایش بر بروی لیست و دسترسی به گره‌های بعدی وجود ندارد. در نتیجه لیست‌های پیوندی در مقابل از دست‌دادن داده‌ها می‌توانند بسیار آسیب‌پذیر باشند.
4. نامناسب برای پردازش‌های موازی: لیست‌های پیوندی یک‌طرفه برای پردازش‌های موازی مناسب نیستند. زیرا به‌روزرسانی مقادیر گره‌ها نیازمند دسترسی انحصاری به اشاره‌گر گره بعدی دارد و دسترسی انحصاری چیزی نیست که به‌سادگی در محیط‌های عملیاتی موازی بدست آید.
5. پیمایش روبه‌عقب ممکن نیست: لیست‌های پیوندی یک‌طرفه، از عملیات پیمایش لیست به سمت عقب پشتیبانی نمی‌کنند. در واقع گره‌ها اصلا نمی‌دانند که گره قبلی در کجای حافظه قرار دارد.

لیست های پیوندی دوطرفه

در ادامه مطلب «لیست پیوندی چیست» نوبت به معرفی لیست‌های پیوندی دوطرفه رسیده است. در «لیست‌های پیوندی دوطرفه» (Doubly Linked Lists | DLL) هر گره‌ای شامل دو مرجع آدرس است. یکی برای اشاره به گره بعدی و دیگری برای اشاره به گره قبلی مورد استفاده قرار می‌گیرد. به کمک این خاصیت، می‌توان لیست را در هردو جهت جلو و عقب پیمایش کرد. اما این نوع از گره‌ها نیز نیاز به حافظه اضافی برای نگهداری آدرس گره قبل از خود دارند.

اضافه کردن گره جدید به لیست‌های پیوندی دوطرفه بسیار شبیه به اضافه کردن گره در لیست‌های پیوندی یک‌طرفه است. فقط باید کمی کار اضافه برای نگهداری آدرس یا مقدار نشانگر مربوط به گره قبلی انجام دهیم.

گره جدید می‌تواند در چهار حالت متفاوت به لیست پیوندی دوطرفه اضافه شود.

• در جلو یا سر صف DLL
• بین دو گره در وسط لیست پیوندی دوطرفه
  • وارد کردن گره جدید بعد از گره مشخص شده
  • وارد کردن گره جدید قبل از گره مشخص شده
• در عقب یا بعد از دم DLL

در ادامه تمام این روش‌ها را همراه با کدهای پیاده‌سازی شده بررسی کرده‌ایم.

وارد کردن گره جدید در سر لیست پیوندی دو طرفه

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

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

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

1def push(self, new_data):
2
3    # 1 & 2: Allocate the Node & Put in the data
4    new_node = Node(data=new_data)
5
6    # 3. Make next of new node as head and previous as NULL
7    new_node.next = self.head
8    new_node.prev = None
9
10    # 4. change prev of head node to new node
11    if self.head is not None:
12        self.head.prev = new_node
13
14    # 5. move the head to point to the new node
15    self.head = new_node

وارد کردن گره جدید بین دو گره در لیست پیوندی دوطرفه

همین‌طور که اشاره کردیم این عملیات را می‌توان به دو روش زیر انجام داد.

• وارد کردن گره جدید بعد از گره مشخص شده
• وارد کردن گره جدید قبل از گره مشخص شده

اضافه کردن گره جدید به لیست پیوندی دوطرفه بعد از گره مشخص شده

در فرض این مسئله، اطلاعات مربوط به نشانگر به سمت گره‌ای به نام گره قبلی prev_node  داده شده است. گره جدید را باید دقیقا بعد از این گره در لیست وارد کنیم.

برای انجام این عملیات می‌توانیم مراحل زیر را به صورت قدم به قدم انجام دهیم.

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

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

1def insertAfter(self, prev_node, new_data):
2
3    # Check if the given prev_node is NULL
4    if prev_node is None:
5        print("This node doesn't exist in DLL")
6        return
7
8    # 1. allocate node  & 
9    # 2. put in the data
10    new_node = Node(data=new_data)
11
12    # 3. Make next of new node as next of prev_node
13    new_node.next = prev_node.next
14
15    # 4. Make the next of prev_node as new_node
16    prev_node.next = new_node
17
18    # 5. Make prev_node as previous of new_node
19    new_node.prev = prev_node
20
21    # 6. Change previous of new_node's next node
22    if new_node.next is not None:
23        new_node.next.prev = new_node

اضافه کردن گره جدید به لیست پیوندی دوطرفه قبل از گره مشخص شده

در این مسئله فرض می‌گیریم که اطلاعات مربوط به گره‌ای next_node  داده شده که گره جدید ما باید قبل از آن در لیست قرار بگیرد.

برای انجام این عملیات می‌توانیم مراحل زیر را به صورت قدم به قدم انجام دهیم.

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

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

1def insertAfter(self, next_node, new_data):
2
3    # Check if the given next_node is NULL
4    if next_node is None:
5        print("This node doesn't exist in DLL")
6        return
7
8    # 1. Allocate node  & 
9    # 2. Put in the data
10    new_node = Node(data=new_data)
11
12    # 3. Make previous of new node as previous of prev_node
13    new_node.prev = next_node.prev
14
15    # 4. Make the previous of next_node as new_node
16    next_node.prev = new_node
17
18    # 5. Make next_node as next of new_node
19    new_node.next = next_node
20
21    # 6. Change next of new_node's previous node
22    if new_node.prev is not None:
23        new_node.prev.next = new_node
24    else:
25        head = new_node

وارد کردن گره جدید در انتها یا دم لیست پیوندی دو طرفه

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

• در ابتدا گره جدیدی به نام new_node ایجاد می‌کنیم.
• سپس داده مورد نظر را در بخش داده گره جدید new_node وارد می‌کنیم.
• اشاره‌گر خانه بعدی new_node را برابر با NULL قرار می‌دهیم.
• اگر لیست خالی باشد، new_node را به عنوان گره سر لیست تعیین می‌کنیم.
• در غیر این صورت، به سمت انتهای لیست حرکت می‌کنیم و این گره را به عنوان گره انتها یا دم لیست تعیین می‌کنیم.
• الان باید اشاره‌گر خانه بعدی آخرین گره را با اطلاعات مربوط به آدرس new_node پُر کنیم.
• اطلاعات مربوط به اشاره‌گر خانه قبلی new_node را با اطلاعات مربوط به آدرس آخرین گره فعلی در لیست پر می‌کنیم.

در پایین پیاده‌سازی مراحل بالا را با زبان برنامه‌نویسی پایتون نمایش داده‌ایم.

1def append(self, new_data):
2
3    # 1. allocate node 
4    # 2. put in the data
5    new_node = Node(data=new_data)
6    last = self.head
7
8    # 3. This new node is going to be the
9    # last node, so make next of it as NULL
10    new_node.next = None
11
12    # 4. If the Linked List is empty, then
13    #  make the new node as head
14    if self.head is None:
15        new_node.prev = None
16        self.head = new_node
17        return
18
19    # 5. Else traverse till the last node
20    while (last.next is not None):
21        last = last.next
22
23    # 6. Change the next of last node
24    last.next = new_node
25    # 7. Make last node as previous of new node */
26    new_node.prev = last

لیست های پیوندی حلقوی

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

به‌طور کلی دو نوع لیست پیوندی حلقوی وجود دارند.

• «لیست پیوندی حلقوی یک‌طرفه» (Circular Singly Linked List): در لیست‌های پیوندی حلقوی یک‌طرفه، آخرین گره لیست شامل اشاره‌گری می‌شود که به اولین گره لیست اشاره می‌کند. در روی این لیست‌های پیوندی می‌توانیم تا زمان رسیدن به محل شروع حرکت، پیمایش کنیم. لیست پیوندی حلقوی یک‌طرفه هیچ محل شروع یا پایانی ندارد. به همچنین، در بخش گره بعدی هیچ گره‌ای به مقدار NULL اشاره نشده است.

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

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

پیاده سازی لیست پیوندی حلقوی

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

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

1class Node:
2    def __init__(self,data):
3        self.data = data
4        self.next = None

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

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

1one = Node(3)
2two = Node(5)
3three = Node(9)
4
5# Connect nodes
6one.next = two
7two.next = three
8three.next = one

توضیحات: در برنامه‌ بالا  one  و two  و three  گره‌هایی با مقادیر به ترتیب 3  ، 5  و 9  هستند. این گره‌ها در یک حالت حلقوی با یکدیگر متصل‌اند.

• برای گره one: اشاره‌گر بعد، آدرس گره two را ذخیره کرده است.
• برای گره two: اشاره‌گر بعد، آدرس گره three را ذخیره کرده است.
• برای گره three: اشاره‌گر بعد، آدرس گره one را ذخیره کرده است.

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

مزایای استفاده از لیست پیوندی حلقوی

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

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

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

معایب استفاده از لیست پیوندی حلقوی

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

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

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

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

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

انواع عملیات رایج در لیست پیوندی چیست؟

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

1. «ورود داده» (Insertion): اضافه کردن گره جدید به لیست‌‌های پیوندی، شامل تنظیم کردن اشاره‌گرهای موجود بر روی گره‌ها به‌منظور حفظ نظم جاری به صورتی مناسب است. عملیات ورود داده‌ها را می‌توان از ابتدا، انتها یا هر موقعیت درون لیست انجام داد.
2. «حذف داده» (Deletion): با حذف هر گره از لیست یک جای خالی به‌جای آن‌ گره به‌جا می‌ماند. بنابراین، حذف کردن گره‌ای از درون لیست مستلزم تنظیم اشاره‌گرهای گره‌های همسایه برای پرکردن فاصله ایجاد شده است. عملیات حذف داده‌ها را می‌توان از ابتدا، انتها یا هر موقعیت درون لیست انجام داد.
3. «جست‌وجو» (Searching): جست‌وجو به دنبال مقدار مشخصی درون لیست پیوندی، شامل پیمایش لیست از گره سر تا مقدار مورد نظر یا تا گره دم است.

فیلم آموزش درهم سازی در ساختمان داده (رایگان) در فرادرس

کلیک کنید

عملیات Insertion در لیست پیوندی را به‌طور کامل در بالای همین مطلب، بخش مربوط به لیست پیوندی دوطرفه توضیح داده‌ایم. در ادامه این بخش نیز عملیات «حذف داده» (Deletion) و «جست‌وجو» (Searching) را با نمایش مثال‌های کدنویسی شده به‌طور کامل توضیح داده‌ایم.

عملیات Deletion در لیست پیوندی

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

همانند عملیات Insertion، اجرای عمل Deletion نیز در سه موقعیت مختلف قابل انجام است.

• سر لیست
• وسط لیست
• انتهای لیست

بررسی اجرای عمل Deletion را با حذف گره از سر لیست شروع می‌کنیم.

حذف گره از سر لیست پیوندی

حذف گره از سر لیست پیوندی، عملیات ساده‌ای است.

• بهتر است که در ابتدا داده درون گره سر head  را درون متغیر موقتی -در اینجا نام دلخواه temp  را برای این متغیر انتخاب کردیم- ذخیره کنیم. معمولا به داده‌های گره‌های حذف شده برای اجرای عملیات بعدا نیاز داریم.
• سپس نشانگر head را بر روی گره بعد از گره سر فعلی تنظیم می‌کنیم.
• گره را حذف می‌کنیم.
• مطمئن می‌شویم که حافظه گره حذف شده آزاد شده باشد.

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

حذف گره از انتهای لیست پیوندی

این عملیات هم تقریبا مانند عملیات قبلی است. فقط شامل چند تغییر جزئی شده است.

• نشانگر head را بر روی گره قبلی تنظیم می‌کنیم.
• اطلاعات درون نشانگر مربوط به خانه بعدی در گره قبلی را به NULL تغییر می‌دهیم.
• داده درون گره آخر را درون متغیر موقتی نگهداری می‌کنیم.
• گره نهایی قبلی را حذف کرده و از آزاد شدن حافظه اشغال شده مطمئن می‌شویم.

حذف گره از وسط لیست پیوندی

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

• داده درون گره را در متغیر موقتی temp وارد می‌کنیم.
• آدرس گره بعدی در خانه قبلی را به گره بعد از گره‌ای که باید حذف شود تغییر می‌دهیم.
• اگر لیست دوطرفه بود آدرس گره قبلی در گره بعدی را به گره قبل از گره فعلی تغییر می‌دهیم.
• گره هدف را حذف کرده و حافظه اشغال شده را آزاد می‌کنیم.

پیاده‌سازی عملیات حذف گره

برای پیاده‌سازی عمل حذف هر عنصر در لیست دو روش عمده وجود دارد.

1. استفاده از تکنیک پیمایشی
2. استفاده از تکنیک بازگشتی

استفاده از تکنیک پیمایشی

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

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

پیاده‌سازی عملیات حذف گره در لیست پیوندی با استفاده از زبان برنامه‌نویسی پایتون

1class Node:
2	# constructor to initialize the node object
3	def __init__(self, data):
4		self.number = data
5		self.next = None
6
7
8def push(head, A):
9	n = Node(A)
10	n.number = A
11	n.next = head
12	head = n
13	return head
14
15
16def deleteN(head, position):
17	temp = head
18	prev = head
19	for i in range(0, position):
20		if i == 0 and position == 1:
21			head = head.next
22
23		else:
24			if i == position-1 and temp is not None:
25				prev.next = temp.next
26			else:
27				prev = temp
28
29				# Position was greater than
30				# number of nodes in the list
31				if prev is None:
32					break
33				temp = temp.next
34	return head
35
36
37def printList(head):
38	while(head):
39		if head.next == None:
40			print("[", head.number, "] ", "[", hex(id(head)), "]->", "nil")
41		else:
42			print("[", head.number, "] ", "[", hex(
43				id(head)), "]->", hex(id(head.next)))
44		head = head.next
45	print("")
46	print("")
47
48
49head = Node(0)
50head = push(head, 1)
51head = push(head, 2)
52head = push(head, 3)
53
54printList(head)
55
56# Delete any position from list
57head = deleteN(head, 1)
58printList(head)

خروجی حاصل از اجرای کدهای بالا به‌ صورت زیر نمایش داده می‌شود.

[3] [0x1b212c0]->0x1b212a0
[2] [0x1b212a0]->0x1b21280
[1] [0x1b21280]->0x1b21260
[0] [0x1b21260]->(nil)


[2] [0x1b212a0]->0x1b21280
[1] [0x1b21280]->0x1b21260
[0] [0x1b21260]->(nil)

استفاده از تکنیک بازگشتی

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

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

پیاده‌سازی عملیات حذف گره در لیست پیوندی با استفاده از زبان برنامه‌نویسی پایتون

1class Node:
2	def __init__(self,data):
3		self.data = data
4		self.next = None
5
6# Deletes the node containing 'data'
7# part as val and alter the head of
8# the linked list (recursive method)
9def deleteNode(head, val):
10	# Check if list is empty or we
11	# reach at the end of the
12	# list.
13	if (head == None):
14		print("Element not present in the list")
15		return -1
16	# If current node is the
17	# node to be deleted
18	if (head.data == val):
19		# If it's start of the node head
20		# node points to second node
21		if head.next: 
22			head.data = head.next.data
23			head.next = head.next.next
24			return 1
25		else: return 0
26	if deleteNode(head.next, val) == 0:
27		head.next = None
28		return 1
29
30# Utility function to add a
31# node in the linked list
32# Here we are passing head by
33# reference thus no need to
34# return it to the main function
35def push(head, data):
36	newNode = Node(data) 
37	newNode.next = head 
38	head = newNode 
39	return head
40
41# Utility function to print
42# the linked list (recursive
43# method)
44def printLL(head):
45	if (head == None):
46		return
47	temp = head
48	while temp:
49		print(temp.data,end=' ')
50		temp = temp.next
51	print()
52
53# Driver Code
54
55# Starting with an empty linked list
56head = None
57# Adds new element at the
58# beginning of the list
59head = push(head, 10) 
60head = push(head, 12) 
61head = push(head, 14) 
62head = push(head, 15)
63# original list
64printLL(head) 
65# Call to delete function
66deleteNode(head, 20) 
67# 20 is not present thus no change
68# in the list
69printLL(head) 
70deleteNode(head, 10) 
71printLL(head) 
72deleteNode(head, 14) 
73printLL(head)

عملیات Searching در لیست پیوندی

برای بررسی این عملیات، فرض می‌کنیم که لیست پیوندی به همراه کلید X  داده شده است. الان باید وجود یا عدم وجود کلید X را در لیست پیوندی بررسی کنیم. به عنوان مثال اگر لیست پیوندی به شکل 14->21->11->30->10  و X = 14  داده شده باشند. خروجی این برنامه باید Yes  شود و اگر لیست پیوندی به شکل 6->21->17->30->10->8  و X = 13  شود خروجی این عملیات جست‌وجو باید به شکل No  باشد.

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

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

برای انجام جست‌وجوی پیمایشی برای پیداکردن عنصری درون لیست پیوندی باید مراحل زیر را طی کنیم.

• اشاره‌گر گره را مقدار دهی اولیه می‌کنیم current = head  .
• تا وقتی که مقدار گره فعلی current  برابر با NULL نشده عملیات زیر را تکرار می‌کنیم.
  • اگر مقدار فعلی current  برابر با مقدار کلید X شد در خروجی True  را برمی‌گردانیم یعنی current->key  .
  • در غیر این صورت به حرکت خود برای رفتن به گره بعدی ادامه می‌دهیم current = current->next  .
• در نهایت اگر مقدار کلید X پیدا نشد در خروجی False  را برمی‌گردانیم.

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

1class Node:
2
3	# Function to initialise the node object
4	def __init__(self, data):
5		self.data = data # Assign data
6		self.next = None # Initialize next as null
7
8# Linked List class
9
10
11class LinkedList:
12	def __init__(self):
13		self.head = None # Initialize head as None
14
15	# This function insert a new node at the
16	# beginning of the linked list
17	def push(self, new_data):
18
19		# Create a new Node
20		new_node = Node(new_data)
21
22		# 3. Make next of new Node as head
23		new_node.next = self.head
24
25		# 4. Move the head to point to new Node
26		self.head = new_node
27
28	# This Function checks whether the value
29	# x present in the linked list
30	def search(self, x):
31
32		# Initialize current to head
33		current = self.head
34
35		# loop till current not equal to None
36		while current != None:
37			if current.data == x:
38				return True # data found
39
40			current = current.next
41
42		return False # Data Not found
43
44
45# Driver code
46if __name__ == '__main__':
47
48	# Start with the empty list
49	llist = LinkedList()
50	x = 21
51	
52	''' Use push() to construct below list
53		14->21->11->30->10 '''
54	llist.push(10)
55	llist.push(30)
56	llist.push(11)
57	llist.push(21)
58	llist.push(14)
59
60	# Function call
61	if llist.search(x):
62		print("Yes")
63	else:
64		print("No")

جست‌ وجو به روش بازگشتی درون لیست پیوندی

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

• اگر مقدار نشانگر head برابر با NULL بود در خروجی مقدار False را برگردانیم.
• اگر مقدار داده درون head برابر با مقدار X بود، در خروجی True برمی‌گردانیم.
• در غیر از این حالت، به صورت بازگشتی گره بعدی next node  را بررسی می‌کنیم.

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

1class Node:
2
3	# Function to initialise
4	# the node object
5	def __init__(self, data):
6		self.data = data # Assign data
7		self.next = None # Initialize next as null
8
9
10class LinkedList:
11
12	def __init__(self):
13		self.head = None # Initialize head as None
14
15	# This function insert a new node at
16	# the beginning of the linked list
17	def push(self, new_data):
18
19		# Create a new Node
20		new_node = Node(new_data)
21
22		# Make next of new Node as head
23		new_node.next = self.head
24
25		# Move the head to
26		# point to new Node
27		self.head = new_node
28
29	# Checks whether the value key
30	# is present in linked list
31
32	def search(self, li, key):
33
34		# Base case
35		if(not li):
36			return False
37
38		# If key is present in
39		# current node, return true
40		if(li.data == key):
41			return True
42
43		# Recur for remaining list
44		return self.search(li.next, key)
45
46
47# Driver Code
48if __name__ == '__main__':
49
50	li = LinkedList()
51
52	li.push(10)
53	li.push(30)
54	li.push(11)
55	li.push(21)
56	li.push(14)
57
58	x = 21
59
60	# Function call
61	if li.search(li.head, x):
62		print("Yes")
63	else:
64		print("No")

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

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

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

• فیلم آموزش طراحی الگوریتم همراه با حل مثال های عملی در فرادرس
• فیلم آموزش طراحی الگوریتم در کنار مرور و تست کنکور ارشد در فرادرس
• فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته به‌علاوه مرور و تست کنکور ارشد در فرادرس
• فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم فرادرس

تجزیه و تحلیل مصرف منابع در لیست های پیوندی

اگر n برابر با تعداد عناصر لیست پیوندی باشد، برای عملیات مربوط به «دسترسی» (Accessing)، وارد کردن و حذف داده در شروع لیست و جست‌وجو به دنبال عنصری در لیست، پیچیدگی زمانی برابر با O(n) است.

فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته – مرور و تست کنکور ارشد در فرادرس

کلیک کنید

البته پیچیدگی زمانی عملیات «وارد کردن» (Insertion) و «حذف» (Deletion) داده در لیست‌های پیوندی دوطرفه در دو بخش سر و دم لیست برابر با O(1) است. زیرا دسترسی به سر و دم لیست پیوندی دوطرفه به صورت مستقیم ممکن است.

پیچیدگی فضایی برای هر دونوع لیست پیوندی برابر با O(n) است. زیرا هر گره‌ای در لیست نیازمند فضای ذخیره‌سازی برای نگهداری داده و بخش اشاره‌گر به سمت خانه بعدی و شاید هم خانه قبلی است. این روند باعث استفاده از فضای خطی متناسب با تعداد گره‌های لیست می‌شود.

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

پیچیدگی زمانی جست و جو Searching در لیست پیوندی

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

• در بهترین حالت برابر با O(1) است: اگر عنصر در سر لیست پیدا شود، پیچیدگی زمانی برابر با این مقدار می‌شود.
  • در بهترین حالت، عنصر هدف در محل شروع یا سر لیست قرار دارد. پس فقط یک مقایسه برای یافتن جواب لازم است.
• در بدترین حالت برابر با O(n) است: اگر عنصر در انتهای لیست باشد یا اصلا در لیست وجود نداشته باشد این مقدار بدست می‌آید.
  • در بدترین حالت، گره هدف در یکی از دو حالت قرار داشتن در انتهای لیست و وجود نداشتن در لیست است. هر کدام از این دو حالت نیازمند پیمایش کل داده‌های لیست هستند.
• در حالت میانگین برابر با O(n) است: به‌طور میانگین هر عنصر شاید نیاز به بررسی داشته باشد، پس این‌ بار هم همانند بدترین حالت، پیچیدگی زمانی برابر با O(n) است.
  • در حالت میانگین، عنصر هدف در هر موقعیتی در لیست می‌تواند قرار داشته باشد، که در این صورت تقریبا نیازمند پیمایش نیمی از عناصر لیست در هر جست‌وجو هستیم.

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

برای دانستن اینکه مقدار دقیق پیچیدگی زمانی عملیات Insertion در لیست پیوندی چیست، باید هر سه حالت ممکن زیر را در نظر گرفت.

• در بهترین حالت برابر با O(1) است: اگر عنصر را در اول لیست وارد کنیم به این نتیجه می‌رسیم.
  • وارد کردن گره به اول لیست، نیازمند به‌روزرسانی نشانگر head است. برورزسانی این نشانگر در زمان ثابتی انجام می‌پذیرد.
• در بدترین حالت برابر با O(n) است: وارد کردن گره در میانه و انتهای لیست پیوندی نیازمند پیمایش بر روی لیست است.
  • وارد کردن داده در انتها و میانه لیست پیوندی نیازمند اجرای عمل پیمایش برای رسیدن به موقعیت مورد نظر است. پیمایش بر روی لیست شاید نیازمند مشاهده همه عناصر لیست نیز باشد.
• در حالت میانگین برابر با O(n) است: حالت میانگین وارد کردن داده نیز مانند حالت قبل، نیازمند پیمایش عناصر لیست برای رسیدن به خانه مورد نظر است.
  • به صورت میانگین، از آنجا که وارد کردن داده در لیست نیز می‌تواند در هر موقعیتی درون لیست اتفاق بی‌افتد، بنابراین، تقریبا نیازمند پیمایش نیمی از عناصر لیست در هر جست‌وجو هستیم.

پیچیدگی زمانی حذف داده Deletion در لیست پیوندی

برای دانستن اینکه مقدار دقیق پیچیدگی زمانی عملیات Deletion در لیست پیوندی چیست، باید هر سه حالت ممکن زیر را در نظر گرفت.

• در بهترین حالت برابر با O(1) است: اگر عنصر را از اول لیست حذف کنیم به این نتیجه می‌رسیم.
  • حذف کردن گره در اول لیست، نیازمند به‌روزرسانی نشانگر head است. برورزسانی این نشانگر در زمان ثابتی انجام می‌پذیرد.
• در بدترین حالت برابر با O(n) است: حذف کردن گره در میانه و انتهای لیست پیوندی نیازمند پیمایش بر روی لیست است.
  • حذف کردن داده در انتها و میانه لیست پیوندی نیازمند اجرای عمل پیمایش برای رسیدن به موقعیت مورد نظر است. برای پیمایش بر روی لیست شاید لازم شود که همه عناصر را پیمایش کنیم.
• در حالت میانگین برابر با O(n) است: حالت میانگین حذف کردن داده نیز مانند حالت قبل، نیازمند پیمایش عناصر لیست برای رسیدن به خانه مورد نظر است.
  • از آنجا که عنصر هدف، در حالت میانگین، در هر موقعیتی در لیست می‌تواند قرار داشته باشد، تقریبا نیازمند پیمایش نیمی از عناصر لیست در هر جست‌وجو هستیم.

پیچیدگی فضایی کمکی لیست پیوندی

برای اینکه بدانیم «پیچیدگی فضایی کمکی» (Auxiliary Space Complexity) لیست پیوندی چیست باید به این نکته توجه کنیم که لیست‌های پیوندی چقدر حافظه اشغال می‌کنند. عملیات مربوط به لیست پیوندی که در بالا مورد اشاره قرار گرفتن پیچیدگی فضایی در حد O(1) دارند. زیرا این نوع از عملیات به‌جز عددی که در سر جای خودش تثبیت شده به فضای اضافی و اصطلاحا کمکی نیازی ندارند.

اگرچه، برای عملیات خاصی شاید فضای بیشتری به اندازه O(N) لازم باشد. برای مثال، مرتب کردن لیست پیوندی با استفاده از الگوریتم مرتب‌سازی Non-In-Place به این فضای اضافی نیاز خواهد داشت.

مزایا و معایب استفاده از لیست پیوندی چیست؟

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

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

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

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

1. «اندازه پویا» (Dynamic Size): همین‌طور که تخصیص حافظه در زمان اجرای برنامه انجام می‌گیرد، لیست‌های پیوندی نیز می‌توانند به صورت پویا رشد کنند یا جمع شوند.
2. «ورود و حذف داده» (Insertion And Deletion): عملیات مربوط به ورود و حذف داده‌ها در لیست پیوندی به صورت بهینه‌ای انجام می‌پذیرد. این بهینه‌گی به خصوص در زمان کار با لیست‌های بزرگ خود را نشان می‌دهد.
3. «انعطاف‌پذیری» (Flexibility): لیس‌های پیوندی را می‌توان به سادگی اصلاح کرد یا از اول سازماندهی کرد. اجرای این عملیات نیازی به وجود بلاک‌های حافظه‌ای متوالی و بهم چسبیده ندارد.

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

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

• «دسترسی تصادفی» (Random Access): بر خلاف آرایه‌ها، لیست‌های پیوندی اجازه دسترسی مستقیم به عناصرشان را از طریق ایندکس‌ مربوط به هر عنصر نمی‌دهند. برای رسیدن به گره خاصی حتما نیاز داریم که بر روی لیست پیمایش کنیم.
• «حافظه اضافی» (Extra Memory): در مقایسه با آرایه‌ها لیست‌های پیوندی به حافظه اضافی برای نگهداری آدرس اشاره‌گرها نیاز دارند.

جمع بندی

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

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

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