Линейный список. Физическое представление. Итераторы: безопасная навигация

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

Зачем это нужно?

Итератор необходим для безопасной и универсальной навигации по элементам структуры данных. В языке C указатели можно легко инкрементировать (i++). Это отлично работает для сплошных массивов, но если список динамический и его узлы разбросаны в памяти, операция ptr++ приведет к выходу за пределы памяти и краху программы.

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

Линейный список. Физическое представление. Итераторы: как они организованы в C

Итератор специально упаковывается в структуру (struct), внутри которой прячется "сырой" указатель на узел списка. Эта простая упаковка лишает программиста возможности случайно применить встроенную арифметику указателей Си.

/* Сырой узел списка */
typedef struct Item {
    struct Item* prev;
    struct Item* next;
    int data;
} Item;

/* Итератор (обертка для безопасности) */
typedef struct {
    Item* node;
} Iterator;

Абстрактные операции

Управление итератором осуществляется через специальные функции:

• Next(i) / Prev(i): Возвращает итератор, указывающий на следующий (или предыдущий) элемент. Внутри функции безопасно извлекается i.node->next.
• Equal(i1, i2) / NotEqual(i1, i2): Сравнивают два итератора, указывают ли они на один и тот же физический элемент. Это нужно для проверки условия выхода из цикла.
• Fetch(i): Функция "разыменования". Читает и возвращает полезную нагрузку (data) из узла, на который сейчас указывает итератор.

Универсальный цикл обхода списка

Вместо перебора по индексам (дискретному времени), обход списка с помощью итератора выглядит так (классическая идиома):

Iterator i;
Iterator last = Last(&list); /* Терминатор (элемент ПОСЛЕ конца списка) */

for (i = First(&list); NotEqual(i, last); i = Next(i)) {
    int value = Fetch(i);
    /* Действие с элементом... */
}