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 fulfils 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://codepad.org/78kxUIUZ