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

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

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

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

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

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

هرچند stacks و queues را می‌توان با lists، collections.deque، queue.LifoQueue و multiprocessing.Queue پیاده‌سازی کرد، این تمرین انتظار یک پشته‌ی «آخرین ورودی، اولین خروجی» (LIFO) را دارد که با یک فهرست پیوندی یک‌طرفه دست‌ساز ساخته شده باشد:

این را نباید با پشته‌ی LIFO که از یک آرایه یا فهرست پویا استفاده می‌کند اشتباه گرفت؛ آن یکی ممکن است در زیر از list، queue یا array بهره ببرد. stacksهای مبتنی بر آرایه‌ی پویا موقعیت head متفاوتی دارند و پیچیدگی زمانی (Big-O) و مصرف حافظه‌ی متفاوتی هم دارند.

برای دیدن چند نکته‌ی قابل توجه، این دو پرسش Stack Overflow را ببینید: پشته‌ها و صف‌های مبتنی بر آرایه در برابر مبتنی بر فهرست و تفاوت‌های پشته‌ی آرایه‌ای، پشته‌ی پیوندی و پشته. برای جزئیات بیشتر درباره‌ی فهرست‌های پیوندی، پشته‌های LIFO و دیگر انواع داده‌ی انتزاعی (ADT) در Python:

• Baeldung: ساختارهای داده‌ی فهرست پیوندی (چندین پیاده‌سازی را پوشش می‌دهد)
• Geeks for Geeks: پشته با فهرست پیوندی
• Mosh: ساختارهای داده‌ی انتزاعی (بسیاری از ADTها را پوشش می‌دهد، نه فقط فهرست‌های پیوندی)

کلاس‌ها در Python

پیاده‌سازی «متعارف» یک فهرست پیوندی در Python معمولاً به یک یا چند classes نیاز دارد. برای آشنایی خوب با classes، classes و تمرین همراه آن ellens-alien-game را ببینید، یا بخش کلاس‌ها در آموزش رسمی Python.

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

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

ساخت یک تکرارکننده

برای پشتیبانی از حلقه زدن روی LinkedList یا معکوس کردن آن، باید متد ویژه‌ی __iter__ را پیاده‌سازی کنید. برای جزئیات پیاده‌سازی، پیاده‌سازی یک تکرارکننده برای یک کلاس را ببینید.

سفارشی‌سازی و پرتاب استثناها

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

استثناهای سفارشی را می‌توان از طریق کلاس‌های استثنای تازه ساخت (برای جزئیات بیشتر classes را ببینید) که معمولاً زیرکلاس‌هایی از Exception هستند.

برای موقعیت‌هایی که می‌دانید منبع خطا مشتقی از یک نوع استثنای مشخص خواهد بود، می‌توانید ارث‌بری از یکی از built in error types زیر کلاس Exception را انتخاب کنید. هنگام پرتاب خطا، باز هم باید یک پیام معنادار بگنجانید.

این تمرین خاص می‌خواهد که یک استثنای سفارشی بسازید تا وقتی فهرست پیوندی‌تان خالی است، پرتاب/«thrown» شود. testها فقط زمانی قبول می‌شوند که استثناهای مناسب را سفارشی کنید، آن استثناها را raise کنید و پیام‌های خطای مناسب را بگنجانید.

برای سفارشی‌سازی یک استثنای عمومی، یک class بسازید که از Exception ارث‌بری کند. هنگام پرتاب استثنای سفارشی همراه با یک پیام، پیام را به عنوان آرگومان به نوع exception بدهید:

# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
    """Exception raised when the linked list is empty.

    message: explanation of the error.

    """
    def __init__(self, message):
        self.message = message

# raising an EmptyListException
raise EmptyListException("The list is empty.")

---

منبع

با الهام از «Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby»، لیست‌های پیوندی یک‌طرفه.