Зачем второй указатель

В прошлом уроке мы видели проблему singly linked: чтобы удалить элемент зная только его узел, нужно найти предыдущий узел, обойдя список с head. Это O(n).

Doubly linked list решает это, добавляя в каждый узел указатель на предыдущий:

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

    def __init__(self, value, prev=None, next_=None):
        self.value = value
        self.prev = prev
        self.next = next_

Теперь узел знает обоих соседей. И операция «убрать узел из списка», если у тебя на руках указатель на этот узел, — O(1):

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

Две перестановки указателей — и узел исключён из цепочки. Не нужно искать предыдущий — он сам у тебя.

Полная реализация

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

    def __init__(self, value, prev=None, next_=None):
        self.value = value
        self.prev = prev
        self.next = next_


class DoublyLinkedList:
    __slots__ = ('head', 'tail', 'size')

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def push_front(self, value):
        node = DNode(value, next_=self.head)
        if self.head is not None:
            self.head.prev = node
        else:
            self.tail = node
        self.head = node
        self.size += 1
        return node

    def push_back(self, value):
        node = DNode(value, prev=self.tail)
        if self.tail is not None:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self.size += 1
        return node

    def pop_front(self):
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        if self.head is not None:
            self.head.prev = None
        else:
            self.tail = None
        self.size -= 1
        return node.value

    def pop_back(self):
        """Теперь O(1) — спасибо prev."""
        if self.tail is None:
            raise IndexError("pop from empty list")
        node = self.tail
        self.tail = node.prev
        if self.tail is not None:
            self.tail.next = None
        else:
            self.head = None
        self.size -= 1
        return node.value

    def remove(self, node):
        """Удаление по указателю на узел — O(1)."""
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self.size -= 1

Ключевая операция — remove(node). Она работает за константу, если у тебя уже есть node. В этом главное преимущество doubly linked.

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

Память: цена второго указателя

В Python:

import sys

class SinglyNode:
    __slots__ = ('value', 'next')

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

s = SinglyNode()
d = DoublyNode()
print(f"singly node: {sys.getsizeof(s)} bytes")
print(f"doubly node: {sys.getsizeof(d)} bytes")

Обычно singly ~48 байт, doubly ~56-64 байта. На 1M узлов разница ~8-16 MB. В C/Rust разница чище: 16 байт (value + next) vs 24 байта (value + prev + next).

Это плата за O(1) remove. Если ваша задача не требует удаления по узлу — берите singly, чтобы сэкономить.

Применение: LRU cache

Главный практический случай doubly linked — LRU (Least Recently Used) cache. Это структура с двумя операциями:

• get(key) — найти значение по ключу, отметить как «недавно использованное».
• put(key, value) — добавить пару. Если cache полон, выбросить наименее использованную.

Реализация: dict + doubly linked list.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}  # key -> DNode
        self.list = DoublyLinkedList()

    def get(self, key):
        if key not in self.map:
            return None
        node = self.map[key]
        # передвигаем к head — это самое «свежее»
        self.list.remove(node)
        moved = self.list.push_front(node.value)
        self.map[key] = moved
        return moved.value[1]  # value хранится как (key, value)

    def put(self, key, value):
        if key in self.map:
            old = self.map[key]
            self.list.remove(old)

        new_node = self.list.push_front((key, value))
        self.map[key] = new_node

        if len(self.map) > self.capacity:
            # выкидываем последний (наименее использованный)
            tail_key, _ = self.list.pop_back()
            del self.map[tail_key]

Каждая операция — O(1):

• get: dict lookup O(1) + remove(node) O(1) + push_front O(1).
• put: dict lookup O(1) + remove(node) O(1) + push_front O(1) + (опционально) pop_back O(1).

Без doubly linked это было бы сложно: чтобы передвинуть узел к head, нужно его удалить — а для удаления в singly нужен предыдущий узел, O(n).

Защитный случай: пустой список и единственный элемент

Когда вы добавляете/удаляете узлы, надо аккуратно поддерживать инварианты:

• head is None <=> tail is None <=> size == 0
• Если узлов больше 0, head.prev is None и tail.next is None.

Многие баги в реализации doubly linked — это забытые перестановки указателей на границах. Чтобы упростить, иногда используют sentinel-узлы: фиктивный узел перед head и после tail. Тогда не нужно проверять None.

class DLLWithSentinel:
    def __init__(self):
        self.head_sentinel = DNode(None)
        self.tail_sentinel = DNode(None)
        self.head_sentinel.next = self.tail_sentinel
        self.tail_sentinel.prev = self.head_sentinel
        self.size = 0

    def push_front(self, value):
        # вставка между head_sentinel и его текущим next
        first = self.head_sentinel.next
        node = DNode(value, prev=self.head_sentinel, next_=first)
        self.head_sentinel.next = node
        first.prev = node
        self.size += 1

С sentinel’ом любая операция — это «вставка между двумя узлами», без специальных кейсов для пустого списка. Это стиль из C/Java, часто видна в production-коде.

Попробуй сам

Реализуйте detect-cycle через два указателя (slow и fast). Cycle — это когда next в цепочке возвращает в уже посещённый узел:

def has_cycle(head):
    """Floyd's cycle detection algorithm — O(n) время, O(1) память."""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# тест: соберём цикл
n1 = DNode(1)
n2 = DNode(2)
n3 = DNode(3)
n1.next = n2
n2.next = n3
n3.next = n1   # цикл!

print(has_cycle(n1))   # True

Этот алгоритм работает на любом linked list (singly или doubly). Если slow и fast встретились — есть цикл; если fast достиг None — цикла нет. Полезно при отладке: если ваш linked list внезапно бесконечно итерируется, проверьте has_cycle.