LinkedList.h++

// this is part of a tutorial that can be found here: http://pastebin.com/DXunz58Q

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

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

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

    // 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 );
    }

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

    // 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
    }

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

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

#ifndef NDEBUG

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

#endif

};