لیست پیوندی در پایتون – Linked List in Python

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

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

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

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

 

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

 

برای تعریف یک لیست پیوندی ابتدا به یک کلاس گره (Node) نیاز داریم تا داده‌هایمان را در آن ذخیره کنیم و همچنین آدرس به گره بعدی را نگه داریم. برای این منظور کد پایتون زیر را نوشته‌ایم:

این کلاس دو ویژگی برای ذخیره داده‌ و آدرس گره بعدی دارد. همچنین چهار عملگر برای خواند و نوشتن آن دو ویژگی دارد.

 

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

حالا که ویژگی کلاس Link List را تعریف کردیم، به ترتیب به عملگرهای (متد) این کلاس می‌پردازیم. اولین عملگری که برای کلاس لیست پیوندی می‌نویسیم، یک تابع برای شماردن تعداد گره‌های درون لیست است. این کار را با استفاده از کد زیر انجام می‌دهیم:

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

 

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

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

 

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

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

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

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

 

متد آخر نیز برای چاپ اطلاعات درون لیست پیوندی به ترتیب محل قرارگیری آن‌ها درون لیست پیوندی است:

 

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

سپس یک گره (Node) به لیست پیوندی اضافه می‌کنیم و بعد از آن لیست‌پیوندی و اندازه آن را چاپ می‌کنیم:

خروجی این قسمت از کد برابر می‌شود با

در ادامه ۵ گره دیگر با مقدارهای متفاوت به لیست پیوندی اضافه می‌کنیم و در گام لیست‌ پیوندی و اندازه‌اش را چاپ می‌کنیم:

خروجی این تکه کد برابر زیر است:

اکنون مقدار‌های مختلف را در لیست پیوندی جست‌وجو می‌کنیم تا اندیس گره‌های متناظر با آن‌ها را در صورت موجود بودن پیدا کنیم:

خروجی این تکه کد را در زیر مشاهده می‌کنید:

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

خروجی این تکه کد در زیر آورده شده است:

 

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

 

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

 

 

 

 

 

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *