双向链表也叫，是链表的一种，它的每个数据结点中都有两个，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向。

由于双向链表可以方便地实现正序和逆序两个方向的插入、查找等功能，在很多算法中经常被使用，

这里用C＋＋构造了一个双向链表，提供了对双向链表的插入、查找、删除节点、排序等功能，其中排序提供了插入排序和冒泡排序两种方式

1 #include
     
        2   3 using namespace std;  4   5 class Node          //组成双向链表的节点  6 {  7 public:  8     int data;  9     Node * pNext; 10     Node * pLast; 11 }; 12  13 class List      //构造一个双向链表 14 { 15 private: 16     Node * pHead; 17     Node * pTail; 18     int length; 19 public: 20     List(int length)　　　　//创建双向链表 21     { 22         this->length=length; 23         pHead=new Node(); 24         pHead->pLast=NULL; 25         pTail=pHead; 26         for(int i=0;i
      
       >temp->data; 31             temp->pNext=NULL; 32             temp->pLast=pTail; 33             pTail->pNext=temp; 34             pTail=temp; 35         } 36     } 37      38     void traverseList()　　　　//正向遍历 39     { 40         Node * p=pHead->pNext; 41         while(p!=NULL) 42         { 43             cout<
       
        data<
        
         pNext; 45         } 46     } 47      48     void traverseListReturn()　　　　//逆向遍历 49     { 50         Node * p=pTail; 51         while(p->pLast!=NULL) 52         { 53             cout<
         
          data<
          
           pLast; 55 } 56 } 57 58 void sortList() //冒泡排序 59 { 60 Node * p=new Node(); 61 Node * q=new Node(); 62 int temp; 63 for(p=pHead->pNext;p->pNext!=NULL;p=p->pNext) 64 { 65 for(q=p->pNext;q!=NULL;q=q->pNext) 66 { 67 if(q->data
           
            data) 68 { 69 temp=q->data; 70 q->data=p->data; 71 p->data=temp; 72 } 73 } 74 } 75 } 76 77 void sortListByInsertWay() //插入排序 78 { 79 if(pHead->pNext==NULL||pHead->pNext->pNext==NULL) 80 { 81 return; 82 } 83 Node * p2=pHead->pNext->pNext; 84 Node * p1=pHead; 85 pHead->pNext->pNext=NULL; 86 while(p2) 87 { 88 Node * pN=p2->pNext; 89 while(p1->pNext) 90 { 91 if(p2->data
            
             pNext->data) 92 { 93 p2->pNext=p1->pNext; 94 p2->pLast=p1; 95 p1->pNext->pLast=p2; 96 p1->pNext=p2; 97 break; 98 } 99 p1=p1->pNext;100 }101 if(p1->pNext==NULL)102 {103 p2->pNext=NULL;104 p2->pLast=p1;105 p1->pNext=p2;106 }107 p2=pN;108 }109 110 //重新查找pTail的位置111 Node * pt=pHead;112 while(pt->pNext)113 {114 pt=pt->pNext;115 }116 pTail=pt;117 }118 119 void changeList(int num,int position)　　　　//修改链表中指定位置的节点120 {121 Node * p=pHead->pNext;122 if(position>length||position<=0)123 {124 cout<<"over stack !"<
             
              pNext;130 }131 p->data=num;132 }133 134 void insertList(int num,int position)　　　　//插入数据135 {136 Node * p=pHead->pNext;137 if(position>length||position<=0)138 {139 cout<<"over stack !"<
              
               pNext;145 }146 Node * temp=new Node();147 temp->data=num;148 temp->pNext=p;149 temp->pLast=p->pLast;150 p->pLast->pNext=temp;151 p->pLast=temp;152 length++;153 }154 155 void clearList()　　　　　　//清空156 {157 Node * q;158 Node * p=pHead->pNext;159 while(p!=NULL)160 {161 q=p;162 p=p->pNext;163 delete q;164 }165 p=NULL;166 q=NULL;167 }168 169 void deleteList(int position)　　　//删除指定位置的节点170 {171 Node * p=pHead->pNext;172 if(position>length||position<=0)173 {174 cout<<"over stack !"<
               
                pNext;180 }181 p->pLast->pNext=p->pNext;182 p->pNext->pLast=p->pLast;183 delete p;184 length--;185 }186 187 int getItemInList(int position)　　　　　　//查找指定位置的节点188 {189 Node * p=pHead->pNext;190 if(position>length||position<=0)191 {192 cout<<"over stack !"<
                
                 pNext;198 }199 return p->data;200 }201 202 ~List()203 {204 Node * q;205 Node * p=pHead->pNext;206 while(p!=NULL)207 {208 q=p;209 p=p->pNext;210 delete q;211 }212 p=NULL;213 q=NULL;214 }215 216 };217 218 int main()219 {220 List l(3);221 l.traverseList();222 cout<<"AFTER SORT------------------------------------------------------"<