Треки
/
Tcl
Tcl
/
Вправи
/
Звʼязаний список
Звʼязаний список

Звʼязаний список

Середня

Вступ

Ми працюємо над проєктом з розробки системи розкладу потягів для завантаженої залізничної мережі.

Нас попросили розробити прототип маршрутів потягів для цієї системи розкладу. Кожен маршрут складається з послідовності станцій, на яких зупиняється відповідний потяг.

Вказівки

Наша команда вирішила використовувати двонаправлений звʼязаний список, щоб представити кожен маршрут потяга в розкладі. Кожну станцію на маршруті потяга представлятиме вузол у звʼязаному списку.

Нам не потрібно перейматися часом прибуття та відправлення на станціях. Кожну станцію просто представлятиме число.

Маршрути можна подовжувати, додаючи станції на початок або в кінець маршруту. Їх також можна скорочувати, прибираючи станції з початку або з кінця маршруту.

Іноді станцію закривають, і тоді її потрібно прибрати з маршруту, навіть якщо вона не на початку і не в кінці маршруту.

Розмір маршруту вимірюють не тим, яку відстань долає потяг, а тим, на скількох станціях він зупиняється.

Note

Звʼязаний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують для реалізації інших структур даних. Як випливає з назви, це список вузлів, зʼєднаних між собою. Це список «вузлів», де кожен вузол посилається на свого сусіда або сусідів. У однонаправленому звʼязаному списку кожен вузол посилається лише на вузол, що йде за ним. У двонаправленому звʼязаному списку кожен вузол посилається і на вузол, що йде перед ним, і на вузол, що йде після нього.

Якщо хочеться глибше зануритися у звʼязані списки, погляньте на цю статтю, де все пояснено за допомогою гарних малюнків.

Нотатки щодо реалізації

Ми напишемо реалізацію двобічно звʼязаного списку.

Реалізуйте Node, який зберігатиме значення та посилання на наступний і попередній вузли.

Потім реалізуйте LinkedList, який зберігає посилання на перший і останній вузол і надає подібний до масиву інтерфейс для додавання й видалення елементів:

  • push (додає значення в кінець);
  • pop (видаляє значення з кінця);
  • shift (видаляє значення з початку);
  • unshift (додає значення на початок);
  • delete (видаляє перший вузол, що збігається)

Щоб реалізація залишалася простою, тести не будуть охоплювати помилкові ситуації. Зокрема: pop або shift ніколи не будуть викликані для порожнього списку.


Джерело

Класична тема з інформатики
Редагувати через GitHub Посилання відкривається в новому вікні або вкладці
Tcl Exercism

Час розпочати Звʼязаний список?

Зареєструйтеся на Exercism, щоб вивчати й опановувати Tcl, а також 135 вправ та справжнє наставництво від людей, і все це безкоштовно.