#include <iostream>

using namespace std;

// implements a doubly-linked list
template <class T>
class MyList
{
    class NullPointer {};

    class Node
    {
        public:
            T     data;
            Node* prev;
            Node* next;

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

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

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

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

            void insert_after(Node* new_node)
            {
                // bail, we got a null pointer
                if (new_node == NULL)
                    throw NullPointer();

                // new node's next is current next
                new_node->next = next;

                // new node's previous becomes me
                new_node->prev = this;

                // current next's previous is the new node
                next->prev = new_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 = new_node;
            }
    };

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

        void print()
        {
            Node* cursor = head;

            while (cursor != NULL)
            {
                cout << cursor->data << endl;
                cursor = cursor->next;
            }
        }

};

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>
void MyList<T>::push_front(T const& data)
{
    Node* new_node = new Node(data);

    head->insert_after(new_node);
}

int main()
{
    MyList<string> my_list;

    my_list.push_front("one");
    my_list.push_front("two");
    my_list.push_front("three");

    my_list.print();
}