Linked List Tutorial C++

    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 <iostream>
        #include "LinkedList.h++"

        int main()
        {
            List<int> lst;

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

            // iterate and print
            auto iter = lst.Begin();
            while( iter != lst.End() )
            {
                std::cout << iter->data << " ";
                iter = iter->next;
            }
            std::cout << std::endl;
        }

    A few things to note:

    1. The implementation is a template, this is not as complicated to write as
       you may think.
    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.h++
    For brevity, all error checking is omitted, and const considerations largely ignored

        #pragma once

        #include <cstddef>

        template<typename T>
        class List
        {
            struct Node
            {
                Node* next;
                Node* prev;
                T data;
            };

            struct Sentry // since T might not be default-constructible, we need a separate Sentry type
            {
                Node* next;
                Node* prev;
            };

            Node* sentry;  // this will be our sentry node. it will be of type Sentry, but 'poses' as a Node
            std::size_t size;

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

        public:

            typedef Node* Iterator;


    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.

    Effectively, sentry->next functions as a head pointer, and sentry->prev as a tail pointer.


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

            // this creates a new empty list
            List()
            {
                sentry = (Node*) new Sentry;  // make a new sentry node
                Link( sentry, sentry );       // that points to itself
                size = 0;
            }

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

            // returns size of list
            std::size_t Size() const
            {
                return size;
            }

    Please note that here is no copy-constructor, assignment operator etc. The List class is not
    really complete without those, but the point of this tutorial is to demonstrate benefits of
    using a sentry node, so I cut away some 'clutter'


    Let's see how Begin and End are implemented:

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

            // pointer to end (one past last)
            Iterator End()
            {
                return 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:

        constexpr int 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.

    My apologies for the use of macros, but if you are capable of parsing the replacement
    templates, you don't qualify as a novice, or need this tutorial.

    Note that iterators in the standard library's std::list, std::vector etc mimic
    C-style array iterators with '++' and '*'


    Lets see how adding items to the list is implemented:

            // this inserts new data before 'here'
            Iterator Insert( Iterator here, const T& data )
            {
                Iterator item = new Node{0,0,data};  // create new item. use T's copy-constructor
                Link( here->prev, item );            // link in new node. item comes before here,
                Link( item, here );                  // so in-between `here->prev´ and `here´
                size += 1;                           // update size
                return item;
            }

            // adds new item last
            void PushBack( const T& d )
            {
                Insert( End(), d );
            }

            // adds new item first
            void PushFront( const T& d )
            {
                Insert( Begin(), 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( Iterator here )
            {
                if( here == sentry ) return 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
                delete here;                         // delete item. this will call T's destructor
                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 fulfills some criteria:

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

    Also note that erasing end is NOT harmless on STL containers.


    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
            void PopBack()
            {
                Erase( sentry->prev );  // sentry->prev points to last item
            }

            // remove first item. don't call on empty list
            void PopFront()
            {
                Erase( sentry->next );  // sentry->next points to first item
            }

    I chose to let the Pop functions return void, since T may not be lightweight


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

            // erase all items
            void Clear()
            {
                Iterator cur = sentry->next;
                while( cur != sentry )
                {
                    Iterator nxt = cur->next; // we have to save the next pointer, since deletion invalidates access
                    delete cur;               // this will call T's destructor
                    cur = nxt;
                }
                size = 0;
                // note that the list is left in a usable (but empty) state
                // while(!Empty()) Erase(Begin());  // would have been simpler
            }

            // this destroys the list itself
            ~List()
            {
                Clear();
                delete (Sentry*) sentry;
            }


    A few more convenience functions:

            // returns last item by reference
            T& Back()
            {
                return sentry->prev->data;
            }

            // returns first item by reference
            T& Front()
            {
                return sentry->next->data;
            }

            // non-range-checked index access
            T& operator [] ( std::size_t idx )
            {
                Iterator iter = Begin();
                while( idx-- ) iter = iter->next;  // this loop is why index access in O(n)
                return iter->data;
            }


    Now lastly an integrity check for debugging purpose:

            bool IntegrityCheck()
            {
                if( ! sentry ) return false;                // not even allocated?
                Iterator prev = sentry;
                Iterator curr = sentry->next;
                std::size_t sz = 0;
                while( curr != sentry )
                {
                    if( ! curr ) return false;              // there should be no null pointers in the list
                    if( sz >= size ) return false;          // list is longer than what size suggest
                    ++sz;
                    if( curr->prev != prev ) return false;  // back-pointer dont point to previous item
                    prev = curr;
                    curr = curr->next;
                }
                if( sz != size ) return false;              // list is shorter than what size suggest
                if( sentry->prev != prev ) return false;    // 'tail' pointer don't point to last item

                return true;
            }

        };

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

        #include <iostream>
        #include <cassert>
        #include <string>

        #include "LinkedList.h++"

        // lets create an adaptor, so we can use range-based for loops
        template<typename T> struct ll_iter {
            typename List<T>::Iterator i;
            ll_iter& operator++() { i=i->next; return *this; }
            T& operator*() { return i->data; }
            bool operator!=(ll_iter other) { return i != other.i; }
        };
        template<typename T> ll_iter<T> begin ( List<T>& l ) { return {l.Begin()}; }
        template<typename T> ll_iter<T> end   ( List<T>& l ) { return {l.End()};   }

        using namespace std;

        string TestList()
        {
            List<int> list;

            assert( list.IntegrityCheck() );

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

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

            assert( list.IntegrityCheck() );

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

            assert( list.IntegrityCheck() );

            string str;

            for( auto&& val : list )
            {
                str += to_string( val ) + " ";
            }

            return str; // this should return "6 12 "
        }

        int main() { cout << TestList() << endl; }



    For reference, the whole content of LinkedList.h++ can be accessed at http://pastebin.com/U2CSvtr7