What is a Doubly Linked List?

Двусвязный список — это последовательность узлов, где каждый узел содержит значение и два указателя: prev на предыдущий узел и next на следующий узел. Сам список отслеживает оба конца: head (первый узел) и tail (последний узел).

Наличие двух указателей в каждом узле и дополнительной ссылки tail дает нам много преимуществ. Добавление в конец теперь выполняется за O(1) (переход сразу к tail вместо перебора всей цепочки), и удаление последнего узла также выполняется за O(1) (потому что мы можем получить доступ к предпоследнему узлу через tail.prev). Обратной стороной является больший расход памяти на каждый узел, а также необходимость синхронизации большего количества указателей при каждой вставке и удалении.

Пять основных операций в двусвязном списке:

1. AddFirst: Добавить значение в начало списка.
2. AddLast: Добавить значение в конец списка (O(1)!).
3. Get: Вернуть значение по заданному индексу.
4. RemoveLast: Удалить последний узел (O(1)!).
5. Size: Вернуть количество хранящихся в данный момент узлов.

Давайте сначала создадим класс Node, а затем построим DoublyLinkedList на его основе!