#include <iostream>
using namespace std;

/* clas :: list_item */
template <class elemType>
class list_item {
      public :
             list_item( elemType value, list_item<elemType>* item_to_link_to = 0 );
             
             void           next(list_item* link) { _next = link; }
             list_item*     next()                 { return _next; }
             elemType       value()                { return _value;}
             void           value(elemType nValue) { _value = nValue; }
      private:
             elemType _value;
             list_item* _next;
};

template<class elemType>
inline 
list_item<elemType>::
list_item( elemType value, list_item<elemType>* item ) : _value(value)
{
       if(!item)
                _next = 0;
       else {
            _next = item->_next;
            item->_next = this;
            }
}
       


/* class :: ilist  */
template <class elemType>
class list {
      public :
             list () : _at_front(0) , _at_end(0) , _size(0) , current(0) {}
             list( const list &rhs ) : 
	           _at_front( 0 ), _at_end( 0 ) , current(0) { copy( rhs ); }
             list& operator = (const list &list);
             list_item<elemType>* find( elemType value );
             list_item<elemType>* begin() { return _at_front; }
             list_item<elemType>* end()   { return _at_end;   }
             ~list() { remove_all(); }
             int  size();  
             void insert        ( list_item<elemType>* ptr, elemType value );
             void insert_end    ( elemType value );
             void insert_front  ( elemType value );
             void remove        ( elemType value );
             void display       (ostream& os = cout);
             void remove_front  ();
             void remove_all    ();
             void concat        (list mlist);
             void reverse       ();
             list_item<elemType>* init_pos  (list_item<elemType>* pnt) { current = pnt; }
             list_item<elemType>* inc_pos   () { if(current) current = current->next; }
      private:
             void        copy (const list &mlist);
             void        link (list_item<elemType>* first , list_item<elemType>* next);
             void        size_up  (int v = 1);
             void        size_down(int v = 1);
             list_item<elemType>* _at_front  ;
             list_item<elemType>* _at_end    ;
             list_item<elemType>* current    ;
             int         _size     ;
};

template<class elemType>
inline void list<elemType>::size_up(int v)   { _size += v; }

template<class elemType>
inline void list<elemType>::size_down(int v) { _size -= v; }

template<class elemType>
inline int  list<elemType>::size() { return _size; }

template<class elemType>
inline list<elemType>& list<elemType>::operator=(const list &rhs)
{
       _at_front = 0;
       _at_end = 0;
       copy(rhs);
       _size = rhs._size;
       current = _at_front;
       return *this;
}

template<class elemType>
inline void list<elemType>::insert_front( elemType value )
{
       list_item<elemType>* ptr = new list_item<elemType> ( value );
       if(!_at_front)
           _at_front = _at_end = ptr;
       else
           { 
                ptr->next( _at_front );
                _at_front =  ptr;
           } 
       size_up();      
}


template<class elemType>
inline void list<elemType>::insert_end( elemType value )
{
       if(!_at_end)
           _at_end = _at_front = new list_item<elemType>( value );
       else
                _at_end = new list_item<elemType>( value , _at_end );
       size_up();
}
 
template<class elemType>                
inline void list<elemType>::insert( list_item<elemType>* ptr, elemType value )
{
       if(!ptr) 
           insert_front( value );
       else
       {
           size_up();
           new list_item<elemType>( value , ptr );
       }
}
        
template<class elemType>
inline void list<elemType>::copy (const list<elemType> &mlist)
{
       _at_front = _at_end = 0;
       list_item<elemType>* pnt = mlist._at_front;
       while (pnt)
       {
             insert_end( pnt->value() );
             pnt = pnt->next();
       }
}
               
template<class elemType>
inline list_item<elemType>* list<elemType>::find ( elemType value )
{
       list_item<elemType>* iter = _at_front;
       while (iter)
       {
             if( iter->value() == value )
                 break;
             iter = iter->next();
       }
       return iter;
}            

template<class elemType>
inline void list<elemType>::display( ostream& os )
{
       os << "\n( " << _size << ") (";
       list_item<elemType>* iter = _at_front;
       while ( iter )
             {
                os << iter->value();
                iter = iter->next();
             }
       os << ")\n";
} 

template<class elemType>
inline void list<elemType>::remove_front()
{
       list_item<elemType>* ptr = _at_front;
       _at_front = _at_front->next();
       delete ptr;
}

template<class elemType>
inline void list<elemType>::remove_all()
{
  if( !_size ) return;
  while (_at_front)
        remove_front();
  _size =  int( _at_front = _at_end = 0 ) ;
}      

template<class elemType>
inline void  list<elemType>::link (list_item<elemType>* first , list_item<elemType>* next) 
{ 
       if ( first && next ) first->next(next);
       if ( !first )   _at_front =next;
       if ( !next  ) { _at_end  =first; first->next(0); }
} 

template<class elemType>
inline void  list<elemType>::remove ( elemType value )
{     
      list_item<elemType>* prev = 0 , *iter = _at_front , *del;
      int deleted = 0;
      while (del = iter)
      {
               if ( iter->value() == value )
               {
                  ++deleted;
                  link( prev , (iter = iter->next()) );
                  delete del;
               }
               else 
               {
                  prev = iter;
                  iter = iter->next();
               }
      }      
      size_down(deleted);
}

template<class elemType>
inline void list<elemType>::concat ( list<elemType> mlist )
{
       list_item<elemType>* iter = mlist.begin();
       while (iter)
       {
             insert_end(iter->value());
             iter = iter->next();
       }
}

template<class elemType>
inline void list<elemType>::reverse ()
{
       list_item<elemType> *sled = 0 , *iter = _at_front , *store;
       _at_front = _at_end;
       _at_end   = iter   ;
       while (iter)
       {
             store = iter;
             iter  = iter->next();
             (sled = store)->next(sled);
       }
}