Структуры данных. Связный список

05.02.2026

Computer Science

C++

Python

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

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

Связный список — это цепочка узлов (nodes), где каждый узел содержит:

полезные данные (число, строка, объект и т.д.)

ссылку (указатель) на следующий узел

Последний узел обычно указывает на null (или None в Python), сигнализируя конец списка. Первый узел называется head (голова), последний — tail (хвост).

Главные отличия от массива:

Размер не фиксирован. Можно добавлять и удалять элементы в любой момент

Элементы могут располагаться в памяти в произвольном порядке

Доступ по индексу медленный, зато вставка/удаление в определённых местах часто быстрее

Основные разновидности связных списков

Односвязный. Каждый узел знает только следующий элемент и движение возможно только вперёд.

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

Циклический. Последний узел указывает обратно на первый тем самым получая зацикленный список.

Циклический двусвязный. Комбинация предыдущих двух вариантов.

Ключевые возможные операции

Доступ по индексу

Вставка в начало (head)

Вставка в конец (tail)

Вставка посередине

Удаление из начала

Удаление из конца

Удаление по значению/индексу

Поиск элемента

Полный обход

Примеры реализации

Python — односвязный список:

C++ — двусвязный (фрагмент узла):

Сильные стороны связных списков

Динамический размер. Не нужно заранее знать количество элементов

Быстрая вставка и удаление в начале (и в конце, если есть tail)

Не требуется сдвиг элементов при вставке/удалении посередине (в отличие от массива)

Легко реализовать стек, очередь, дек

Память выделяется только под реально существующие элементы

Слабые стороны

Доступ по индексу очень медленный

Требуется дополнительная память на каждый указатель (next/prev)

Нет случайного доступа (random access)

Сложнее отлаживать и читать код по сравнению с массивами

Где применяются связные списки на практике

Реализация стеков и очередей

Менеджеры памяти

Музыкальные плейлисты (следующий/предыдущий трек)

Навигация вперёд-назад в браузерах

Хеширование с цепочками

Реализация полиномов, больших чисел

Графовые алгоритмы (списки смежности)

Связные списки — это та структура, которую стоит понимать на уровне "почему и как", даже если в повседневной разработке вы чаще используете ArrayList / vector / list. Именно они помогают глубже понять указатели, управление памятью и компромисс между скоростью доступа и гибкостью изменений.

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