Что такое «Связный список»
В массиве элементы лежат в памяти подряд, и чтобы вставить новый в середину, приходится сдвигать все последующие. Связный список устроен иначе: узлы могут находиться где угодно, а порядок задают ссылки. Чтобы вставить элемент, достаточно поменять пару ссылок у соседей.
Первый узел называют головой, последний — хвостом, его ссылка на следующий элемент пустая. В односвязном списке можно двигаться только вперёд. В двусвязном каждый узел знает и предыдущего соседа, поэтому по нему можно идти в обе стороны и быстро удалять узел, имея ссылку только на него.
Сравнение с массивом
- Доступ по номеру: в массиве сразу, в списке — проход от головы, время растёт с длиной.
- Вставка и удаление в известном месте: в списке за постоянное время, в массиве со сдвигом элементов.
- Память: каждому узлу списка нужно место под ссылки, а сами узлы разбросаны, что хуже для кеша процессора.
На практике массивы и динамические массивы выигрывают в большинстве повседневных задач. Связный список выбирают, когда вставок и удалений в начале, конце или середине много, а случайный доступ по индексу почти не нужен.
Пример в 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

