لیست پیوندی

دستورالعمل‌ها

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

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

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

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

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

ساختار این تمرین در Python

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

در فایل اولیه، ابتدای یک کلاس Node و همچنین یک کلاس LinkedList را می‌بینید. کلاس Node شما باید مقدار خود و نیز گره‌هایی را که پیش یا پس از آن می‌آیند ردیابی کند. متدهای push، pop، shift، unshift و متد ویژه‌ی len باید در کلاس LinkedList پیاده‌سازی شوند. شاید پیاده‌سازی یک متد ویژه‌ی iter هم برای پیمایش به کارتان بیاید.

برخلاف تمرین اصلی، ما شرایط خطا را با فراخوانی pop و shift روی LinkedLists خالی آزمایش می‌کنیم؛ بنابراین باید خطاها را به‌شکل مناسب raise کنید.

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

پیام‌های استثنا

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

این تمرین به‌طور خاص می‌خواهد که با دستور raise یک ValueError را «پرتاب کنید» وقتی مقداری که با delete() حذف می‌شود در لیست پیوندی پیدا نمی‌شود. به‌علاوه، اگر گرهی برای pop() باقی نمانده باشد، باید یک IndexError پرتاب شود. آزمون‌ها تنها در صورتی قبول می‌شوند که هم این exceptions را raise کنید و هم پیام‌هایی همراهشان بگنجانید.

برای مطرح کردن یک ValueError همراه با پیام، پیام را به‌عنوان آرگومان به نوع exception بدهید:

# When the value passed to `delete()` is not found.
if not found:
    raise ValueError("Value not found")

برای مطرح کردن یک IndexError همراه با پیام، پیام را به‌عنوان آرگومان به نوع exception بدهید:

# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
    raise IndexError("List is empty")

متدهای ویژه در Python

آزمون‌های این تمرین همچنین len() را روی LinkedList شما فراخوانی می‌کنند. برای اینکه len() کار کند، باید یک متد ویژه‌ی __len__ بسازید. برای جزئیات پیاده‌سازی متدهای ویژه یا «dunder» در Python، به مستندات Python: سفارشی‌سازی پایه‌ی شیء و مستندات Python: object.len(self) نگاه کنید.

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