Вступ
Ми працюємо над проєктом з розробки системи розкладу потягів для завантаженої залізничної мережі.
Нас попросили розробити прототип маршрутів потягів для цієї системи розкладу. Кожен маршрут складається з послідовності станцій, на яких зупиняється відповідний потяг.
Вказівки
Наша команда вирішила використовувати двонаправлений звʼязаний список, щоб представити кожен маршрут потяга в розкладі.
Кожну станцію на маршруті потяга представлятиме вузол у звʼязаному списку.
Нам не потрібно перейматися часом прибуття та відправлення на станціях.
Кожну станцію просто представлятиме число.
Маршрути можна подовжувати, додаючи станції на початок або в кінець маршруту.
Їх також можна скорочувати, прибираючи станції з початку або з кінця маршруту.
Іноді станцію закривають, і тоді її потрібно прибрати з маршруту, навіть якщо вона не на початку і не в кінці маршруту.
Розмір маршруту вимірюють не тим, яку відстань долає потяг, а тим, на скількох станціях він зупиняється.
Звʼязаний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують для реалізації інших структур даних.
Як випливає з назви, це список вузлів, зʼєднаних між собою.
Це список «вузлів», де кожен вузол посилається на свого сусіда або сусідів.
У однонаправленому звʼязаному списку кожен вузол посилається лише на вузол, що йде за ним.
У двонаправленому звʼязаному списку кожен вузол посилається і на вузол, що йде перед ним, і на вузол, що йде після нього.
Якщо хочеться глибше зануритися у звʼязані списки, погляньте на цю статтю, де все пояснено за допомогою гарних малюнків.
Реалізація
Напишіть реалізацію двозвʼязного списку.
Реалізуйте Node, щоб зберігати значення та вказівники на наступний і попередній вузли.
Потім реалізуйте List, який зберігає посилання на перший і останній вузол і надає функції для додавання та вилучення елементів.
Node має містити такі поля та методи:
-
Value: значення вузла (використаємо any).
-
Next() *Node: вказівник на наступний вузол.
-
Prev() *Node: вказівник на попередній вузол.
Має бути функція NewList(), яка створює й повертає List:
-
NewList(args ...any) *List: створює новий звʼязаний список, зберігаючи порядок значень.
List має містити такі методи:
-
First() *Node: повертає вказівник на перший вузол (голову).
-
Last() *Node: повертає вказівник на останній вузол (хвіст).
-
Push(v any): вставляє значення в кінець списку.
-
Pop() (any, error): вилучає значення з кінця списку.
-
Unshift(v any): вставляє значення на початок списку.
-
Shift() (any, error): вилучає значення з початку списку.
-
Reverse(): обертає звʼязаний список.
Джерело
Класична тема з інформатики
