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

Отличие от односвязного

В двусвязном списке каждый узел хранит ссылки на следующий и предыдущий узлы. Это позволяет перемещаться в обоих направлениях.

Односвязный:
[1] -> [2] -> [3] -> [4] -> null
 head

Двусвязный:
null <- [1] <-> [2] <-> [3] <-> [4] -> null
         head                     tail

Структура узла

class DListNode
{
    public function __construct(
        public int $val = 0,
        public ?DListNode $prev = null,
        public ?DListNode $next = null,
    ) {}
}

type DListNode struct {
    Val  int
    Prev *DListNode
    Next *DListNode
}

func NewDListNode(val int) *DListNode {
    return &DListNode{Val: val}
}

public class DListNode(int val = 0, DListNode? prev = null, DListNode? next = null)
{
    public int Val { get; set; } = val;
    public DListNode? Prev { get; set; } = prev;
    public DListNode? Next { get; set; } = next;
}

from __future__ import annotations

from dataclasses import dataclass, field

@dataclass
class DListNode:
    val: int = 0
    prev: DListNode | None = field(default=None, repr=False)
    next: DListNode | None = field(default=None, repr=False)

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

class DoublyLinkedList
{
    private DListNode $head; // sentinel
    private DListNode $tail; // sentinel
    private int $size = 0;

    public function __construct()
    {
        // Sentinel nodes (dummy boundaries)
        $this->head = new DListNode(0);
        $this->tail = new DListNode(0);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    /** Insert at the beginning — O(1) */
    public function addFirst(int $val): void
    {
        $node = new DListNode($val);
        $node->next = $this->head->next;
        $node->prev = $this->head;
        $this->head->next->prev = $node;
        $this->head->next = $node;
        $this->size++;
    }

    /** Insert at the end — O(1) */
    public function addLast(int $val): void
    {
        $node = new DListNode($val);
        $node->prev = $this->tail->prev;
        $node->next = $this->tail;
        $this->tail->prev->next = $node;
        $this->tail->prev = $node;
        $this->size++;
    }

    /** Remove a specific node — O(1) */
    public function remove(DListNode $node): void
    {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
        $this->size--;
    }

    /** Remove from the beginning — O(1) */
    public function removeFirst(): ?int
    {
        if ($this->size === 0) {
            return null;
        }
        $node = $this->head->next;
        $this->remove($node);
        return $node->val;
    }

    /** Remove from the end — O(1) */
    public function removeLast(): ?int
    {
        if ($this->size === 0) {
            return null;
        }
        $node = $this->tail->prev;
        $this->remove($node);
        return $node->val;
    }

    /** Traverse forward */
    public function printForward(): void
    {
        $current = $this->head->next;
        while ($current !== $this->tail) {
            echo $current->val . ' <-> ';
            $current = $current->next;
        }
        echo "null\n";
    }

    /** Traverse backward */
    public function printBackward(): void
    {
        $current = $this->tail->prev;
        while ($current !== $this->head) {
            echo $current->val . ' <-> ';
            $current = $current->prev;
        }
        echo "null\n";
    }
}

type DoublyLinkedList struct {
    head *DListNode // sentinel
    tail *DListNode // sentinel
    size int
}

func NewDoublyLinkedList() *DoublyLinkedList {
    // Sentinel nodes (dummy boundaries)
    head := &DListNode{}
    tail := &DListNode{}
    head.Next = tail
    tail.Prev = head
    return &DoublyLinkedList{head: head, tail: tail}
}

// AddFirst inserts at the beginning — O(1)
func (dl *DoublyLinkedList) AddFirst(val int) {
    node := &DListNode{Val: val}
    node.Next = dl.head.Next
    node.Prev = dl.head
    dl.head.Next.Prev = node
    dl.head.Next = node
    dl.size++
}

// AddLast inserts at the end — O(1)
func (dl *DoublyLinkedList) AddLast(val int) {
    node := &DListNode{Val: val}
    node.Prev = dl.tail.Prev
    node.Next = dl.tail
    dl.tail.Prev.Next = node
    dl.tail.Prev = node
    dl.size++
}

// Remove removes a specific node — O(1)
func (dl *DoublyLinkedList) Remove(node *DListNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    dl.size--
}

// RemoveFirst removes from the beginning — O(1)
func (dl *DoublyLinkedList) RemoveFirst() (int, bool) {
    if dl.size == 0 {
        return 0, false
    }
    node := dl.head.Next
    dl.Remove(node)
    return node.Val, true
}

// RemoveLast removes from the end — O(1)
func (dl *DoublyLinkedList) RemoveLast() (int, bool) {
    if dl.size == 0 {
        return 0, false
    }
    node := dl.tail.Prev
    dl.Remove(node)
    return node.Val, true
}

// PrintForward traverses forward
func (dl *DoublyLinkedList) PrintForward() {
    current := dl.head.Next
    for current != dl.tail {
        fmt.Printf("%d <-> ", current.Val)
        current = current.Next
    }
    fmt.Println("nil")
}

// PrintBackward traverses backward
func (dl *DoublyLinkedList) PrintBackward() {
    current := dl.tail.Prev
    for current != dl.head {
        fmt.Printf("%d <-> ", current.Val)
        current = current.Prev
    }
    fmt.Println("nil")
}

public class DoublyLinkedList
{
    private DListNode _head = new(); // sentinel
    private DListNode _tail = new(); // sentinel
    private int _size;

