#include
     
      #include
      
       using namespace std;template
       
        struct Node{     Node(const T& d)         :_data(d)         ,_next(NULL)         , _prev(NULL)     {}     T _data;     Node
        
         * _next;     Node
         
          * _prev;};template
          
           class DList{public:     DList();     ~DList();     DList(const DList
           
            & list);     DList
            
             & operator=(const DList
             
               list);     void PushBack(const T& d);     void PopBack();     void PushFront(const T& d);     void PopFront();     Node
              
               * Find(const T& d);     void Insert(Node
               
                * pos, const T& d);     void Reverse();     void Sort();     void Remove(const T& d);     void RemoveAll(const T& d);     void Erase(Node
                
                 * pos);     friend ostream& operator<<
                 
                  (ostream& output, const DList
                  
                   & s);private:     Node
                   
                    * _head;     Node
                    
                     * _tail;};template
                     
                          DList
                      
                       ::DList()    :_head(NULL)    ,_tail(NULL)    {}template
                       
                        DList
                        
                         ::~DList(){     Node
                         
                          * cur = _head;     while (cur)     {          Node
                          
                           * del = cur;          cur = cur->_next;          delete del;     }}template
                           
                             DList
                            
                             ::DList(const DList
                             
                              & list)    :_head(NULL)    ,_tail(NULL){         Node
                              
                               * cur = list._head;         while (cur)    {      PushBack(cur->_data);      cur = cur->_next;     }}template
                               
                                DList
                                
                                 & DList
                                 
                                  ::operator=(const DList
                                  
                                    list){     swap((Node
                                   
                                    *)_head, (Node
                                    
                                     *)list._head);     swap((Node
                                     
                                      *)_tail, (Node
                                      
                                       *)list._tail);     return *this;}template
                                       
                                        void DList
                                        
                                         ::PushBack(const T& d){     if (_head == NULL)     {          _head = new Node
                                         
                                          (d);          _tail = _head;     }     else     {          Node
                                          
                                           * NewNode = new Node
                                           
                                            (d);          _tail->_next = NewNode;          NewNode->_prev = _tail;          _tail = NewNode;     }}template
                                            
                                             void DList
                                             
                                              ::PopBack(){     if (_head == NULL)     {          return;     }     else if (_head== _tail)     {          delete _head;          _tail = NULL;          _head = NULL;     }     else     {          _tail = _tail->_prev;          delete _tail->_next;          _tail->_next = NULL;     }}template
                                              
                                               void DList
                                               
                                                ::PushFront(const T& d){     Node
                                                
                                                 * NewNode = new Node
                                                 
                                                  (d);     if (_head == NULL)     {          _head = NewNode;          _tail = _head;          return; }     NewNode->_next = _head;     _head->_prev = NewNode;     _head = NewNode;}template
                                                  
                                                   void DList
                                                   
                                                    ::PopFront(){     if (_head == NULL)      return;     else if (_head==_tail)     {          delete _head;          _head = NULL;          _tail = NULL;      }     else     {          _head = _head->_next;          delete _head->_prev;     }}template
                                                    
                                                     ostream& operator<<(ostream& output, const DList
                                                     
                                                      & s){     Node
                                                      
                                                       * cur = s._head;     while (cur)     {      cout<< cur->_data << "<->";      cur = cur->_next;     }     output << "over";     return output;}template
                                                       
                                                        Node
                                                        
                                                         * DList
                                                         
                                                          ::Find(const T& d){     Node
                                                          
                                                           * cur = _head;     while (cur)    {          if (cur->_data == d)           return cur;          cur = cur->_next;     }     return NULL;}template
                                                           
                                                            void DList
                                                            
                                                             ::Insert(Node
                                                             
                                                              * pos, const T& d){     if (pos == NULL)      return;     Node
                                                              
                                                               * NewNode = new Node
                                                               
                                                                (d);     if (pos == _tail)     {          _tail->_next = NewNode;          NewNode->_prev = _tail;          _tail = NewNode;     }     else     {          NewNode->_next = pos->_next;          NewNode->_prev = pos;          pos->_next = NewNode;          NewNode->_next->_prev = NewNode;     }}template
                                                                
                                                                 void DList
                                                                 
                                                                  ::Reverse(){     Node
                                                                  
                                                                   * cur = _head;     while (cur)     {          swap(cur->_next, cur->_prev);          cur = cur->_prev;     }     swap(_head, _tail);}template
                                                                   
                                                                    void DList
                                                                    
                                                                     ::Sort(){     Node
                                                                     
                                                                      * cur = _head;     Node
                                                                      
                                                                       * end = NULL;     while (cur != end)     {      while (cur && cur->_next != end)      {           if (cur->_data > cur->_next->_data)           {            T tmp = cur->_data;            cur->_data = cur->_next->_data;            cur->_next->_data = tmp;           }           cur = cur->_next;      }      end = cur;      cur = _head;     }}template
                                                                       
                                                                        void DList
                                                                        
                                                                         ::Remove(const T& d){     Node
                                                                         
                                                                          * cur = _head;     while (cur)     {        Node
                                                                          
                                                                           * del = cur;      if (cur->_data == d)      {       if (cur == _head)       {            _head = _head->_next;            _head->_prev = NULL;       }       else if (cur!=_head && cur==_tail)       {            _tail = _tail->_prev;            _tail->_next = NULL;       }       else       {            cur->_prev->_next = cur->_next;       }       delete del;       break;      }      cur = cur->_next; }}template
                                                                           
                                                                            void DList
                                                                            
                                                                             ::RemoveAll(const T& d){     Node
                                                                             
                                                                              * cur = _head;     while (cur)     {      Node
                                                                              
                                                                               * del = cur;      if (cur->_data == d)      {       if (cur == _head)       {            _head = _head->_next;            _head->_prev = NULL;            cur = _head;       }       else if (cur != _head && cur == _tail)       {            _tail = _tail->_prev;            _tail->_next = NULL;            cur = NULL;       }       else       {            cur->_prev->_next = cur->_next;            cur->_next->_prev = cur->_prev;            cur = cur->_next;       }       delete del;      }  else      cur = cur->_next; }}template
                                                                               
                                                                                void DList
                                                                                
                                                                                 ::Erase(Node
                                                                                 
                                                                                  * pos){     if (pos == NULL)      return;     if (pos == _head && pos == _tail)     {          _head = NULL;          _tail = NULL;          return;     }     if (pos == _head)     {          _head = _head->_next;          _head->_prev = NULL;     }     else if (pos == _tail)     {          _tail = _tail->_prev;          _tail->_next = NULL;     }     else     {          pos->_prev->_next = pos->_next;          pos->_next->_prev = pos->_prev;     } delete pos;}