Двусвязный список
У каждого узла prev и next: удаление O(1), обход в обе стороны.
1class DNode {2 value: number3 prev: DNode | null = null4 next: DNode | null = null5 constructor(value: number) { this.value = value }6}7 8function insertAfter(node: DNode, value: number): DNode {9 const fresh = new DNode(value)10 fresh.prev = node11 fresh.next = node.next12 if (node.next !== null) node.next.prev = fresh13 node.next = fresh14 return fresh15}16 17function removeNode(node: DNode): void {18 if (node.prev !== null) node.prev.next = node.next19 if (node.next !== null) node.next.prev = node.prev20}Проблема
Односвязный список удаляет узел только найдя предыдущий (O(n) поиска), и не умеет ходить назад. Если операции идут с обоих концов и по обеим сторонам — нужен второй указатель.
Что вы видите
Узлы со стрелками в обе стороны: вставка в середину — четыре перестрелки, никакого сдвига.
Как это работает
Каждый узел хранит prev и next: вставка перецепляет четыре стрелки вместо двух, зато удаление по ссылке — O(1) без поиска, а обход возможен в обе стороны. Именно эта симметрия делает двусвязный список основой LRU-кэша и deque из stdlib.
Пошаговый разбор
- 01
Вставка
fresh получает prev и next, соседи обновляются.
- 02
Обход назад
По prev от хвоста к голове.
- 03
Удаление
Соседи перемахивают через узел.
Complexity и ограничения
См. complexity в шапке страницы.
Edge cases
- Удаление головы
head сдвигается — special case без prev.
- Удаление хвоста
tail.next нет — проверка на null обязательна.
- Вставка в пустой список
head и tail оба указывают на новый узел.
Где встречается в реальности
Продукт
Классический приём в реальных системах.
Собеседования
Стандартный вопрос на понимание структуры.
Связанные алгоритмы
«Удаление за две стрелки: prev и next»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.