    public DoublyLinkedList()
    {
        // Sentinel nodes (dummy boundaries)
        _head.Next = _tail;
        _tail.Prev = _head;
    }

    public int Count => _size;

    // Insert at the beginning — O(1)
    public void AddFirst(int val)
    {
        var node = new DListNode(val);
        node.Next = _head.Next;
        node.Prev = _head;
        _head.Next!.Prev = node;
        _head.Next = node;
        _size++;
    }

    // Insert at the end — O(1)
    public void AddLast(int val)
    {
        var node = new DListNode(val);
        node.Prev = _tail.Prev;
        node.Next = _tail;
        _tail.Prev!.Next = node;
        _tail.Prev = node;
        _size++;
    }

    // Remove a specific node — O(1)
    public void Remove(DListNode node)
    {
        node.Prev!.Next = node.Next;
        node.Next!.Prev = node.Prev;
        _size--;
    }

    // Remove from the beginning — O(1)
    public int? RemoveFirst()
    {
        if (_size == 0)
        {
            return null;
        }
        var node = _head.Next!;
        Remove(node);
        return node.Val;
    }

    // Remove from the end — O(1)
    public int? RemoveLast()
    {
        if (_size == 0)
        {
            return null;
        }
        var node = _tail.Prev!;
        Remove(node);
        return node.Val;
    }

    // Traverse forward
    public void PrintForward()
    {
        for (var current = _head.Next; current != _tail; current = current!.Next)
        {
            Console.Write($"{current!.Val} <-> ");
        }
        Console.WriteLine("null");
    }

    // Traverse backward
    public void PrintBackward()
    {
        for (var current = _tail.Prev; current != _head; current = current!.Prev)
        {
            Console.Write($"{current!.Val} <-> ");
        }
        Console.WriteLine("null");
    }
}

# Educational implementation. Real Python code uses collections.deque —
# it is a C-level doubly linked list with O(1) push/pop on both ends.
class DoublyLinkedList:
    def __init__(self) -> None:
        # Sentinel nodes (dummy boundaries)
        self._head = DListNode()
        self._tail = DListNode()
        self._head.next = self._tail
        self._tail.prev = self._head
        self._size = 0

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

    # Insert at the beginning — O(1)
    def add_first(self, val: int) -> None:
        node = DListNode(val)
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node
        self._size += 1

    # Insert at the end — O(1)
    def add_last(self, val: int) -> None:
        node = DListNode(val)
        node.prev = self._tail.prev
        node.next = self._tail
        self._tail.prev.next = node
        self._tail.prev = node
        self._size += 1

