Связный список: когда слайс не подходит

Связный список: когда слайс не подходит

В 95% случаев слайс лучше. Но есть ситуации, где связный список выигрывает.

Проще всего это понять на очереди. Сидишь в очереди. Знаешь только, за кем занимать. За кем идёшь - помнишь, дальше туман. Это связный список: у каждого ссылка только на следующего. Запомнил ещё и того, кто занял после тебя? Уже двусвязный список - ходишь в обе стороны: «кто передо мной? кто за мной?».

В жизниВ коде
сосед, за которым занималуказатель Next
тот, кто занял после тебяуказатель Prev
первый в очередиHead
«а кто тут девятый?» - идти и считатьдоступ по индексу O(n)

Спросить «кто девятый?» нельзя - надо идти вдоль очереди и пересчитывать. Зато встать в начало или уйти из середины - мгновенно, соседи просто перезнакомятся. А если нужен мгновенный ответ про любого - это уже бабуля из урока про map.

Связный список: узлы с указателями next и prev, односвязный vs двусвязный

Односвязный список

type Node[T any] struct {
    Value T
    Next  *Node[T]
}

type LinkedList[T any] struct {
    Head *Node[T]
    Size int
}

func (l *LinkedList[T]) PushFront(val T) {
    node := &Node[T]{Value: val, Next: l.Head}
    l.Head = node
    l.Size++
}

func (l *LinkedList[T]) PopFront() (T, bool) {
    if l.Head == nil {
        var zero T
        return zero, false
    }
    val := l.Head.Value
    l.Head = l.Head.Next
    l.Size--
    return val, true
}
<?php
declare(strict_types=1);

$list = new SplDoublyLinkedList();
$list->push('a');    // в хвост
$list->push('b');
$list->push('c');
$list->unshift('0'); // в голову

foreach ($list as $value) {
    echo $value . "\n"; // 0, a, b, c
}

// O(1) операции на концах
$first = $list->shift(); // удаляем '0' из головы
$last = $list->pop();    // удаляем 'c' из хвоста

echo count($list); // 2

// Доступ по индексу O(n) - честный linked list
$middle = $list[0];

В PHP писать связный список руками не нужно - есть \SplDoublyLinkedList (база для \SplStack и \SplQueue). Он реализует Iterator, Countable, ArrayAccess, поддерживает обход в обе стороны.

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass(slots=True)
class Node(Generic[T]):
    value: T
    next: "Node[T] | None" = None


class LinkedList(Generic[T]):
    def __init__(self) -> None:
        self.head: Node[T] | None = None
        self.size = 0

    def push_front(self, val: T) -> None:
        self.head = Node(val, self.head)
        self.size += 1

    def pop_front(self) -> T | None:
        # Вместо пары (T, bool) из Go - None, если список пуст
        if self.head is None:
            return None
        val = self.head.value
        self.head = self.head.next
        self.size -= 1
        return val

\SplDoublyLinkedList - двусвязный список (как container/list в Go). Если нужен односвязный - встроенного нет, проще написать руками final class Node { public function __construct(public mixed $value, public ?Node $next = null) {} }. Значение по умолчанию null важно: типизированное свойство без него остаётся неинициализированным, и первое же чтение $node->next бросит Error.

Сложность операций

ОперацияSliceLinked List
Доступ по индексуO(1)O(n)
Вставка в началоO(n)O(1)
Вставка в конецO(1) amortizedO(1) с tail
Удаление из началаO(n)O(1)
Удаление из серединыO(n)O(1) в двусвязном при указателе на узел; O(n) в односвязном
ПоискO(n)O(n)
Cache-friendlyДаНет

Строка «доступ по индексу O(n)» - это та самая очередь: чтобы узнать девятого, надо пройти от соседа к соседу.

container/list из stdlib

Go предоставляет двусвязный список в стандартной библиотеке:

import "container/list"

func main() {
    l := list.New()

    // Вставка
    l.PushBack("first")
    l.PushBack("second")
    l.PushFront("zero")

    // Итерация
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value) // zero, first, second
    }

    // Удаление
    l.Remove(l.Front())
}
<?php
declare(strict_types=1);

$list = new SplDoublyLinkedList();
$list->push('first');
$list->push('second');
$list->unshift('zero');

// Итерация (порядок такой же: zero, first, second)
foreach ($list as $value) {
    echo $value . "\n";
}

// Удаление головы
$list->shift();
// Или offsetUnset по индексу:
$list->offsetUnset(0);
from collections import deque

# Готового container/list в stdlib нет: ближайший аналог -
# collections.deque, двусторонняя очередь с O(1) на обоих концах


def main() -> None:
    l: deque[str] = deque()

    # Вставка
    l.append("first")
    l.append("second")
    l.appendleft("zero")

    # Итерация
    for value in l:
        print(value)  # zero, first, second

    # Удаление головы
    l.popleft()

ℹ️ Когда использовать container/list

LRU-кеш (вытесняет то, к чему дольше всех не обращались, разбор ниже; его делают и поверх Redis), очередь с приоритетным удалением, реализация deque. В остальных случаях слайс быстрее из-за cache locality.

Для PHP такой же выбор: \SplDoublyLinkedList или \Ds\Deque для двусторонней очереди. Для готового LRU-кеша - Symfony\Component\Cache\Adapter\ArrayAdapter (или LRUCache-обёртка вокруг него); реализовывать самому почти никогда не нужно.

