#include <iostream>

using namespace std;

// implements a doubly-linked list
template <class T>
class MyList
{
    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(new T(_data))
                : data(_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

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