#include <iostream>

// implements a doubly-linked list
template <class T>
class MyList
{
    class Node
    {
        public:
            T *data;
            Node *prev;
            Node *next;

            Node()
                : data(NULL)
                , prev(NULL)
                , next(NULL)
            {
                return;
            }

            Node(T const& _data)
                : data(new T(_data))
                , prev(NULL)
                , next(NULL)
            {
                return;
            }

            Node(T const& _data, Node *_prev, Node *_next)
                : data(new T(_data))
                , prev(_prev)
                , next(_next)
            {
                return;
            }

            ~Node()
            {
                // memory leaks are bad, mmmk
                delete data;
            }

            void insert_after(Node *node)
            {
                // hold onto next so we don't lose it
                Node *next_ref = next;

                // next one after us is now the new node we're inserting
                next = node;

                // new node's next becomes the old next
                next->next = next_ref;

                // new node's prev becomes me
                next->prev = this;
            }
    };

    // stores the size of the linked list
    size_t _size;

    // head and tail pointers
    // simply point to next and prev nodes, respectively, do not store data
    Node *head;
    Node *tail;

    public:
        MyList();
        ~MyList();

        // push new data onto the front
        void push_front(T const& data);

        // push new data onto the back

};

template<class T>
MyList<T>::MyList()
                 : _size(0)
                 , head(new Node())
                 , tail(new Node())
{
    head->next = tail;
    tail->prev = head;
    return;
}

template<class T>
MyList<T>::~MyList()
{
    delete head;
    delete tail;
}

template<class T>
MyList<T>::push_front(T const& data)
{

}