1. Bidirectional linked list - C language implementation

Main functionality of a list

• initialize;
• insert;
• exclude;
• test if empty

Here are these magic lines:

#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;}

To explain my idea, I present classic approach to list implementation, and show code to insert an element in such a list.

.

Such a list is accessed through list head, which is typically a pointer to the first element. Head is NULL for empty list. The end of list is marked by NULL 'next' pointer. 'prev' pointer of the first element is NULL also.

Well, let us insert element 'elem' after '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;
}

If you try to write element removal code, you will see the same problem - only 2 or 4 lines of code are moving link pointers, the rest of bulky code do process special cases - removing 1st element of a list, or removing last element.

The principal idea of presented implementation is "NO NULL pointers". That complicates the drawing but principally simplifies the code.

.

So instead of the pointer to the first element, we use dummy element as a head. And the head for empty list contains no null pointers, all head pointers point to head !

.

Instead of usual check for empty list

  if (head == NULL)

  if (head->next == head)

  if (head->prev == head)

  if (head->next == head->prev)

Funny thing is that described approach looks more complicated on the drawing, but when implemented in code, turns to be straightforward and very simple. Absence of conditional branches gives hope of most efficient performance on modern long-conveyered processors.

And finally the implementation is so simple that it does not require separate compilation module, inlining or defines are sufficient.

My include file which I use for more than decade, is here - an-list.h .

The presented list implementation is intrusive. See famous book of Bjarne Stroustrup for discussion of intrusive and nonintrusive container implementations.