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

Коротко

Главное отличие в третьей строке: имея ссылку на узел, двусвязный список удаляет его мгновенно. Именно поэтому он лежит в основе LRU-кэша.

Устройство

Каждый узел хранит значение и две ссылки: на следующий узел и на предыдущий.

None ← [ 10 ] ⇄ [ 20 ] ⇄ [ 30 ] → None
        head                tail

В односвязном списке ссылка только вперёд. Чтобы удалить узел, нужно знать предыдущий — а чтобы его найти, придётся пройти список с начала. Отсюда O(n).

В двусвязном предыдущий узел известен сразу: node.prev. Удаление сводится к переброске двух ссылок.

Фиктивные узлы: приём, который убирает половину багов

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

Решение — завести два фиктивных узла, head и tail, которые не хранят данных и никогда не удаляются. Реальные узлы всегда находятся между ними.

[head] ⇄ [ 10 ] ⇄ [ 20 ] ⇄ [tail]
 фикт.                        фикт.

Теперь у любого реального узла гарантированно есть и prev, и next. Проверки на None исчезают полностью.

Реализация на Python

class Node:
    __slots__ = ('value', 'prev', 'next')

    def __init__(self, value=None) -> None:
        self.value = value
        self.prev: 'Node | None' = None
        self.next: 'Node | None' = None


class DoublyLinkedList:
    def __init__(self) -> None:
        # фиктивные границы — реальные узлы всегда между ними
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0

    def __len__(self) -> int:
        return self._size

    def append(self, value) -> Node:
        """Добавить в конец за O(1)."""
        return self._insert_before(self.tail, value)

    def appendleft(self, value) -> Node:
        """Добавить в начало за O(1)."""
        return self._insert_before(self.head.next, value)

    def _insert_before(self, node: Node, value) -> Node:
        new = Node(value)
        prev = node.prev

        new.prev = prev
        new.next = node
        prev.next = new
        node.prev = new

        self._size += 1
        return new

    def remove(self, node: Node) -> None:
        """Удалить узел за O(1) — нужна только ссылка на него."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None   # помогаем сборщику мусора
        self._size -= 1

    def __iter__(self):
        current = self.head.next
        while current is not self.tail:
            yield current.value
            current = current.next

    def __reversed__(self):
        current = self.tail.prev
        while current is not self.head:
            yield current.value
            current = current.prev


lst = DoublyLinkedList()
lst.append(10)
node20 = lst.append(20)
lst.append(30)

print(list(lst))            # [10, 20, 30]
print(list(reversed(lst)))  # [30, 20, 10]

lst.remove(node20)          # O(1) — узел известен
print(list(lst))            # [10, 30]

Обратите внимание на порядок присваиваний в _insert_before. Сначала настраиваем ссылки нового узла, потом переписываем ссылки соседей. Если сделать наоборот, потеряется указатель на prev, и список порвётся.

Почему remove принимает узел, а не значение

Это принципиальный момент. Удаление по значению требует поиска — O(n), и никакого преимущества перед односвязным списком нет.

Вся сила двусвязного списка проявляется, когда ссылка на узел уже есть. Откуда она берётся? Обычно из хеш-таблицы: ключ → узел. Такая связка и даёт LRU-кэш с операциями за O(1).

# схема LRU-кэша
cache = {}                # ключ -> Node
order = DoublyLinkedList()

node = cache[key]         # O(1) — нашли узел
order.remove(node)        # O(1) — вырвали из списка
order.appendleft(value)   # O(1) — вернули в начало

Обнуление ссылок при удалении

Строка node.prev = node.next = None выглядит необязательной — узел ведь уже выброшен из списка. Но она важна по двум причинам.

Сборка мусора. Если удалённый узел где-то ещё хранится, через его ссылки остаётся доступен весь список, и он не освободится.

Отлов ошибок. Попытка использовать удалённый узел упадёт с AttributeError вместо того, чтобы молча испортить структуру.

Где применяется

LRU-кэш — каноническое применение, разобрано выше.

История переходов в браузере: вперёд и назад — это ровно next и prev.

collections.deque в Python реализована на основе двусвязного списка блоков, что даёт O(1) на добавление и удаление с обоих концов.

Отмена действий (undo/redo) в редакторах.

Планировщики задач в операционных системах, где процессы нужно быстро перемещать между очередями.

Сравнение с массивом

Практический вывод: список выигрывает только тогда, когда вы часто вставляете и удаляете в середине, имея ссылку на нужное место. Во всех остальных случаях массив быстрее за счёт локальности памяти — даже там, где асимптотика говорит обратное.

Частые ошибки

Неправильный порядок переприсваивания. Классика: сначала затёрли node.prev, потом попытались через него добраться до соседа. Всегда сохраняйте нужные ссылки в переменные до изменений.

Отсутствие фиктивных узлов. Приводит к разрастанию кода проверками и ошибкам на границах — при удалении единственного элемента, первого или последнего.

Удаление по значению вместо ссылки. Превращает O(1) в O(n) и обесценивает всю структуру.

Забытое обновление размера. Мелочь, но __len__ начинает врать, и ошибка всплывает далеко от места.

Что запомнить

• Каждый узел хранит ссылки и вперёд, и назад.
• Удаление узла по ссылке — O(1), это главное преимущество перед односвязным списком.
• Фиктивные head и tail убирают все проверки на пустоту и границы.
• Связка «хеш-таблица + двусвязный список» — основа LRU-кэша.
• Обнуляйте ссылки удалённого узла: это помогает сборщику мусора и ловит ошибки.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→