#include<stdio.h>

#include<conio.h>

#include<iostream.h>

template<class T>

class List

{

protected:

class node

{ public:

node(const T& data = T(), node* prev=0, node* next=0)

: _data(data), _prev(prev), _next(next)

{ if(_prev==0) _prev = this ;

if(_next==0) _next = this ;

}

T _data ;

node* _prev , * _next ;

};

node* _ ;

int _size ;

public:

class Iterator

{ friend class List ;

public:

Iterator(node* p) : _p(p) { }

T& operator*() { return _p->_data; }

void operator=(const Iterator& it) { _p = it._p; }

int operator==(const Iterator& it) { return _p==it._p; }

int operator!=(const Iterator& it) { return _p!=it._p; }

Iterator operator++(int)

{ Iterator it(_p);

_p = _p->_next ;

return it ;

}

Iterator operator++() { _p=_p->_next; return *this;}

Iterator operator--(int)

{ Iterator it(_p);

_p = _p->_prev ;

return it ;

}

Iterator operator--() { _p=_p->_prev; return *this;}

// private:

List<T>::node* _p ;

};

List() ;

~List() ;

int size() const ;

int empty() const ;

T& front() const ;

T& back() const ;

Iterator begin() { return Iterator(_->_next);}

Iterator end() { return Iterator(_->_prev);}

void push_front(const T&) ;

void push_back(const T&) ;

void printList() ;

void showList();

void clear() ;

Iterator insert(Iterator& it, const T& x)

{it._p->_prev = it._p->_prev->_next = new node(x, it._p->_prev, it._p);

it._p = it._p->_prev ; ++_size ;

return it ; }

void insert(Iterator& it,int n,const T& x)

{ node* p = it._p , * q = p->_prev ;

for(int i=0; i<n; i++)

p = p->_prev = new node(x,q,p) ;

it._p = it._p->_prev = q->_next = p ;

_size += n ;

}

void erase(Iterator& it)

{ if(_size==0) return ;

node* p = it._p ; //temp *p

p->_prev->_next = p->_next ;

p->_next->_prev = p->_prev ;

it._p = p->_next ;

delete p ;

--_size ;

}

};

template<class T>

List<T>::List() : _size(0)

{ _ = new node() ; }

template<class T>

List<T>::~List()

{ node* p = _->_next ;

while(p!= _ )

{ node* pp = p->_next ;

delete p ;

p = pp ;

}

delete _ ;

}

template<class T>

int List<T>::size() const

{ return _size ; }

template<class T>

int List<T>::empty() const

{ return (_size==0 ) ; }

template<class T>

T& List<T>::front() const

{ return _->_next->_data ; }

template<class T>

T& List<T>::back() const

{ return _->_prev->_data ; }

template<class T>

void List<T>::push_front(const T& x)

{ _->_next = _->_next->_prev = new node( x , _ , _->_next ) ;

++_size ;

}

template<class T>

void List<T>::push_back(const T& x)

{ _->_prev = _->_prev->_next = new node( x , _->_prev , _ ) ;

++_size ;

}

template<class T>

void List<T>::printList()

{ node* p = _->_next ;

while(p!= _ )

{ cout<<p->_data<<" " ;

p = p->_next ;

}

}

template<class T>

void List<T>::clear()

{ node* p = _ , * q=p->_next ;

while(q!=p)

{ p->_next = q->_next ;

q->_next->_prev = p ;

delete q ;

q = p->_next ;

}

_size = 0 ;

}

template<class T>

void List<T>::showList()

{ Iterator ip(_),it(_->_next) ;

while(it!=ip)

{ cout<<*(it)<<" ";

++it;

}

}

void main()

{

List<int> lst ;

clrscr() ;

lst.push_front(3) ; lst.push_front(9) ;

lst.push_back(8) ; lst.push_back(4) ;

lst.printList() ;

cout<<endl<<lst.front()<<" "<<lst.back() ;

getch();

cout<<endl;

lst.erase(lst.begin()) ;

cout<<*(lst.begin())<<" "<<*(lst.end()) ;

getch();

cout<<endl;

lst.showList() ;

getch() ;

}