Связный список: когда слайс не подходит
Связный список: когда слайс не подходит
В 95% случаев слайс лучше. Но есть ситуации, где связный список выигрывает.
Проще всего это понять на очереди. Сидишь в очереди. Знаешь только, за кем занимать. За кем идёшь - помнишь, дальше туман. Это связный список: у каждого ссылка только на следующего. Запомнил ещё и того, кто занял после тебя? Уже двусвязный список - ходишь в обе стороны: «кто передо мной? кто за мной?».
| В жизни | В коде |
|---|---|
| сосед, за которым занимал | указатель Next |
| тот, кто занял после тебя | указатель Prev |
| первый в очереди | Head |
| «а кто тут девятый?» - идти и считать | доступ по индексу O(n) |
Спросить «кто девятый?» нельзя - надо идти вдоль очереди и пересчитывать. Зато встать в начало или уйти из середины - мгновенно, соседи просто перезнакомятся. А если нужен мгновенный ответ про любого - это уже бабуля из урока про map.
Односвязный список
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.
Сложность операций
| Операция | Slice | Linked List |
|---|---|---|
| Доступ по индексу | O(1) | O(n) |
| Вставка в начало | O(n) | O(1) |
| Вставка в конец | O(1) amortized | O(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)