#include <string>
using namespace std;

template <class  T> class list;

template <class  T> class Node{
    friend class list<T>;
public:
    T data;
    Node *next;
    Node *prev;

    Node(){ next = prev = NULL; };
};

template <class  T> class list{
public:
    typedef Node<T> * Position;
    list();
    ~list();
    Position  first();
    Position  last();
    bool isEmpty();
    void clear();

private:
    Position fir, las;
    int size;
};

template <class T>
list<T>::list(){
    size = 0;
    fir = las = NULL;
}

template <class  T>
typename list<T>::Position  list<T>::first(){
    return fir;
}

template <class  T>
typename list<T>::Position   list<T>::last(){
    return las;
}

template <class  T>
bool list<T>::isEmpty(){
    return first() == NULL;
}

template <class  T>
void list<T>::clear(){
    Position temp = fir;

    while (temp != NULL){
        Position temp2 = temp;
        temp = temp->next;
        delete temp2;
    }

    fir = las = NULL;

    size = 0;
}