لیست پیوندی

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

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

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

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

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

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

ساختار این تمرین در مسیر C++

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

در فایل linked_list_test.cpp خواهید دید که یک کلاس List قالبی فراخوانی می‌شود. از شما انتظار می‌رود این کلاس را با توابع عضو زیر بنویسید:

• push یک عنصر را به انتهای لیست اضافه می‌کند،
• pop آخرین عنصر لیست را حذف می‌کند و برمی‌گرداند،
• shift اولین عنصر لیست را حذف می‌کند و برمی‌گرداند،
• unshift یک عنصر را به ابتدای لیست اضافه می‌کند،
• count تعداد کل عناصر لیست جاری را برمی‌گرداند.

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

هرچند Test نمی‌شود، ممکن است بخواهید اگر pop و shift روی یک List خالی فراخوانی شوند، یک استثنا پرتاب کنید.