    # Remove a specific node — O(1)
    def remove(self, node: DListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1

    # Remove from the beginning — O(1)
    def remove_first(self) -> int | None:
        if self._size == 0:
            return None
        node = self._head.next
        self.remove(node)
        return node.val

    # Remove from the end — O(1)
    def remove_last(self) -> int | None:
        if self._size == 0:
            return None
        node = self._tail.prev
        self.remove(node)
        return node.val

    # Traverse forward
    def print_forward(self) -> None:
        parts: list[str] = []
        current = self._head.next
        while current is not self._tail:
            parts.append(str(current.val))
            current = current.next
        print(" <-> ".join([*parts, "None"]))

    # Traverse backward
    def print_backward(self) -> None:
        parts: list[str] = []
        current = self._tail.prev
        while current is not self._head:
            parts.append(str(current.val))
            current = current.prev
        print(" <-> ".join([*parts, "None"]))

## Визуализация операций

Вставка в начало

До:
  head <-> [A] <-> [B] <-> tail

Вставка X:
  1. X->next = head->next (= A)
  2. X->prev = head
  3. A->prev = X
  4. head->next = X

После:
  head <-> [X] <-> [A] <-> [B] <-> tail

Удаление узла

До:
  ... <-> [A] <-> [B] <-> [C] <-> ...
                   ^
              удаляем B

  1. A->next = C    (B->prev->next = B->next)
  2. C->prev = A    (B->next->prev = B->prev)

После:
  ... <-> [A] <-> [C] <-> ...

Sentinel (фиктивные узлы)

Sentinel nodes — это фиктивные узлы на границах списка. Они упрощают код, убирая необходимость проверять null.

// Without sentinel (many checks):
public function addFirstNoSentinel(int $val): void
{
    $node = new DListNode($val);
    if ($this->head === null) {
        $this->head = $node;
        $this->tail = $node;
    } else {
        $node->next = $this->head;
        $this->head->prev = $node;
        $this->head = $node;
    }
}

// With sentinel (clean code):
public function addFirstWithSentinel(int $val): void
{
    $node = new DListNode($val);
    $node->next = $this->head->next;
    $node->prev = $this->head;
    $this->head->next->prev = $node;
    $this->head->next = $node;
    // Works even for empty list!
}

// Without sentinel (many checks):
func (dl *DoublyLinkedList) addFirstNoSentinel(val int) {
    node := &DListNode{Val: val}
    if dl.head == nil {
        dl.head = node
        dl.tail = node
    } else {
        node.Next = dl.head
        dl.head.Prev = node
        dl.head = node
    }
}

// With sentinel (clean code):
func (dl *DoublyLinkedList) addFirstWithSentinel(val int) {
    node := &DListNode{Val: val}
    node.Next = dl.head.Next
    node.Prev = dl.head
    dl.head.Next.Prev = node
    dl.head.Next = node
    // Works even for empty list!
}

// Without sentinel (many checks):
public void AddFirstNoSentinel(int val)
{
    var node = new DListNode(val);
    if (_head is null)
    {
        _head = node;
        _tail = node;
    }
    else
    {
        node.Next = _head;
        _head.Prev = node;
        _head = node;
    }
}

// With sentinel (clean code):
public void AddFirstWithSentinel(int val)
{
    var node = new DListNode(val);
    node.Next = _head.Next;
    node.Prev = _head;
    _head.Next!.Prev = node;
    _head.Next = node;
    // Works even for empty list!
}

# Without sentinel (many checks):
def add_first_no_sentinel(self, val: int) -> None:
    node = DListNode(val)
    if self._head is None:
        self._head = node
        self._tail = node
    else:
        node.next = self._head
        self._head.prev = node
        self._head = node

# With sentinel (clean code):
def add_first_with_sentinel(self, val: int) -> None:
    node = DListNode(val)
    node.next = self._head.next
    node.prev = self._head
    self._head.next.prev = node
    self._head.next = node
    # Works even for empty list!

## Практическое применение: LRU Cache

LRU Cache (Least Recently Used) — классическая задача, которая идеально решается двусвязным списком + HashMap.

class LRUNode
{
    public function __construct(
        public int $key = 0,
        public int $val = 0,
        public ?LRUNode $prev = null,
        public ?LRUNode $next = null,
    ) {}
}

class LRUCache
{
    private array $cache = [];  // key -> LRUNode
    private LRUNode $head;
    private LRUNode $tail;

    public function __construct(private int $capacity)
    {
        $this->head = new LRUNode();
        $this->tail = new LRUNode();
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    private function addToFront(LRUNode $node): void
    {
        $node->next = $this->head->next;
        $node->prev = $this->head;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }

    private function removeNode(LRUNode $node): void
    {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }

    private function moveToFront(int $key): void
    {
        $node = $this->cache[$key];
        $this->removeNode($node);
        $this->addToFront($node);
    }

    public function get(int $key): int
    {
        if (!isset($this->cache[$key])) {
            return -1;
        }
        $this->moveToFront($key);
        return $this->cache[$key]->val;
    }

    public function put(int $key, int $value): void
    {
        if (isset($this->cache[$key])) {
            $this->cache[$key]->val = $value;
            $this->moveToFront($key);
        } else {
            if (count($this->cache) >= $this->capacity) {
                // Remove least recently used (end of list)
                $lru = $this->tail->prev;
                $this->removeNode($lru);
                unset($this->cache[$lru->key]);
            }

            $node = new LRUNode($key, $value);
            $this->cache[$key] = $node;
            $this->addToFront($node);
        }
    }
}

type LRUNode struct {
    Key  int
    Val  int
    Prev *LRUNode
    Next *LRUNode
}

type LRUCache struct {
    capacity int
    cache    map[int]*LRUNode // key -> LRUNode
    head     *LRUNode
    tail     *LRUNode
}

func NewLRUCache(capacity int) *LRUCache {
    head := &LRUNode{}
    tail := &LRUNode{}
    head.Next = tail
    tail.Prev = head
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*LRUNode),
        head:     head,
        tail:     tail,
    }
}

func (c *LRUCache) addToFront(node *LRUNode) {
    node.Next = c.head.Next
    node.Prev = c.head
    c.head.Next.Prev = node
    c.head.Next = node
}

func (c *LRUCache) removeNode(node *LRUNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (c *LRUCache) Get(key int) int {
    node, ok := c.cache[key]
    if !ok {
        return -1
    }
    c.removeNode(node)
    c.addToFront(node)
    return node.Val
}

func (c *LRUCache) Put(key, value int) {
    if node, ok := c.cache[key]; ok {
        node.Val = value
        c.removeNode(node)
        c.addToFront(node)
    } else {
        if len(c.cache) >= c.capacity {
            // Remove least recently used (end of list)
            lru := c.tail.Prev
            c.removeNode(lru)
            delete(c.cache, lru.Key)
        }

        node := &LRUNode{Key: key, Val: value}
        c.cache[key] = node
        c.addToFront(node)
    }
}

public class LRUNode(int key = 0, int val = 0)
{
    public int Key { get; set; } = key;
    public int Val { get; set; } = val;
    public LRUNode? Prev { get; set; }
    public LRUNode? Next { get; set; }
}

public class LRUCache
{
    private readonly int _capacity;
    private readonly Dictionary<int, LRUNode> _cache = []; // key -> LRUNode
    private readonly LRUNode _head = new();
    private readonly LRUNode _tail = new();

    public LRUCache(int capacity)
    {
        _capacity = capacity;
        _head.Next = _tail;
        _tail.Prev = _head;
    }

    private void AddToFront(LRUNode node)
    {
        node.Next = _head.Next;
        node.Prev = _head;
        _head.Next!.Prev = node;
        _head.Next = node;
    }

    private static void RemoveNode(LRUNode node)
    {
        node.Prev!.Next = node.Next;
        node.Next!.Prev = node.Prev;
    }

    private void MoveToFront(LRUNode node)
    {
        RemoveNode(node);
        AddToFront(node);
    }

    public int Get(int key)
    {
        if (!_cache.TryGetValue(key, out var node))
        {
            return -1;
        }
        MoveToFront(node);
        return node.Val;
    }

    public void Put(int key, int value)
    {
        if (_cache.TryGetValue(key, out var existing))
        {
            existing.Val = value;
            MoveToFront(existing);
            return;
        }

        if (_cache.Count >= _capacity)
        {
            // Remove least recently used (end of list)
            var lru = _tail.Prev!;
            RemoveNode(lru);
            _cache.Remove(lru.Key);
        }

        var node = new LRUNode(key, value);
        _cache[key] = node;
        AddToFront(node);
    }
}

# Manual version below shows the mechanics; in real code
# collections.OrderedDict.move_to_end / popitem gives the same O(1) LRU.
@dataclass
class LRUNode:
    key: int = 0
    val: int = 0
    prev: LRUNode | None = field(default=None, repr=False)
    next: LRUNode | None = field(default=None, repr=False)

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self._capacity = capacity
        self._cache: dict[int, LRUNode] = {}  # key -> LRUNode
        self._head = LRUNode()
        self._tail = LRUNode()
        self._head.next = self._tail
        self._tail.prev = self._head

    def _add_to_front(self, node: LRUNode) -> None:
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node

    @staticmethod
    def _remove_node(node: LRUNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_front(self, node: LRUNode) -> None:
        self._remove_node(node)
        self._add_to_front(node)

    def get(self, key: int) -> int:
        node = self._cache.get(key)
        if node is None:
            return -1
        self._move_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self._cache.get(key)
        if node is not None:
            node.val = value
            self._move_to_front(node)
            return

        if len(self._cache) >= self._capacity:
            # Remove least recently used (end of list)
            lru = self._tail.prev
            self._remove_node(lru)
            del self._cache[lru.key]

        node = LRUNode(key, value)
        self._cache[key] = node
        self._add_to_front(node)

``` LRU Cache (capacity=3):

Начало: head <-> tail

put(1, A): head <-> [1:A] <-> tail put(2, B): head <-> [2:B] <-> [1:A] <-> tail put(3, C): head <-> [3:C] <-> [2:B] <-> [1:A] <-> tail

get(1): head <-> [1:A] <-> [3:C] <-> [2:B] <-> tail (1 перемещён в начало)

put(4, D): head <-> [4:D] <-> [1:A] <-> [3:C] <-> tail (2:B вытеснен — был последним)


Все операции — **O(1)**: HashMap для O(1) доступа, двусвязный список для O(1) перемещения/удаления.

## Сравнение одно- и двусвязных списков

| Свойство                      | Односвязный | Двусвязный  |
|-------------------------------|-------------|-------------|
| Память на узел                | val + next  | val + prev + next |
| Обход вперёд                  | O(n)        | O(n)        |
| Обход назад                   | Невозможен  | O(n)        |
| Вставка в начало              | O(1)        | O(1)        |
| Вставка в конец (с tail)      | O(1)        | O(1)        |
| Удаление по ссылке на узел    | O(n)*       | O(1)        |
| Удаление с конца              | O(n)        | O(1)        |
| Реализация сложность          | Простая     | Умеренная   |

*\* Нужен предыдущий узел, а его найти за O(n)*

### Когда использовать двусвязный

- LRU Cache и подобные задачи
- Нужно удалять узлы по ссылке за O(1)
- Нужен обход в обоих направлениях
- Реализация deque (двусторонней очереди)
- Текстовые редакторы (курсор может двигаться вперёд и назад)

### Когда хватит односвязного

- Простые стеки и очереди
- Обход только в одном направлении
- Минимизация памяти
- Большинство задач на интервью

> **Запомни:** Двусвязный список + HashMap = O(1) для всех операций в LRU Cache. Sentinel nodes устраняют edge cases при вставке и удалении. Используй двусвязный, когда нужно удалять узлы по ссылке за O(1) или двигаться в обоих направлениях.

## Итоги

1. Двусвязный = prev + val + next в каждом узле
2. Удаление узла по ссылке за O(1) (главное преимущество)
3. Sentinel nodes упрощают код, устраняя проверки на null
4. LRU Cache = HashMap + Doubly Linked List
5. Больше памяти на узел, но гибче в операциях