Двусвязный список
Отличие от односвязного
В двусвязном списке каждый узел хранит ссылки на следующий и предыдущий узлы. Это позволяет перемещаться в обоих направлениях.
Односвязный:
[1] -> [2] -> [3] -> [4] -> null
head
Двусвязный:
null <- [1] <-> [2] <-> [3] <-> [4] -> null
head tail
Структура узла
PHPGo
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}
}
PHPGo
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")
}
Вставка в начало
До:
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.
PHPGo
// 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!
}
LRU Cache (Least Recently Used) — классическая задача, которая идеально решается двусвязным списком + HashMap.
PHPGo
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)
}
}
Начало: 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. Больше памяти на узел, но гибче в операциях