Bidirectional linked list - реализация на языке C

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

Основная функциональность работы со списком:

  • инициализация;
  • вставка элемента;
  • удаление;
  • проверка на пустой список
занимают 8 строчек кода.

Вот эти удивительные строчки:

#define AN_LIST_Init(x)         {(x)->next=(x)->prev=(x);     }
#define AN_LIST_IsEmpty(x)      ((x)->next==(x)                )

#define AN_LIST_Insert(x,y)     {((y)->next=(x)->next)->prev=(y);\
                                 ((x)->next=(y))->prev=(x);   }

#define AN_LIST_InsertB4(x,y)   {((y)->prev=(x)->prev)->next=(y);\
                                 ((x)->prev=(y))->next=(x);   }

#define AN_LIST_Exclude(x)      {((x)->prev)->next=(x)->next;\
                                 ((x)->next)->prev=(x)->prev;}
Полагаю, что в этот момент читатель думает "бред какой-то" (слишком просто чтобы быть правдой). Но если стало интересно, что это за бред, читаем дальше.

Чтобы объяснить в чем основная идея такой реализации списка, я представлю классическое построение списка, и приведу код вставки элемента в классический список.

.

Доступ к такому списку осуществляется через голову списка, которая обычно есть указателем на первый элемент списка. Голова списка равна NULL для пустого списка. Конец списка обозначен нулевым NULL 'next' указателем. Указатель 'prev' первого элемента также обычно равен NULL.

Рассмотрим вставку элемента 'elem' в список после элемента 'cur'.

void classic_list_insert_after( struct ELEM * cur, struct ELEM * elem)
{
  if( cur == NULL)              /* insert at the head of list */
  {
     elem->next = head;
     elem->prev = NULL;
     head = elem;
  }
  else
  {
     elem->next = cur->next;
     elem->prev = cur;
     cur->next = elem;
  }
  if( elem->next != NULL)
     elem->next->prev = elem;
}
Обратите внимание на расцветку кода. Собственно, только синие строки кода выполняют вставку. Весь остальной код отмеченный красным цветом, обрабатывает особые случаи - когда что-то равно NULL - в голове или хвосте списка.

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

Принципиальная идея предлагаемой реализации - "нет NULL указателям". Это усложняет блок-схему списка, но категорически упрощает код.

.

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

.

Вместо классической проверки, является ли список пустым

  if (head == NULL)
будет другая проверка, бОлее сложная, но зато их три !
  if (head->next == head)
или
  if (head->prev == head)
или
  if (head->next == head->prev)
В общем, шучу, что сложная, все очень просто и натурально.

Меня удивляет то, что на блок схемах (диаграмах) такая реализация списка выглядит бОлее сложной, чем реализация с нулевыми указателями. Но при ее кодировании на языке программирования она оказывается предельно лаконичной и естественной. Таки есть концептуальное различие между нашим восприятием (читай алгоритмами нашего мозга), и классическими языками программирования ;)

Отсутствие условного ветвления в алгоритме дает надежду об очень эффективном исполнении на современных процессорах с конвейером команд.

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

Мой хедер файл, который я использую больше десятилетия, можно загрузить здесь - an-list.h .

Представленная реализация списка является интрузивной, согласно классификации Страуструпа (Bjarne Stroustrup), см. его знаменитую книгу The C++ Programming Language по поводу intrusive и nonintrusive реализаций контейнеров.

Home  
Terms and Conditions (c) 2005, 2006, 2008, 2009, 2011, 2012, ..., 2023 NAN