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

Вказівки

Реалізуйте двобічно звʼязаний список.

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

Звʼязаний список - це сукупність елементів даних, які називають вузлами. В однобічно звʼязаному списку кожен вузол містить значення та посилання на наступний вузол. У двобічно звʼязаному списку кожен вузол також містить посилання на попередній вузол.

У цій вправі треба написати реалізацію двобічно звʼязаного списку. Реалізуйте Node, який зберігає значення та вказівники на наступний і попередній вузли. Потім реалізуйте List, який зберігає посилання на перший і останній вузол і надає інтерфейс, схожий на масив, для додавання й видалення елементів:

• push (вставити значення в кінець);
• pop (видалити значення з кінця);
• shift (видалити значення з початку).
• unshift (вставити значення на початок);

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

Докладніше про звʼязані списки у Вікіпедії.