http://www.cnblogs.com/jingliming/p/4602144.html#0-tsina-1-42616-397232819ff9a47a7b7e80a40613cfe1
一、雙向鏈表的定義
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。
注意：在實現的過程中，要分清前驅指針和后繼指針，不要把他們當成一個指針。
1 //雙向鏈表的實現 2 template<typename T>struct node{ 3 T data; 4 node<T> *prior,*next; 5 };
二、雙向鏈表的實現
1 template<typename T>class nLink 2 { 3 private: 4 node<T> *head; 5 public: 6 nLink() 7 { 8 head=new node<T>; 9 head->next=head->prior=NULL; 10 } 11 ~nLink() 12 { 13 14 } 15 //清空雙鏈表 16 void clearLink() 17 { 18 node<T> *p=head->next,*q=NULL; 19 while(p) 20 { 21 q=p->next; 22 delete p; 23 p=q; 24 } 25 head->next=NULL; 26 } 27 //銷毀雙鏈表 28 void destoryLink() 29 { 30 clearLink(); 31 if (head) 32 { 33 delete head; 34 head=NULL; 35 } 36 } 37 //打印雙鏈表 38 void printLink() 39 { 40 node<T> *p=head->next; 41 while(p) 42 { 43 44 cout<<p->data<<" "; 45 p=p->next; 46 } 47 cout<<endl; 48 } 49 //在雙鏈表末尾添加結點 50 bool appendLink(T e) 51 { 52 node<T> *p=head,*s=NULL; 53 s=new node<T>; 54 if (s==NULL) 55 return false; 56 s->data=e; 57 s->next=s->prior=NULL; 58 while(p->next) 59 { 60 p=p->next; 61 } 62 p->next=s; 63 s->prior=p; 64 return true; 65 } 66 //獲取鏈表的長度 67 int length() 68 { 69 node<T> *p=head; 70 int lenth=0; 71 if (p==NULL) 72 return 0; 73 while(p) 74 { 75 p=p->next; 76 lenth++; 77 } 78 return lenth; 79 } 80 //在第pos個位置插入新節點 81 bool insertLink(int pos,T e) 82 { 83 node<T> *p=head; 84 int posflag=0; 85 while(p&&posflag<pos-1) 86 { 87 p=p->next; 88 ++posflag; 89 } 90 node<T> *s=new node<T>; 91 if (s==NULL) 92 return false; 93 s->data=e; 94 s->next=s->prior=NULL; 95 if (p==NULL||posflag>pos-1) 96 { 97 return false; 98 } 99 s->next=p->next; 100 if(p->next!=NULL) 101 p->next->prior=s; 102 p->next=s; 103 s->prior=p; 104 return true; 105 } 106 107 //刪除第i個位置上的節點 108 bool deleteLink(int pos) 109 { 110 node<T> *p=head; 111 if (pos>length()||pos<1) 112 { 113 return false; 114 } 115 int posflag=0; 116 while(p && posflag<pos-1) 117 { 118 p=p->next; 119 ++posflag; 120 } 121 if (p && p->next==NULL) 122 { 123 p->prior->next=NULL; 124 delete p; 125 p=NULL; 126 } 127 else{ 128 p->prior->next=p->next; 129 p->next->prior=p->prior; 130 delete p; 131 p=NULL; 132 } 133 return true; 134 } 135 136 //刪除制定元素的節點 137 bool deleteLink(T e) 138 { 139 node<T> *p=head; 140 while (p) 141 { 142 if (p->data==e) 143 { 144 break; 145 } 146 p=p->next; 147 } 148 if(p==NULL) 149 { 150 cout<<"can not find the elem:"<<e<<endl; 151 return false; 152 } 153 //判斷要刪除的是不是尾節點 154 if (p->next==NULL) 155 { 156 p->prior->next=NULL; 157 delete p; 158 p=NULL; 159 } 160 else{ 161 p->prior->next=p->next; 162 p->prior=p->next->prior; 163 delete p; 164 p=NULL; 165 } 166 return true; 167 } 168 };
測試工作
1 int main() 2 { 3 nLink<char> link; 4 for (int i=0;i<10;i++) 5 { 6 link.appendLink('a'+i); 7 } 8 link.insertLink(11,'s'); 9 cout<<"Length:"<<link.length()<<endl; 10 link.printLink(); 11 link.deleteLink('s'); 12 link.printLink(); 13 cout<<"Length:"<<link.length()<<endl; 14 system("pause"); 15 return 0; 16 }
參考地址：http://www.oschina.net/code/snippet_250934_12063
