Вступ
Ми працюємо в компанії, що займається потоковим передаванням музики.
Наше завдання - створити можливість плейлистів для застосунку музичного плеєра.
Вказівки
Напишіть прототип застосунку музичного плеєра.
Для прототипу кожна пісня просто позначається числом.
Маючи діапазон чисел (ідентифікатори пісень), створіть однозвʼязний список.
Маючи однозвʼязний список, ми повинні мати змогу розвернути його, щоб відтворити пісні у зворотному порядку.
Звʼязний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують у реалізації інших структур даних.
Найпростіший різновид звʼязного списку - однозвʼязний список.
Це означає, що кожен елемент (або «вузол») містить дані та щось, що вказує на наступний вузол у списку.
Якщо ми хочемо заглибитися у звʼязні списки, варто поглянути на цю статтю, де все пояснено за допомогою гарних малюнків.
Як ця вправа побудована в Python
Хоча stacks і queues можна реалізувати за допомогою lists, collections.deque, queue.LifoQueue і multiprocessing.Queue, ця вправа передбачає стек «останнім прийшов, першим вийшов» (LIFO), побудований на власноруч створеному однозвʼязному списку:
Не варто плутати це з LIFO стеком на основі динамічного масиву чи списку, який під капотом може використовувати list, queue або array.
У stacks, побудованих на динамічному масиві, інша позиція head, інша часова складність (Big-O) та інший обсяг памʼяті.
Ось два питання на Stack Overflow, які варто взяти до уваги: Стеки та черги на основі масиву проти списку і Різниця між стеком на масиві, стеком на звʼязаному списку та стеком.
Докладніше про звʼязані списки, LIFO стеки та інші абстрактні типи даних (ADT) у Python:
Класи в Python
«Канонічна» реалізація звʼязаного списку в Python зазвичай вимагає одного або кількох classes.
Щоб добре познайомитися з classes, зазирнімо до classes та супутньої вправи ellens-alien-game, або до розділу про класи в офіційному туторіалі Python.
Спеціальні методи в Python
Тести цієї вправи викликатимуть len() для нашого LinkedList.
Щоб len() працював, нам потрібно буде створити спеціальний метод __len__.
Докладніше про реалізацію спеціальних, або «dunder», методів у Python можна дізнатися з Документація Python: базове налаштування обʼєктів та Документація Python: object.len(self).
Створення ітератора
Щоб мати змогу перебирати наш LinkedList у циклі або розвертати його, потрібно реалізувати спеціальний метод __iter__.
Подробиці реалізації можна знайти тут: реалізація ітератора для класу.
Налаштування та збудження винятків
Іноді в коді доводиться і налаштовувати, і raise винятки.
Коли ми це робимо, завжди варто додавати змістовне повідомлення про помилку, яке вказує, що стало її джерелом.
Це робить код зрозумілішим і суттєво допомагає з налагодженням.
Власні винятки можна створювати за допомогою нових класів винятків (докладніше про classes), які зазвичай є підкласами Exception.
Якщо відомо, що джерело помилки буде похідним від певного типу винятку, можна успадкуватися від одного з built in error types під класом Exception.
Коли ми збуджуємо помилку, все одно варто додати змістовне повідомлення.
У цій конкретній вправі потрібно створити власний виняток, який буде збуджено/«кинуто», коли наш звʼязаний список порожній.
Тести пройдуть лише тоді, коли ми налаштуємо відповідні винятки, збудимо їх за допомогою 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.")
