Линейный список. Физическое представление (массив): индексный вектор

Модуль "Линейные списки" • урок 3 из 9 • ~6 минут

Проблема простого массива

Самый очевидный способ реализовать список - положить элементы подряд в массив. Вычисление адреса будет мгновенным. Но что, если нужно вставить новый элемент между первым и вторым?

Придется физически сдвинуть все последующие элементы вправо на одну позицию (в среднем N/2 операций). Аналогично, при удалении элемента из середины придется сдвинуть весь хвост влево, чтобы избежать пустот. Это делает вставку и удаление очень медленными операциями со сложностью O(N).

Линейный список. Физическое представление (массив): как работает индексный вектор

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

• Удаление: Мы не сдвигаем массив. Мы просто меняем индекс у предыдущего элемента, чтобы он указывал "через одного". Появляется пустая "дырка".
• Вставка: Мы берем первую свободную ячейку из специального списка свободных элементов, пишем туда данные и перенастраиваем связи (индексы).

Как это выглядит на языке C

Массив становится суррогатом динамической памяти: индексы играют роль указателей, а программист пишет собственный менеджер памяти ("сборщик мусора").

#define MAX_SIZE 100

/* Элемент массива, содержащий данные и индекс следующего */
typedef struct {
    int data;
    int next_index; /* Индекс следующего элемента (-1 если конец списка) */
} SurrogateNode;

typedef struct {
    SurrogateNode pool[MAX_SIZE]; /* Сплошной блок памяти (пул) */
    int head_index;               /* Индекс начала логического списка */
    int free_list_head;           /* Индекс первой свободной ячейки */
} SurrogateList;

Если мы удаляем элемент под индексом 5, элементы с 6-го по 100-й остаются на своих местах. Мы просто добавляем число 5 в цепочку free_list_head, чтобы повторно использовать эту ячейку при следующей вставке.