Linked List Tutorial in C using Sentry

    This is a small tutorial showing how to design a linked list in C using a sentry node.
    It's intended for novices that have tried to create a linked list implementation themselves,
    and discovered that there are a lot of special cases needed to handle empty list, first node,
    last node, etc.

    Let's first show intended use, since it affects design:

    Here is a small example creating a list, filling it up with values, and printing them

        #include <stdio.h>
        #define DATA int
        #include "LinkedList.impl"
        #undef DATA

        int main()
        {
            // create and init list
            List* lst;
            Init(&lst);

            // add items
            PushBack( lst, 3 );
            PushBack( lst, 5 );
            PushBack( lst, 7 );

            // iterate and print
            Iterator iter = Begin(lst);
            while( iter != End(lst) )
            {
                printf( "%d ", iter->data );
                iter = iter->next;
            }
            printf("\n");

            // deallocate
            Destroy(lst);
        }

    A few things to note:

    1. The implementation uses a wrapper struct for holding the head pointer, this is useful,
       since this struct can also hold other things, such as the size (item count).
    2. The use of the concept 'iterator'. As the tutorial unfold, it will become clear why
       this is advantageous.


    Let's take a look in the first few lines of LinkedList.impl
    For brevity, all error checking is omitted

        #include <stdbool.h>
        #include <stddef.h>
        #include <stdlib.h>

        typedef struct NodeTag
        {
            struct NodeTag* next;
            struct NodeTag* prev;
            DATA data;
        } Node;

        typedef Node* Iterator;

        typedef struct
        {
            Node* sentry;  /* this will be our sentry node */
            size_t size;
        } List;

    You may notice that this is a doubly linked list, this is very useful even if you don't
    iterate backwards, it simplifies node insertion, node deletion, and last item access.

    Second, there is no head item, but rather a sentry node. In this implementation, the list
    is never really empty, it always contains at least one item (the dummy 'sentry' node).
    This removes the need for ALL special cases, as you will see.


    Let's have a look at a few more lines:

        /* helper function to link 2 nodes */
        static void Link( Iterator n1, Iterator n2 )
        {
            n1->next = n2;
            n2->prev = n1;
        }

        /* helper function to make nodes */
        static Node* MakeNode()
        {
            Node* node = (Node*) malloc( sizeof(Node) );
            return node;
        }

        /* this creates a new empty list */
        void Init( List** lst )
        {
            (*lst) = (List*) malloc( sizeof(List) );  /* create the container */
            Iterator sent = MakeNode();               /* make a new sentry node */
            Link( sent, sent );                       /* that points to itself */
            (*lst)->sentry = sent;
            (*lst)->size = 0;
        }

        /* returns true if list empty */
        bool Empty( List* lst )
        {
            return lst->sentry->next == lst->sentry;  /* when sentry points to itself, the list is empty */
        }

        /* returns size of list */
        size_t Size( List* lst )
        {
            return lst->size;
        }

    A few notes:

    1. The helper functions Link and MakeNode are static. This means they are local to the translation unit.
       (A 'translation unit' is what the standard calls a .c file)
    2. Init creates both the container, and the sentry node. This is consistent with how C is most often used.
       An option would have been to let the use create a List on the stack, or allocate space herself.
    3. Empty & Size are just convenience functions, not really needed.


    Let's see how Begin and End are implemented:

        /* pointer to first item of list, or end if empty */
        Iterator Begin( List* lst )
        {
            return lst->sentry->next;  /* no special-cases needed when using sentry */
        }

        /* pointer to end (one past last) */
        Iterator End( List* lst )
        {
            return lst->sentry;
        }

    As you can see, the sentry node also doubles as the 'one past last' marker.

    If you are unfamiliar with the 'iterator' concept, the begin marker points to the first item,
    and the end marker points one past last item. This can be used for arrays too, like this:

        #define SZ 15
        int arr[SZ];
        int* iter = arr;
        int* end = arr+SZ;
        while( iter != end )
        {
            (*iter) = 3; /* set value for all items to 3 */
            ++iter;
        }

    With an array, the iterator type is an item pointer, item access is done with '*', and
    iterating to next item with '++'

    With our list implementation, the iterator type is a Node*, item access is done with
    '->data' and iterating to next item is done with 'i=i->next'

    With macros, these could be handled the same way. Then you could change mid-project if
    you are using an array or a list, without having to rewrite your algorithms.

    It could look something like this:

        // for array
        #define NXT(i) ++i
        #define ACC(i) *i
        // for list
        #define NXT(i) i=i->next
        #define ACC(i) i->data

    But it's beyond the scope of this tutorial, so let's not delve further into that.


    Lets see how adding items to the list is implemented:

        /* this inserts new data before 'here' */
        Iterator Insert( List* lst, Iterator here, DATA data )
        {
            Iterator item = MakeNode();  /* create new item */
            item->data = data;           /* copy in data */
            Link( here->prev, item );    /* link in new node. item comes before here, */
            Link( item, here );          /* so in-between `here->prev´ and `here´ */
            lst->size += 1;              /* update size */
            return item;
        }

        /* adds new item last */
        void PushBack( List* lst, DATA d )
        {
            Insert( lst, End( lst ), d );
        }

        /* adds new item first */
        void PushFront( List* lst, DATA d )
        {
            Insert( lst, Begin( lst ), d );
        }

    As you can see, the Insert function adds the new item *before* its marker node,
    this way you can easily insert nodes everywhere, even first and last,
    as the PushBack and PushFront functions demonstrate.


    Let's have a look at the erase implementation:

        /* erase one item. erasing end is harmless */
        Iterator Erase( List* lst, Iterator here )
        {
            if( here == lst->sentry ) return lst->sentry;  /* check for end */
            Iterator nxt = here->next;                     /* save next item for return value */
            Link( here->prev, here->next );                /* unlink item. no special cases needed when using sentry */
            free( here );                                  /* delete item */
            lst->size -= 1;                                /* update size */
            return nxt;
        }

    A curious thing is that Erase returns the next item. This is for a reason:

    This is how you iterate a list, while deleting some items that fulfils some criteria:

        Iterator iter = Begin( lst );
        while( iter != End( lst ) )
        {
            DoSomething( iter->data );
            if( SomeCriteria( iter->data ) )
                iter = Erase( lst, iter ); // this is why Erase returns an iterator
            else
                iter = iter->next;
        }


    A List is sometimes used as a stack. We have Push functions, let's have Pop too:

        /* remove last item. don't call on empty list */
        DATA PopBack( List* lst )
        {
            Iterator iter = lst->sentry->prev;  /* sentry->prev points to last item */
            DATA ret = iter->data;              /* save data value for return, before erasure */
            Erase( lst, iter );
            return ret;
        }

        /* remove first item. don't call on empty list */
        DATA PopFront( List* lst )
        {
            Iterator iter = lst->sentry->next;  /* sentry->next points to first item */
            DATA ret = iter->data;              /* save data value for return, before erasure */
            Erase( lst, iter );
            return ret;
        }

    I chose to let the Pop functions return the popped item, since in C it's always copyable,
    and probably lightweight. In C++, I would have chosen 'void' for return type.


    We are nearing the end. Lets have a way to clean up after us.

        /* erase all items */
        void Clear( List* lst )
        {
            Iterator cur = lst->sentry->next;
            Iterator nxt;
            while( cur != lst->sentry )
            {
                nxt = cur->next;
                free( cur );
                cur = nxt;
            }
            lst->size = 0;
            /* note that the list is left in a usable (but empty) state */
            /* while(!Empty(lst)) Erase(lst,Begin(lst)); would have been simpler, but slower */
        }

        /* this destroys the list itself */
        void Delete( List* lst )
        {
            Clear( lst );
            free( lst->sentry );
            free( lst );
        }

    As you can see, Delete takes care of all cleaning up duties, even if the list is not empty.


    A few more convenience functions:

        /* returns last item */
        DATA Back( List* lst )
        {
            return lst->sentry->prev->data;
        }

        /* returns first item */
        DATA Front( List* lst )
        {
            return lst->sentry->next->data;
        }

        /* return iterator by index */
        Iterator ByIndex( List* lst, size_t idx )
        {
            if( idx >= lst->size ) return End(lst);  /* check for out of bounds, return end marker if so */
            Iterator iter = Begin( lst );
            while( idx-- ) iter = iter->next;        /* this loop is why index access in O(n) */
            return iter;
        }

    Note that Front & Back could have been defined as macros, like this:

        #define Back(l) l->sentry->prev->data

    That way they could be used as lvalues, like:

        Back(lst) += 3;  // add 3 to last item


    Now lastly an integrity check for debugging purpose:

        bool IntegrityCheck( List* lst )
        {
            if( ! lst ) return false;
            if( ! lst->sentry ) return false;
            Iterator prev = lst->sentry;
            Iterator curr = lst->sentry->next;
            size_t sz = 0;
            while( curr != lst->sentry )
            {
                if( ! curr ) return false;
                if( sz >= lst->size ) return false;
                ++sz;
                if( curr->prev != prev ) return false;
                prev = curr;
                curr = curr->next;
            }
            if( sz != lst->size ) return false;
            if( lst->sentry->prev != prev ) return false;

            return true;
        }

    That concludes the content of LinkedList.impl, lets have a complete example:


        #define DATA int
        #include "LinkedList.impl"
        #undef DATA

        #include <stdio.h>
        #include <assert.h>

        char* TestList()
        {
            List* list;
            Init( &list );

            assert( IntegrityCheck( list ) );

            PushBack( list, 1 );
            PushBack( list, 2 );
            PushBack( list, 3 );
            PushBack( list, 4 );

            /* list should be 1, 2, 3, 4 */

            assert( IntegrityCheck( list ) );

            Node* iter = Begin( list );
            while( iter != End( list ) )
            {
                iter->data *= 3; /* triple values to 3, 6, 9, 12 */
                if( iter->data % 2 )
                    iter = Erase( list, iter ); /* remove odd, now 6, 12 */
                else
                    iter = iter->next;
            }

            assert( IntegrityCheck( list ) );

            static char buffer[256];
            char* str = buffer;

            str[0] = '\0';

            iter = Begin( list );
            while( iter != End( list ) )
            {
                str += sprintf( str, "%d ", iter->data ); /* sprintf returns number of chars written, */
                                                          /* so str is moved to end of string */
                iter = iter->next;
            }

            Delete( list );

            return buffer; /* this should return "6 12 " */
        }

        int main() { printf("%s\n",TestList()); }



    For reference, the whole content of LinkedList.impl can be accessed at http://codepad.org/eY8vjUwg