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

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

Почему динамические объекты?

Это наиболее естественное и гибкое представление списков. Оно полностью избавляет программиста от недостатков массива: не нужно сдвигать элементы при вставках и удалениях, нет проблемы "дырок", не нужно вручную программировать суррогатный индексный вектор. Выделение памяти берет на себя операционная система (или среда выполнения) по мере необходимости.

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

Элемент списка (узел) состоит из информационной части (данные) и служебной части (один или несколько физических указателей).

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

Каждый узел хранит данные и один указатель next на следующий элемент. Это экономит память, но имеет недостаток: двигаться по такому списку можно только в одном направлении - от головы к хвосту.

Двусвязный (симметричный) список

Узел содержит два указателя: на следующий (next) и на предыдущий (prev) элементы.

typedef struct Item {
    struct Item* prev; /* Ссылка назад */
    struct Item* next; /* Ссылка вперед */
    int data;          /* Полезные данные */
} Item;

Кольцевые списки: Двусвязные списки часто замыкают в кольцо. Последний элемент своим next указывает на первый, а первый своим prev - на последний. Это избавляет от проблемы "тупиков" по краям и убирает лишние проверки на NULL.

Вставка и удаление за O(1)

Физически вставка в середину двусвязного списка выглядит как простое "перебрасывание" четырех указателей. Мы разрываем связь между соседями и направляем их указатели на новый узел, а указатели нового узла - на соседей.

Сами данные в памяти никуда не копируются и не перемещаются! Стоимость самой операции переброски - O(1) (но не забывайте, что поиск нужного места все равно занимает O(N)).

Реализация вставки на языке C

Пример функции, которая вставляет новый узел после заданного (pos):

#include <stdlib.h>

/* Функция вставляет новый элемент ПОСЛЕ указанного узла (pos) */
void InsertAfter(Item* pos, int value) {
    if (pos == NULL) return;

    Item* newItem = (Item*)malloc(sizeof(Item));
    newItem->data = value;

    /* Настраиваем связи нового узла */
    newItem->prev = pos;
    newItem->next = pos->next;

    /* Перебрасываем связи соседей на новый узел */
    if (pos->next != NULL) {
        pos->next->prev = newItem;
    }
    pos->next = newItem;
}

В интерактивном тренажере ниже можно по шагам проследить жизненный цикл связного списка: от выделения памяти в куче до точечной переброски указателей при вставке и удалении узлов, а также увидеть, почему поиск нужного значения все равно занимает линейное время.