双链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域
　　线性表的双向链表存储结构：
　　[cpp] view plain copy print?
　　typedef struct Node 
　　{ 
　　DataType _data; 
　　struct Node *_next; 
　　struct Node *_front; 
　　}Node; 
　　通过双链表的存储结构我们发现双链表可以反向查找结点优于单链表 ，实质上双链表是以空间换取时间，虽然双链表具有可以反向查找数据的优点但是它也存在缺点：在插入和删除一个结点时需要维护两个指针变量，特别是在双链表的插入中指针的指向顺序是不可修改的。
　　双链表的插入过程：

　　双链表的删除过程：

　　C++实现双链表的基本功能：
　　[cpp] view plain copy print?
　　typedef int DataType; 
　　class LinkList; 
　　class Node 
　　{ 
　　friend LinkList; 
　　friend ostream &operator<<(ostream &os，Node &n); 
　　friend ostream& operator<<(ostream &os，LinkList &list); 
　　public: 
　　Node(DataType x) 
　　:_data(x) 
　　，_next(NULL) 
　　，_front(NULL) 
　　{} 
　　private: 
　　DataType _data; 
　　Node *_next; 
　　Node *_front; 
　　}; 
　　ostream &operator<<(ostream &os，Node &n) 
　　{ 
　　os<<n._data; 
　　return os; 
　　} 
　　class LinkList 
　　{ 
　　friend ostream& operator<<(ostream &os，LinkList &list); 
　　public: 
　　LinkList() 
　　:_head(NULL) 
　　，_tail(NULL) 
　　{} 
　　LinkList(const LinkList &list) 
　　:_head(NULL) 
　　，_tail(NULL) 
　　{ 
　　Node *cur=list._head; 
　　while(cur) 
　　{ 
　　Node *tmp=new Node(cur->_data); 
　　if(_tail) 
　　{ 
　　_tail->_next=tmp; 
　　tmp->_front=_tail; 
　　_tail=tmp; 
　　} 
　　else       //空链表 
　　{ 
　　_head=tmp; 
　　_tail=tmp; 
　　} 
　　cur=cur->_next; 
　　} 
　　} 
　　~LinkList() 
　　{ 
　　Node *cur=_head; 
　　while(cur) 
　　{ 
　　Node *del=cur; 
　　cur=cur->_next; 
　　delete del; 
　　del=NULL; 
　　} 
　　} 
　　public: 
　　void PushBack(DataType x) 
　　{ 
　　Node *NewNode=new Node(x); 
　　if(_tail) 
　　{ 
　　_tail->_next=NewNode; 
　　NewNode->_front=_tail; 
　　_tail=NewNode; 
　　} 
　　else 
　　{ 
　　_head=NewNode; 
　　_tail=NewNode; 
　　} 
　　} 
　　void PopBack() 
　　{ 
　　if(!_head && !_tail)    //空链表 
　　{ 
　　cout<<"链表已空不可尾删"<<endl; 
　　return ; 
　　} 
　　else if(_head == _tail)     //只有一个节点 
　　{ 
　　delete _tail; 
　　_head=NULL; 
　　_tail=NULL; 
　　} 
　　else      //至少存在两个节点 
　　{ 
　　Node *tmp=_tail; 
　　_tail=tmp->_front; 
　　_tail->_next=NULL; 
　　delete tmp; 
　　tmp=NULL; 
　　} 
　　} 
　　void PushFront(DataType x) 
　　{ 
　　Node *NewNode=new Node(x); 
　　if(_head) 
　　{ 
　　Node *tmp=_head; 
　　NewNode->_next=tmp; 
　　tmp->_front=NewNode; 
　　} 
　　else 
　　{ 
　　_tail=NewNode; 
　　} 
　　_head=NewNode;    //更新头 
　　} 
　　void PopFront() 
　　{ 
　　if(!_head && !_tail)     //空链表 
　　{ 
　　cout<<"链表已空不可头删"<<endl; 
　　return ; 
　　} 
　　else if(_head == _tail)    //只有一个节点 
　　{ 
　　delete _head; 
　　_head=NULL; 
　　_tail=NULL; 
　　} 
　　else        //至少存在两个节点 
　　{ 
　　Node *del=_head; 
　　_head=del->_next; 
　　_head->_front=NULL; 
　　delete del; 
　　del=NULL; 
　　} 
　　} 
　　Node *FindNum(DataType x) 
　　{ 
　　Node *cur=_head; 
　　while(cur) 
　　{ 
　　if(cur->_data == x) 
　　return cur; 
　　cur=cur->_next; 
　　} 
　　return NULL; 
　　} 
　　void Insert(Node *pos，DataType x)    //在指定位置后插 
　　{ 
　　Node *NewNode=new Node(x); 
　　if(pos->_next) 
　　{ 
　　NewNode->_front=pos; 
　　NewNode->_next=pos->_next; 
　　pos->_next->_front=NewNode; 
　　pos->_next=NewNode; 
　　} 
　　else    //在后一个结点后插，类似PushBack 
　　{ 
　　pos->_next=NewNode; 
　　NewNode->_front=pos; 
　　_tail=NewNode;    //更新尾 
　　} 
　　} 
　　void Insert(int，Node *pos，DataType x)   //在指定位置前插 
　　{ 
　　Node *NewNode=new Node(x); 
　　if(pos->_front) 
　　{ 
　　NewNode->_next=pos; 
　　pos->_front->_next=NewNode; 
　　NewNode->_front=pos->_front; 
　　pos->_front=NewNode; 
　　} 
　　else   //在第一个结点的前插，类似PushFront 
　　{ 
　　NewNode->_next=pos; 
　　pos->_front=NewNode; 
　　_head=NewNode;    //更新头 
　　} 
　　} 
　　void Remove(DataType &x) 
　　{ 
　　Node *pos=this->FindNum(x); 
　　if(pos != NULL) 
　　{ 
　　if((!(pos->_front)) && pos->_next)    //删除第一个结点 
　　{ 
　　Node *tmp=pos->_next; 
　　tmp->_front=NULL; 
　　_head=tmp; 
　　} 
　　else if(pos->_front && (!(pos->_next)))   //删除后一个结点 
　　{ 
　　Node *tmp=pos->_front; 
　　tmp->_next=NULL; 
　　_tail=tmp; 
　　} 
　　else             //删除中间节点 
　　{ 
　　Node *front=pos->_front; 
　　Node *next=pos->_next; 
　　next->_front=front; 
　　front->_next=next; 
　　} 
　　delete pos; 
　　pos=NULL; 
　　} 
　　} 
　　void RemoveAll(DataType &x) 
　　{ 
　　Node *cur=_head; 
　　Node *ret=this->FindNum(x); 
　　if(ret != _head)    //可删除第一个结点不是要删除的元素 
　　{ 
　　while(cur) 
　　{ 
　　Remove(x); 
　　cur=cur->_next; 
　　} 
　　} 
　　} 
　　void Sort() 
　　{ 
　　int flag=1; 
　　Node *cur=_head; 
　　Node *tail=NULL; 
　　while(cur != tail) 
　　{ 
　　while(cur->_next != tail) 
　　{ 
　　if(cur->_data > cur->_next->_data) 
　　{ 
　　DataType tmp=cur->_data; 
　　cur->_data=cur->_next->_data; 
　　cur->_next->_data=tmp; 
　　flag=0; 
　　} 
　　cur=cur->_next; 
　　} 
　　if(flag == 1) 
　　break; 
　　tail=cur; 
　　cur=_head; 
　　} 
　　} 
　　void Erase(Node *pos) 
　　{ 
　　if((!(pos->_front)) && pos->_next)    //删除第一个结点 
　　{ 
　　Node *tmp=pos->_next; 
　　tmp->_front=NULL; 
　　_head=tmp; 
　　} 
　　else if(pos->_front && (!(pos->_next)))   //删除后一个结点 
　　{ 
　　Node *tmp=pos->_front; 
　　tmp->_next=NULL; 
　　_tail=tmp; 
　　} 
　　else             //删除中间节点 
　　{ 
　　Node *front=pos->_front; 
　　Node *next=pos->_next; 
　　next->_front=front; 
　　front->_next=next; 
　　} 
　　delete pos; 
　　pos=NULL; 
　　} 
　　private: 
　　Node *_head; 
　　Node *_tail; 
　　}; 
　　ostream& operator<<(ostream &os，LinkList &list) 
　　{ 
　　Node *cur=list._head; 
　　while(cur) 
　　{ 
　　os<<(*cur)<<" "; 
　　cur=cur->_next; 
　　} 
　　return os; 
　　}