template <class ListItem>
class List
{
public:
    List() 
        :m_numelements(0)
    {
        m_head = new Link;
        m_tail = new Link;
        m_head->next = m_tail;
        m_tail->next = m_tail;
    };
    ~List()
    {    
        Link* before = m_head;
        Link* after;

        while (before->next != m_tail)
        {
            after = before->next->next;
            delete before->next;
            before->next = after;
        }

        delete m_head;
        delete m_tail;
    };

    void Insert(int index, const ListItem& data)
    {
        Link* before = m_head;
        Link* newnode;

        for (int i=0;i<index;i++)
            before = before->next;
        newnode = new Link(data);
        newnode->next = before->next;
        before->next = newnode;
        m_numelements++;
    }

    void Remove(int index)
    {
        Link* before = m_head;
        Link* after;

        for (int i=0;i<index;i++)
            before = before->next;

        after = before->next->next;
        delete before->next;
        before->next = after;
        m_numelements--;
    }

    ListItem operator[](int index)
    {
        Link* element = m_head->next;
        for (int i=0;i<index;i++)
            element = element->next;
        return element->data;
    }

    int Size()      // number of elements in the list
    {
        return m_numelements;
    }

private:

    // node in our list
    struct Link
    {
        Link()
            :next(NULL) {};
        Link(const ListItem& datain)
            :data(datain),
            next(NULL) {};
        Link*   next;   // next node in list    
        ListItem    data;   // data stored in this node
    };

    // head and tail
    Link*   m_head;
    Link*   m_tail;
    int     m_numelements;
};