Связанный список

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

История

Концепция связанных списков была впервые формально описана в 1955—1956 годах Алленом Ньюэллом, Клиффом Шоу и Гербертом Саймоном в рамках разработки языка обработки списков IPL (Information Processing Language). IPL стал первым языком программирования, в котором использовалась явная структура связанных списков для представления символьной информации. В 1960 году Джон Маккарти применил идеи связанных списков при создании языка Lisp, где списки стали основной структурой данных для представления кода и данных. В последующие десятилетия связанные списки вошли в стандартные библиотеки большинства языков программирования и стали классическим примером для изучения алгоритмов и структур данных.

Основные характеристики

Связанный список состоит из узлов, каждый из которых содержит:

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

Главное преимущество связанного списка перед массивом — динамическое управление памятью: размер списка может изменяться во время выполнения программы без необходимости предварительного выделения памяти. Однако доступ к элементу по индексу требует последовательного обхода списка, что даёт временную сложность O(n), тогда как в массиве доступ по индексу выполняется за O(1).

Виды связанных списков

Односвязный список

Каждый узел содержит ссылку только на следующий узел. Обход возможен только в одном направлении — от головы (первого узла) к хвосту (последнему узлу, у которого ссылка равна null). Простейшая реализация, требует меньше памяти на узел.

Двусвязный список

Каждый узел содержит две ссылки: на следующий и на предыдущий узел. Это позволяет обходить список в обоих направлениях и упрощает операции удаления узла по ссылке на него. Недостаток — увеличенный расход памяти на хранение дополнительной ссылки.

Кольцевой (циклический) список

В кольцевом списке последний узел ссылается на первый, образуя замкнутое кольцо. Может быть как односвязным, так и двусвязным. Применяется в задачах, где требуется циклический обход, например, в планировщиках задач операционных систем (алгоритм Round Robin).

Список с пропусками (Skip list)

Хотя технически это не классический связанный список, список с пропусками использует многоуровневую структуру связанных списков для ускорения поиска. Каждый узел может иметь несколько ссылок на узлы, расположенные на разных расстояниях. Временная сложность поиска, вставки и удаления в среднем составляет O(log n).

Операции над связанным списком

Основные операции включают:

Поиск элемента — последовательный обход узлов до нахождения нужного значения. Временная сложность O(n).
Вставка узла — в начало (O(1) при наличии указателя на голову), в конец (O(1) при наличии указателя на хвост, иначе O(n)), в середину (O(n) для поиска позиции + O(1) для вставки).
Удаление узла — аналогично вставке: удаление первого узла (O(1)), удаление последнего или произвольного узла требует обхода.
Обход списка — последовательное посещение всех узлов для выполнения некоторого действия (например, вывода данных).

Реализация

Реализация связанного списка зависит от языка программирования. В языках с явным управлением памятью (C, C++) программист самостоятельно выделяет и освобождает память под узлы. В языках со сборкой мусора (Java, Python, C#) память управляется автоматически, но концепция остаётся той же.

Пример простейшего односвязного списка на языке C:

```c struct Node { int data; struct Node* next; };

struct Node* head = NULL;

// Вставка в начало void insertAtBeginning(int newData) { struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = newData; newNode->next = head; head = newNode; } ```

В языках высокого уровня, таких как Python, связанные списки редко реализуются вручную, так как встроенные списки (list) уже обеспечивают динамическое изменение размера и эффективный доступ по индексу. Однако для обучения алгоритмам часто пишут собственную реализацию класса LinkedList.

Применение

Связанные списки используются в различных областях информатики и программирования:

Реализация стеков и очередей — на основе односвязных или двусвязных списков строятся динамические структуры LIFO и FIFO.
Управление памятью — операционные системы используют связанные списки для отслеживания свободных и занятых блоков памяти (например, в алгоритмах динамического распределения памяти).
Представление графов — списки смежности, где для каждой вершины хранится связанный список смежных вершин.
Обработка музыки и видео — в плеерах для организации плейлистов с возможностью переключения на следующий или предыдущий трек.
Реализация хеш-таблиц — для разрешения коллизий методом цепочек, когда в каждой ячейке хеш-таблицы хранится связанный список элементов.
Алгоритмы планирования задач — кольцевые списки используются в планировщиках для циклического перебора процессов.

Преимущества и недостатки

Преимущества	Недостатки
Динамический размер, не требуется предварительное выделение памяти	Последовательный доступ к элементам (O(n))
Быстрая вставка и удаление узлов в начале и середине (при известной позиции)	Дополнительный расход памяти на хранение ссылок
Эффективное использование памяти при частых вставках/удалениях	Сложность реализации по сравнению с массивами
Возможность реализации различных структур данных (стек, очередь, дек)	Отсутствие прямого доступа по индексу