Ответ
Двунаправленный (или двусвязный) список — это линейная структура данных, похожая на односвязный список, но с одним ключевым отличием: каждый узел хранит ссылки не только на следующий элемент, но и на предыдущий.
Структура узла:
... ↔ [ prev | data | next ] ↔ ...
Это позволяет обходить список в обоих направлениях: от начала к концу и от конца к началу.
Преимущества перед односвязным списком
- Двусторонний обход: Возможность двигаться в обе стороны.
- Эффективное удаление: Если есть указатель на узел, его можно удалить за
O(1), так как не нужно искать предыдущий элемент для перенаправления ссылок. - Простая вставка: Вставка до или после заданного узла выполняется за
O(1).
Недостатки
- Дополнительная память: Каждый узел хранит дополнительный указатель
prev, что увеличивает расход памяти. - Более сложная реализация: Операции вставки и удаления требуют обновления большего количества ссылок, что повышает вероятность ошибки.
Пример реализации на Python
class Node:
def __init__(self, data):
self.data = data
self.next = None # Ссылка на следующий узел
self.prev = None # Ссылка на предыдущий узел
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# Добавление элемента в конец списка
def append(self, data):
new_node = Node(data)
if self.head is None:
# Если список пуст, новый узел становится и головой, и хвостом
self.head = new_node
self.tail = new_node
return
# Связываем новый узел с текущим хвостом
self.tail.next = new_node
new_node.prev = self.tail
# Перемещаем указатель хвоста на новый узел
self.tail = new_node