Практика: разворот списка

func (l *LinkedList[T]) Reverse() {
    var prev *Node[T]
    current := l.Head

    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    l.Head = prev
}

Разворот - это когда вся очередь разом переспрашивает «а за кем я теперь?»: каждый запоминает предыдущего вместо следующего.

Практика: есть ли цикл в списке

Если Next последнего узла по ошибке указывает на один из предыдущих, обход for node != nil никогда не закончится. Проверить это без дополнительной памяти помогает алгоритм Флойда («черепаха и заяц»): два указателя идут по списку, slow на один шаг, fast на два. Если цикла нет, fast дойдёт до nil. Если цикл есть, fast рано или поздно догонит slow внутри цикла.

func (l *LinkedList[T]) HasCycle() bool {
    slow, fast := l.Head, l.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}
<?php
declare(strict_types=1);

function hasCycle(?Node $head): bool
{
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) { // === для объектов - тот же экземпляр
            return true;
        }
    }
    return false;
}
def has_cycle(head: "Node | None") -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # is - тот же объект, а не равное значение
            return True
    return False

Время O(n), память O(1). Решение «запоминать посещённые узлы в map» тоже работает, но тратит O(n) памяти.

LRU-кеш на связном списке

LRU (least recently used) - кеш на фиксированное число записей: при переполнении он выбрасывает ту, к которой дольше всех не обращались. Нужны две вещи сразу: найти запись по ключу за O(1) - это map, и хранить порядок обращений с переносом в начало и удалением с конца за O(1) - это двусвязный список. Map хранит указатель на узел списка.

type LRUCache struct {
    capacity int
    items    map[string]*list.Element
    order    *list.List
}

type entry struct {
    key   string
    value string
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        order:    list.New(),
    }
}

func (c *LRUCache) Get(key string) (string, bool) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return "", false
}

func (c *LRUCache) Put(key, value string) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.order.Len() >= c.capacity {
        oldest := c.order.Back()
        c.order.Remove(oldest)
        delete(c.items, oldest.Value.(*entry).key)
    }

    elem := c.order.PushFront(&entry{key, value})
    c.items[key] = elem
}
<?php
declare(strict_types=1);

final class LRUCache
{
    /** @var SplDoublyLinkedList */
    private SplDoublyLinkedList $order;

    /** @var array<string, string> key → value; порядок использования хранится отдельно в $order */
    private array $items = [];

    public function __construct(private readonly int $capacity) {
        $this->order = new SplDoublyLinkedList();
    }

    public function get(string $key): ?string
    {
        if (!isset($this->items[$key])) {
            return null;
        }

        $value = $this->items[$key];
        $this->touch($key, $value);
        return $value;
    }

    public function put(string $key, string $value): void
    {
        if (isset($this->items[$key])) {
            $this->touch($key, $value);
            return;
        }

        if (count($this->items) >= $this->capacity) {
            $oldest = $this->order->shift();
            unset($this->items[$oldest]);
        }

        $this->order->push($key);
        $this->items[$key] = $value;
    }

    private function touch(string $key, string $value): void
    {
        // Удаляем старую позицию ключа и кладём в хвост (most recently used)
        foreach ($this->order as $idx => $k) {
            if ($k === $key) {
                $this->order->offsetUnset($idx);
                break;
            }
        }
        $this->order->push($key);
        $this->items[$key] = $value;
    }
}

// Прагматичный вариант для прода - Symfony Cache:
// use Symfony\Component\Cache\Adapter\ArrayAdapter;
// $cache = new ArrayAdapter(defaultLifetime: 0, storeSerialized: false, maxLifetime: 0, maxItems: 100);
// $cache->get('user:42', fn () => $repo->find(42));

В PHP LRU удобно собирать на \SplDoublyLinkedList + массив-индекс. Но если задача прикладная (HTTP-кеш, мемоизация репозитория) - бери готовое: Symfony\Component\Cache\Adapter\ArrayAdapter с параметром maxItems (при переполнении вытесняет давно не использованные записи, по модели LRU).

Учебная PHP-реализация выше теряет O(1) на touch (linear scan для поиска ноды). Промышленный путь - ArrayAdapter с maxItems, который под капотом делает то же самое за O(1) через array_key_* трюки.

from collections import OrderedDict


class LRUCache:
    # OrderedDict внутри - тот же двусвязный список + hash map,
    # что list.List + map в Go, поэтому отдельный список не нужен
    def __init__(self, capacity: int) -> None:
        self._capacity = capacity
        self._items: OrderedDict[str, str] = OrderedDict()

    def get(self, key: str) -> str | None:
        if key not in self._items:
            return None
        self._items.move_to_end(key, last=False)  # в начало = most recently used
        return self._items[key]

    def put(self, key: str, value: str) -> None:
        if key in self._items:
            self._items.move_to_end(key, last=False)
            self._items[key] = value
            return

        if len(self._items) >= self._capacity:
            self._items.popitem(last=True)  # самый старый - в конце

        self._items[key] = value
        self._items.move_to_end(key, last=False)


# Прагматичный вариант для мемоизации функций - functools.lru_cache(maxsize=100)

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.