1. Bidirectional linked list - C language implementation

During more than 15 years I use very simple and efficient code for bidirectional lists. Note that even now there are lot of systems which must be programmed in C (not C++) language, and having nice portable implementation of a list is indispensable.

Main functionality of a list

  • initialize;
  • insert;
  • exclude;
  • test if empty
takes 8 lines of code.

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;}
I expect that at this point you should not believe in above code (that is tooo simple to be truue !!), but I hope you are curious enough to investigate what it's all about, and read further on.

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;
}
Pay attention to the coloring of the code above. Actually only blue lines of code are doing really the insertion. The rest of code (in red) is special cases when something is NULL - at the head or at the tail of a list.

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)
we have another check, more complicated, but in three variations:
  if (head->next == head)
or
  if (head->prev == head)
or
  if (head->next == head->prev)
Come on, just kidding, nothing difficult !

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.

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