Вступ
Ми працюємо над проєктом з розробки системи розкладу потягів для завантаженої залізничної мережі.
Нас попросили розробити прототип маршрутів потягів для цієї системи розкладу. Кожен маршрут складається з послідовності станцій, на яких зупиняється відповідний потяг.
Вказівки
Наша команда вирішила використовувати двонаправлений звʼязаний список, щоб представити кожен маршрут потяга в розкладі.
Кожну станцію на маршруті потяга представлятиме вузол у звʼязаному списку.
Нам не потрібно перейматися часом прибуття та відправлення на станціях.
Кожну станцію просто представлятиме число.
Маршрути можна подовжувати, додаючи станції на початок або в кінець маршруту.
Їх також можна скорочувати, прибираючи станції з початку або з кінця маршруту.
Іноді станцію закривають, і тоді її потрібно прибрати з маршруту, навіть якщо вона не на початку і не в кінці маршруту.
Розмір маршруту вимірюють не тим, яку відстань долає потяг, а тим, на скількох станціях він зупиняється.
Звʼязаний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують для реалізації інших структур даних.
Як випливає з назви, це список вузлів, зʼєднаних між собою.
Це список «вузлів», де кожен вузол посилається на свого сусіда або сусідів.
У однонаправленому звʼязаному списку кожен вузол посилається лише на вузол, що йде за ним.
У двонаправленому звʼязаному списку кожен вузол посилається і на вузол, що йде перед ним, і на вузол, що йде після нього.
Якщо хочеться глибше зануритися у звʼязані списки, погляньте на цю статтю, де все пояснено за допомогою гарних малюнків.
Як структуровано цю вправу в Python
Хоча звʼязані списки можна реалізувати в різний спосіб і на основі різних структур даних, тут ми просимо реалізувати звʼязаний список в обʼєктно-орієнтованому стилі.
У файлі-заготовці ми побачимо початок класу Node, а також клас LinkedList.
Клас Node має зберігати своє значення, а також те, які вузли стоять перед ним і після нього.
Методи push, pop, shift, unshift і спеціальний метод для len слід реалізувати в класі LinkedList.
Також може стати в пригоді спеціальний метод iter для ітерації.
На відміну від основної вправи, ми будемо тестувати помилкові умови, викликаючи pop і shift на порожніх LinkedList, тож доведеться належним чином застосовувати raise.
Насамкінець, реалізуйте delete на додачу до методів, перелічених вище.
delete приймає один аргумент: значення, яке треба видалити зі звʼязаного списку.
Якщо значення трапляється більше ніж один раз, видаляти слід лише перше входження.
Повідомлення про винятки
Іноді виникає потреба згенерувати виняток. Коли ми так робимо, завжди варто додавати змістовне повідомлення про помилку, яке вказує, у чому джерело помилки.
Це робить код зрозумілішим і дуже допомагає під час налагодження.
Якщо джерело помилки наперед відомого типу, можна викликати один із вбудованих типів помилок, але повідомлення все одно має бути змістовним.
Ця вправа вимагає використати інструкцію raise, щоб «кинути» ValueError, коли значення вузла, яке передали в delete(), не знайдено у звʼязаному списку.
Крім того, слід кинути IndexError, якщо не залишилося вузлів для pop().
Тести пройдуть лише тоді, коли ми викличемо ці exceptions і додамо до них повідомлення.
Щоб викликати 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() для LinkedLists.
Щоб len() працював, потрібно створити спеціальний метод __len__.
Докладніше про реалізацію спеціальних, або «dunder», методів у Python дивіться в Документація Python: базове налаштування обʼєктів та Документація Python: object.len(self).
Також радимо створити спеціальний метод __iter__, який допоможе перебирати звʼязаний список.
Джерело
Класична тема з інформатики
