Что такое двунаправленный список?

Что такое двунаправленный список?

Двунаправленный список (doubly linked list) — это структура данных, в которой каждый элемент содержит две ссылки: на следующий элемент (next) и на предыдущий элемент (previous). Это отличается от обычного связного списка, где каждый узел ссылается только на следующий.

Основная структура

class Node:
    def __init__(self, data):
        self.data = data      # Данные узла
        self.next = None      # Ссылка на следующий элемент
        self.prev = None      # Ссылка на предыдущий элемент

Преимущества и недостатки

Преимущества:

• Можно обходить список в обе стороны (вперёд и назад)
• Удаление элемента легче — не нужно хранить предыдущий элемент отдельно
• Быстрая навигация к соседним элементам

Недостатки:

• Требует больше памяти (две ссылки вместо одной)
• Сложнее в реализации
• Медленнее при простых операциях по сравнению с массивом

Реализация двунаправленного списка

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    
    # Добавление элемента в начало
    def add_front(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    
    # Добавление элемента в конец
    def add_back(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        
        current.next = new_node
        new_node.prev = current
    
    # Удаление элемента по значению
    def delete(self, data):
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                
                if current.next:
                    current.next.prev = current.prev
                return True
            current = current.next
        return False
    
    # Обход вперёд
    def traverse_forward(self):
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result
    
    # Обход назад
    def traverse_backward(self):
        result = []
        current = self.head
        if current is None:
            return result
        
        # Доходим до конца
        while current.next:
            current = current.next
        
        # Идём назад
        while current:
            result.append(current.data)
            current = current.prev
        return result

Пример использования

dll = DoublyLinkedList()
dll.add_back(1)
dll.add_back(2)
dll.add_back(3)
dll.add_front(0)

print("Вперёд:", dll.traverse_forward())    # [0, 1, 2, 3]
print("Назад:", dll.traverse_backward())    # [3, 2, 1, 0]

dll.delete(2)
print("После удаления 2:", dll.traverse_forward())  # [0, 1, 3]

Сравнение со связным списком

Практическое применение

1. Кэширование (LRU Cache) — двусторонний обход для быстрого удаления старых данных
2. Браузер — история навигации (forward/back)
3. Плейлист музыки — перемотка вперёд/назад
4. Undo/Redo — навигация по истории действий
5. Балансирующие очереди — добавление с обоих концов

В Python: встроенные альтернативы

Для большинства задач вместо самописного двунаправленного списка используют:

from collections import deque

# deque поддерживает эффективные операции с обоих концов
dq = deque([1, 2, 3])
dq.appendleft(0)
dq.append(4)
print(list(dq))  # [0, 1, 2, 3, 4]

# Обход в разные стороны
for item in dq:          # вперёд
    print(item)

for item in reversed(dq):  # назад
    print(item)

Вывод: Двунаправленный список — мощный инструмент для задач, требующих навигации в обе стороны. Хотя в современном Python часто используют встроенные структуры (deque, list), понимание внутреннего устройства двунаправленного списка критично для собеседований и оптимизации сложных систем.