Bidirectional linked list - реалізація на мові програмування C

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

• ініціалізація;
• вставка елемента;
• видалення;
• перевірка на пустий список

Ось ці рядки:

#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 для пустого списку. Кінець списку позначається нульовим 'next' вказівником. Вказівник 'prev' першого элементу також зазвичай нульовий.

Розглянемо вставку елемента '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;
}

При спробі написати код для видалення елемента видно ту ж саму проблему - тільки 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 реалізацій контейнерів.