Связный список — это структура данных, где каждый элемент хранит значение и ссылку на следующий узел. В отличие от массива, элементы списка не лежат подряд в памяти. Это делает структуру гибкой при вставках и удалениях, но не всегда быстрой в доступе.
Как устроен связный список
- Обычно узел содержит:
- data — полезные данные
- next — ссылку на следующий элемент
В двусвязном списке добавляется ещё prev — ссылка на предыдущий узел. Есть и циклические списки, где последний элемент указывает на первый.
Основные виды
- Односвязный список — переход только вперёд
- Двусвязный список — можно идти вперёд и назад
- Циклический список — конец связан с началом
Плюсы связных списков ✅
- Быстрая вставка и удаление элемента, если известна позиция
- Размер структуры легко меняется во время работы программы
- Не требуется выделять непрерывный блок памяти
Минусы ⚠️
- Нет быстрого доступа по индексу: чтобы найти элемент, нужно пройти список
- Дополнительная память уходит на хранение ссылок
- Хуже локальность данных по сравнению с массивом, а значит возможны потери в производительности
Сложность операций
- Доступ по индексу — O(n)
- Поиск элемента — O(n)
- Вставка в начало — O(1)
- Удаление из начала — O(1)
- Вставка или удаление после найденного узла — O(1)
Где применяются
Связные списки полезны там, где важны частые изменения структуры:
- реализация очередей и стеков
- хеш-таблицы с цепочками коллизий
- графы через списки смежности
- LRU-кэши вместе с хеш-мапой
- системы, где нужно часто вставлять и удалять элементы в середине
Типовые задачи на собеседованиях и в обучении 🧠
- Развернуть список
- Найти середину списка
- Определить цикл
- Удалить N-й элемент с конца
- Слить два отсортированных списка
- Найти точку пересечения двух списков
Когда выбирать список, а когда массив
Если нужен быстрый доступ по индексу, чаще лучше массив или ArrayList. Если важны частые вставки и удаления, особенно в начале или середине при наличии ссылки на узел, связный список может быть удачным решением.
Главный вывод: связный список — не «устаревшая» структура, а инструмент под конкретные задачи. Понимание его реализации помогает лучше разбираться в алгоритмах, оптимизации памяти и внутреннем устройстве стандартных коллекций. ⚙️📚
Подборку каналов про IT стоит сохранить отдельно — там много полезного по алгоритмам, разработке и карьере 🚀