#include <assert.h>
#include <iostream.h>

template <class T>
class ListNode {
public:
    ListNode(T* init_elem, ListNode<T>* init_next)
        : element(init_elem), next(init_next) {}
    T * element;         // Stores items externally
    ListNode<T> * next;  // Note recursive template use
};

template <class T>
class LinkedList {
public:
    LinkedList() { head = NULL; }
    void append(T* value);
    T* removeFront();

private:
    ListNode<T> * head;  // Note use of previous template
};

template <class T>
void LinkedList<T>::append(T* value)
{
    if (head == NULL) {
        head = new ListNode<T>(value, NULL);
    } else {
        ListNode<T> * cursor = head;
        while (cursor->next != NULL)
            cursor = cursor->next;
        cursor->next = new ListNode<T>(value, NULL);
    }
}

template <class T>
T* LinkedList<T>::removeFront()
{
    assert(head != NULL);
    ListNode<T>* old_head = head;
    T* old_element = old_head->element;
    
    head = head->next;
    delete old_head;
        
    return old_element;
}


int main()
{
    LinkedList<int> ilist;

    int x = 1, y = 2, z = 3;

    ilist.append( &x );
    cout << *ilist.removeFront() << endl;

    ilist.append( &y );
    cout << *ilist.removeFront() << endl;

    ilist.append( &z );
    cout << *ilist.removeFront() << endl;

    return 0;
}