-
我想你在看這之前已經(jīng)掌握了單向鏈表了千康，如果對單向鏈表不是很了解，可以看看這篇文章o(￣▽￣)ブ谷扣。
http://www.reibang.com/p/1b6309b6c9ab雙向鏈表也叫雙鏈表焙畔，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針玻熙，分別指向直接后繼和直接前驅(qū)否彩。所以，從雙向鏈表中的任意一個結(jié)點開始嗦随，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點列荔。
節(jié)點的編寫
struct node {
int val;//節(jié)點中存的值
node *prior;//前驅(qū)結(jié)點
node *next;
};
雙鏈表的創(chuàng)建
node *creat( ) {
node *head = nullptr, *tail;
int num;
while(cin >> num && num) {//以輸入0結(jié)束創(chuàng)建
node *pNode = new node;
pNode->val = num;
if(!head) {
head = pNode;
head->prior = nullptr;
head->next = nullptr;
tail = head;
continue;
}
pNode->prior = tail;
pNode->next = nullptr;
tail->next = pNode;
tail = pNode;
}
return head;
}
鏈表的輸出
void output(node *head) {
if(!head) return ;
for(node *pNode = head; pNode; pNode = pNode->next)
cout << pNode->val << " ";
cout << endl;
}
刪除 (刪除多個或一個）
void remove(node *head, const int num) {
if(!head) return ;
node *pNode = head;
while(pNode->next) {
bool flag = 0;//用于標(biāo)記是否刪除過，使可以刪除連續(xù)相同的兩個節(jié)點
if(pNode->next->val == num) {
flag = 1;//表示刪除過
node *dNode = pNode->next;
pNode->next = dNode->next;
if(dNode->next)//最后一個節(jié)點的next為nullptr,是沒有前驅(qū)的
dNode->next->prior = pNode;
delete dNode;
//如果刪除一個枚尼，就加break;
}
if(!flag && pNode->next)//刪除過就不需要更新pNode,因為在刪除前已經(jīng)更新過pNode了
pNode = pNode->next;
}
}
測試
#include <iostream>
#include <cstdio>
using namespace std;
struct node {
int val;
node *prior;//前驅(qū)結(jié)點
node *next;
};
int main() {
node *head = nullptr;
head = creat();
output(head);
int num;
cin >> num;
remove(head, num);
output(head);
return 0;
}
C++11編譯通過(/▽＼=)
Paste_Image.png
插入等基本操作與單鏈表相似贴浙，這里就不多說了，你懂的（http://www.reibang.com/p/1b6309b6c9ab）
代碼寫的很簡潔署恍，只為說明問題崎溃，有什么不好的地方，歡迎拍磚盯质！(●'?'●)
