#include <iostream>#include <assert.h>using namespace std;typedef int DataType;struct ListNode{ ListNode* _next; ListNode* _prev; DataType _data; ListNode(DataType x)  :_next(NULL)  , _prev(NULL)  , _data(x) {}};typedef ListNode Node;class List{public: List()  :_head(NULL)  ,_tail(NULL) {} List(const List& l)  :_head(NULL)  ,_tail(NULL) {  Copy(l); } void Copy(const List& l) {  Node* cur = l._head;  while (cur)  {   PushBack(cur->_data);   cur = cur->_next;  } } List& operator=(const List& l) {  Destory();  Copy(l);  return *this; } ~List() {  Destory(); } void Destory() {  if (_head)  {   Node* cur = _head;   while (_head)   {    cur = _head;    _head = _head->_next;    delete cur;   }   _head = _tail = NULL;  } } void PushBack(DataType x) {  if (_head == NULL)  {   Node* tmp = new Node(x);   tmp->_next = tmp->_prev = NULL;   _head = _tail = tmp;  }  else  {   Node* tmp = new Node(x);   _tail->_next = tmp;   tmp->_prev = _tail;   _tail = tmp;  } } void PopBack() {  if (_head == NULL)  {   return;  }  else if (_head->_next == NULL)  {   delete _head;   _head = _tail = NULL;  }  else  {   Node* tmp = _tail;   _tail = _tail->_prev;   _tail->_next = NULL;   delete tmp;  } } void PushFront(DataType x) {  if (_head == NULL)  {   _head = _tail = new Node(x);  }  else  {   Node* tmp = new Node(x);   tmp->_next = _head;   _head->_prev = tmp;   _head = _head->_prev;  } } void PopFront() {  if (_head == NULL)  {   return;  }  else if (_head->_next == NULL)  {   delete _head;   _head = _tail = NULL;  }  else  {   Node* tmp = _head;   _head = _head->_next;   delete tmp;   _head->_prev = NULL;  } } Node* Find(DataType x) {  Node* cur = _head;  while (cur)  {   if (cur->_data == x)    return cur;   cur = cur->_next;  }  return NULL; } // 在pos的前面插入x void Insert(Node* pos, DataType x) {  assert(pos);  if ((pos == 0) || (pos->_prev == NULL))  {   PushFront(x);  }  else  {   Node* font = pos->_prev;   Node* tmp = new Node(x);   tmp->_prev = font;   tmp->_next = pos;   font->_next = tmp;   pos->_prev = tmp;  } } //刪除pos位置的元素 void Erase(Node* pos) {  assert(pos);  if ((pos == 0) || (pos->_prev == NULL))  {   PopFront();  }  else if (pos->_next == NULL)  {   PopBack();  }  else  {   Node* font = pos->_prev;   Node* last = pos->_next;   font->_next = last;   last->_prev = font;   delete pos;  } } //逆序整個雙鏈表 void Reverse() {  Node* cur = _head;  while (cur)  {   swap(cur->_next,cur->_prev);   cur = cur->_prev;  }  swap(_head, _tail); } void Print() {  Node* cur = _head;  while (cur)  {   cout << cur->_data << "->";   cur = cur->_next;  }  cout << "NULL" << endl; }private: Node* _head; Node* _tail;};