Двусвязный список

Двусвязный список хранит в каждом узле ссылки и на следующий, и на предыдущий элемент. Это позволяет удалять узел за O(1), если он уже известен, и обходить список в обе стороны.

Сложность: вставка/удаление при известном узле — O(1); доступ по индексу — O(n). Память: O(n) с двумя ссылками на узел. На таком списке часто строят дек и LRU-кэш.

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

# удаление узла за O(1), если есть ссылка на него
def remove(node):
    if node.prev: node.prev.next = node.next
    if node.next: node.next.prev = node.prev