Что такое «Связный список»

В массиве элементы лежат в памяти подряд, и чтобы вставить новый в середину, приходится сдвигать все последующие. Связный список устроен иначе: узлы могут находиться где угодно, а порядок задают ссылки. Чтобы вставить элемент, достаточно поменять пару ссылок у соседей.

Первый узел называют головой, последний — хвостом, его ссылка на следующий элемент пустая. В односвязном списке можно двигаться только вперёд. В двусвязном каждый узел знает и предыдущего соседа, поэтому по нему можно идти в обе стороны и быстро удалять узел, имея ссылку только на него.

Сравнение с массивом

  • Доступ по номеру: в массиве сразу, в списке — проход от головы, время растёт с длиной.
  • Вставка и удаление в известном месте: в списке за постоянное время, в массиве со сдвигом элементов.
  • Память: каждому узлу списка нужно место под ссылки, а сами узлы разбросаны, что хуже для кеша процессора.

На практике массивы и динамические массивы выигрывают в большинстве повседневных задач. Связный список выбирают, когда вставок и удалений в начале, конце или середине много, а случайный доступ по индексу почти не нужен.

Пример в PHP

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

$list = new SplDoublyLinkedList();
$list->push('первый');
$list->push('третий');
$list->add(1, 'второй');   // вставка на позицию 1

foreach ($list as $item) {
    echo $item, PHP_EOL;     // первый, второй, третий
}

На его основе в SPL построены SplQueue и SplStack, то есть очередь и стек.

Где встречается

Связные списки лежат в основе очередей задач, истории действий «отменить/повторить», кеша с вытеснением давно не используемых записей: там двусвязный список хранит порядок обращений, а хеш-таблица даёт быстрый поиск узла. Списки Redis тоже описаны в документации как связные: добавить элемент в начало или конец можно быстро даже в очень длинном списке, а обращение к середине медленнее.

Связанные термины

Обновлено: 10 октября 2026

Все термины раздела «Backend» ↗