[Перевод] Связные списки, трюки с указателями и хороший вкус08.12.2020 23:02

В интервью на TED 2016 (14:10) Линус Торвальдс рассказывает о хорошем стиле программирования. В качестве примера приводит два варианта удаления элементов из односвязных списков (см. ниже). В первом варианте есть специальный случай, а в другом — нет. Линус предпочитает второй.

Его комментарий:

[…] Не надо размышлять, почему здесь нет оператора if. Важно посмотреть на задачу с другой стороны и переписать её так, чтобы особый случай исчез и стал обычным случаем, и это хороший код. — Л. Торвальдс


В качестве примера Линус показывает достаточно простой псевдокод в стиле Си. Но не даёт концептуального объяснения. Поэтому не сразу понятно, как работает косвенный указатель.
Подробно разберём это решение и его преимущества. В качестве бонуса показано не только удаление, но и вставка элемента через косвенную адресацию.
Базовая структура данных для односвязного списка целых чисел показана на рис. 1.

e7dfa79ebd71ac9ea4cdefa4eea5d4d3.png
Рис. 1. Односвязный список из целых чисел

Числа — это произвольно выбранные целочисленные значения, а стрелки соответствуют указателям: head — это указатель типа IntListItem*, все блоки являются экземплярами структуры IntListItem, каждый со своей переменной (nextв коде) типа IntListItem*, которая указывает на следующий элемент.

Реализация структуры данных на Си: 

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;


Также (минимальный) API: 

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);


Теперь рассмотрим реализации remove_cs101() и remove_elegant(). Код примеров не противоречит псевдокоду из примера Линуса, но компилируется и запускается.

Базовая версия


a863a1c83efc1e596bd76922f6b5239a.png
Рис. 2. Концептуальная модель структуры данных списка в базовом алгоритме

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}


В стандартном подходе два указателя обхода cur и prev, которые отмечают текущую и предыдущую позицию обхода в списке соответственно. cur начинает с головы списка head и продвигается вперёд, пока цель не будет найдена. В свою очередь, prev начинается с NULL и впоследствии обновляется на предыдущее значение cur при каждом следующем продвижении вперёд. Когда цель найдена, алгоритм проверяет, не равен ли prev нулю. Если так, то cur указывает на первый элемент в списке, и в этом случае удаление означает перемещение головы списка вперёд.

Более элегантное решение


В более элегантной версии меньше кода, и она не требует отдельной ветви для удаления первого элемента в списке.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}


В коде применяется косвенный указатель p, содержащий адрес указателя на элемент списка, начиная с адреса head. В каждой итерации этот указатель расширяется, чтобы включить адрес указателя на следующий элемент списка, то есть адрес элемента next в текущем IntListItem. Когда указатель на элемент списка (*p) равен target, мы выходим из цикла поиска и удаляем элемент из списка.
Косвенный указатель p даёт два концептуальных преимущества:

  1. Позволяет интерпретировать связный список таким образом, что указатель head становится неотъемлемой частью структуры данных. Это устраняет необходимость в специальном случае для удаления первого элемента.
  2. Также позволяет оценить состояние цикла while без необходимости отпускать указатель, указывающий на target. Это позволяет изменять указатель на target и обходиться одним итератором, в отличие от prev и cur.


Рассмотрим каждый пункт по очереди.

Интеграция указателя head


Стандартная модель интерпретирует связный список как последовательность экземпляров IntListItem. Начало последовательности можно получить с помощью указателя head. Это приводит к концептуальной модели, показанной выше на рис. 2. Указатель head просто рассматривается как дескриптор для доступа к началу списка. prev и cur являются указателями типа IntListItem* и всегда указывают на элемент или NULL.

Элегантная реализация использует схему косвенной адресации, которая даёт другое представление о структуре данных:

77abb45a4a54b7707dced868b9462a20.png
Рис. 3. Концептуальная модель структуры данных списка в более элегантном решении

Здесь p представляет тип IntListItem** и содержит адрес указателя на текущий элемент списка. Когда указатель продвигается вперёд, его адрес меняется на следующий элемент.

В коде это выглядит как p = &(*p)->next:

  1. (*p): разыменовать адрес указателя на текущий элемент списка.
  2. ->next: снова разыменовать этот указатель и выбрать поле с адресом следующего элемента.
  3. &: взять адрес этого поля (то есть получить указатель на него).


Это соответствует интерпретации структуры данных, где список представляет собой последовательность указателей на элементы IntListItem (рис. 3).

Последний штрих


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

Если p содержит адрес указателя на элемент списка, сравнение в цикле поиска становится таким: 

while ((*p) != target) {
    ...
}


Цикл поиска завершится, если (*p) равно target, и как только это произойдёт, мы всё равно сможем изменить (*p), так как удерживаем его адрес p. Таким образом, несмотря на итерацию цикла до конца, сохраняется дескриптор (адрес поля next или указатель head), который можно использовать для непосредственного изменения указателя на элемент.

Вот почему мы можем изменить входящий указатель на элемент, чтобы он указывал на другое место, используя *p = target->next, и поэтому нам не нужны указатели обхода prev и cur для удаления элемента.


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

Вставка перед существующим элементом


Во-первых, добавим следующую декларацию в list.h: 

void insert_before(IntList *l, IntListItem *before, IntListItem *item);


Функция возьмёт указатель на список l, указатель перед элементом в этом списке и указатель на новый элемент списка, который функция вставит перед ним.

Быстрый рефакторинг


Прежде чем двигаться дальше, оформим цикл поиска в отдельную функцию: 

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}


и используем её в remove_elegant(): 

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}


Реализация insert_before ()


Используя find_indirect(), легко реализовать insert_before(): 

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}


Особенно радует цельная семантика для крайних случаев: если before указывает на заголовок списка, новый элемент будет вставлен в начало, если before является нулевым или недействительным (то есть не существует в l), новый элемент будет добавлен в конце.
Предпосылкой более элегантного решения для удаления элементов является одно простое изменение: косвенный указатель IntListItem** для итерации указателей на элементы списка. Всё остальное вытекает оттуда: отпадает необходимость в специальных случаях или ветвлениях. Достаточно одного итератора, чтобы найти и удалить целевой элемент. И оказывается, что тот же подход обеспечивает элегантное решение для вставки вообще и для вставки перед существующим элементом в частности.

Итак, возвращаясь к первоначальному замечанию Линуса: это показатель хорошего вкуса? Трудно сказать. Но явно налицо творческое и очень элегантное решение хорошо известной задачи.

© Habrahabr.ru