#include <stdio.h>
#include <stdlib.h>

template<typename T>
struct list
{
    struct node
    {
        node *prev, *next;
        T value;

        node(T v) { value = v; }
        node *advance() { return next; }
    };

    node *first, *last;

    node *begin() { return first; }
    node *end()   { return NULL; }

    list()  { first = NULL; last = NULL; }
    ~list() { clear(); }

    void insert(node *where, T v)
    {
        node *newnode = new node(v);
        newnode->prev = where ? where->prev : last;
        newnode->next = where;
        if(newnode->prev)  newnode->prev->next = newnode;
        if(where) where->prev = newnode;
        if(where == first) first = newnode;
        if(!where) last = newnode;
    }
    void push_front(T v) { insert(begin(), v); }
    void push_back(T v)  { insert(end(), v); }
    void erase(node *where)
    {
        node* prev = where->prev;
        node* next = where->next;
        if(prev) prev->next = next;
        if(next) next->prev = prev;
        if(where == first) first = next;
        if(where == last) last = prev;
        delete where;
    }
    void clear() { while(first) erase(first); }
};

int main(void)
{
    list<int> mylist;
    mylist.push_back(1);
    mylist.push_back(5);
    mylist.push_front(8);
    mylist.push_back(3);

    for(auto i = mylist.begin(); i != mylist.end(); i = i->advance())
        printf("%d ", i->value);
    printf("\n");

    list<const char*> mylist2;
    mylist2.push_back("Europe");
    mylist2.push_back("Asia");
    mylist2.push_front("Africa");
    mylist2.push_back("Antarctica");

    for(auto i = mylist2.begin(); i != mylist2.end(); i = i->advance())
        printf("%s ", i->value);
    printf("\n");

    return 0;
}