linked list good taste

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

• Введение
• Код
  • Версия CS101
  • Более элегантное решение
• Как это работает?
  • Интеграция указателя головы
  • Поддержание ручки
• Выходя за рамки
  • Вставка перед существующими предметами
  • Быстрый рефактор
  • Реализация insert_before ()
• Заключение

Введение

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

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

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

Фрагменты кода, которые он представляет, являются псевдокодом в стиле C и достаточно просты, чтобы следовать. Однако, как упоминает Линус в комментарии, фрагментам не хватает концептуального объяснения, и не сразу очевидно, что на самом деле работает более элегантное решение.

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

Код

Основная структура данных для отдельного списка целых чисел показана на рисунке 1.

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

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

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

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

struct list {
        struct list_item * head ;
};
typedef struct list list ;

Мы также включаем (минимальный) API:

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

При этом давайте посмотрим на реализации remove_cs101() и remove_elegant() . Код этих примеров верен псевдокоду из примера Linus, а также компилируется и работает.

Версия CS101

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

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

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

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

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

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

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

Как это работает?

Ключевое понимание заключается в том, что использование косвенного указателя p имеет две концептуальные преимущества:

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

Давайте посмотрим на каждый из этих моментов по очереди.

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

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

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

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

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

В коде это переводится как p = &(*p)->next , что означает мы

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

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

Поддержание ручки

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

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

 while ( * p != target )

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

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

Выходя за рамки

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

Вставка перед существующими предметами

Во -первых, давайте добавим следующее объявление в список API в list.h .

 void insert_before ( list * l , list_item * before , list_item * item );

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

Быстрый рефактор

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

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

и используйте эту функцию в remove_elegant()

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

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

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

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

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

Заключение

Предпосыой более элегантного решения для удаления элементов является одно простое изменение: использование косвенного указателя list_item ** на итерацию по указателям на элементы списка. Все остальное течет оттуда: нет необходимости в специальном случае или ветвлении, и одного итератора достаточно, чтобы найти и удалить целевой элемент. Также выясняется, что тот же подход обеспечивает элегантное решение для вставки предметов в целом и для вставки перед существующим элементом в частности.

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