雙向鏈表
定義
我們一開始學(xué)習(xí)的鏈表中各節(jié)點(diǎn)中都只包含一個(gè)指針（游標(biāo)），且都統(tǒng)一指向直接后繼節(jié)點(diǎn)惠毁，通常稱這類鏈表為單向鏈表郑临。
雖然使用單向鏈表能 100% 解決邏輯關(guān)系為 "一對(duì)一" 數(shù)據(jù)的存儲(chǔ)問題，但在解決某些特殊問題時(shí)惋砂，單鏈表并不是效率最優(yōu)的存儲(chǔ)結(jié)構(gòu)妒挎。比如說，如果算法中需要大量地找某指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)西饵，使用單鏈表無疑是災(zāi)難性的酝掩，因?yàn)閱捂湵砀m合 "從前往后" 找，而 "從后往前" 找并不是它的強(qiáng)項(xiàng)眷柔。
為了能夠高效率解決類似的問題期虾，就發(fā)明了雙向鏈表原朝。從名字上理解雙向鏈表，即鏈表是 "雙向" 的镶苞，如下圖所示：
從上圖中可以看到喳坠，雙向鏈表中各節(jié)點(diǎn)包含以下 3 部分信息（如下圖所示）：
- 指針域 prior：用于指向當(dāng)前節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)；
- 數(shù)據(jù)域 data：用于存儲(chǔ)數(shù)據(jù)元素宾尚。
- 指針域 next：用于指向當(dāng)前節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)丙笋；
因此，雙鏈表的節(jié)點(diǎn)結(jié)構(gòu)用 C 語言實(shí)現(xiàn)為：
typedef struct Node {
struct Node *prior;//指向直接前驅(qū)節(jié)點(diǎn)
ElemType data;//數(shù)據(jù)域
struct Node *next;//指向直接后繼節(jié)點(diǎn)
} Node;
注意：因?yàn)閹ь^節(jié)點(diǎn)會(huì)更好操作煌贴，所以我的代碼都有頭節(jié)點(diǎn)御板。
1、雙向鏈表的創(chuàng)建
同單鏈表相比牛郑，雙鏈表僅是各節(jié)點(diǎn)多了一個(gè)用于指向直接前驅(qū)的指針域怠肋。因此，我們可以在單鏈表的基礎(chǔ)輕松實(shí)現(xiàn)對(duì)雙鏈表的創(chuàng)建淹朋。
//1笙各、初始化雙向鏈表（帶頭節(jié)點(diǎn)）
Status initLinkList(LinkList *list){
//創(chuàng)建頭節(jié)點(diǎn)
*list = malloc(sizeof(Node));
if (*list == NULL) {
return ERROR;
}
(*list)->prior = NULL;
(*list)->data = -1;
(*list)->next = NULL;
printf("已初始化鏈表~\n");
return OK;
}
2、遍歷雙向鏈表
和單向鏈表遍歷方式一模模一樣樣础芍，這里就不多講杈抢。我多加了一層使用prior指針逆序輸出，相信有點(diǎn)基礎(chǔ)的同學(xué)應(yīng)該能一眼看明白仑性。
//2惶楼、遍歷雙向鏈表
void printfLinkLisk(LinkList list){
printf("遍歷鏈表：\n");
if (list == NULL || list->next == NULL) {
printf("這是一個(gè)空鏈表\n");
return;
}
LinkList p = list;
//判斷next是否全部正確
printf("根據(jù)next從前往后遍歷：");
while (p->next) {
printf("%d ",p->next->data);
p = p->next;
}
printf("\n");
//判斷prior是否全部正確
printf("根據(jù)prior從后往前遍歷：");
while (p != list) {
printf("%d ",p->data);
p = p->prior;
}
printf("\n");
}
3、根據(jù)索引位置添加節(jié)點(diǎn)
因?yàn)槲业碾p向鏈表有頭節(jié)點(diǎn)诊杆，所以只有兩種添加情況：
- 添加至表的中間位置
同單鏈表添加數(shù)據(jù)類似歼捐，雙向鏈表中間位置添加數(shù)據(jù)需要經(jīng)過以下 4 個(gè)步驟(步驟中的順序中 3 必須放到 1 和 2 后面，其它順序可變)晨汹，如下圖所示：
- 將priorNode->next節(jié)點(diǎn)的prior指向新節(jié)點(diǎn)豹储；
- 將新節(jié)點(diǎn)->next指向原來的priorNode->next；
- 將priorNode->next指向新節(jié)點(diǎn)淘这；
-
新節(jié)點(diǎn)的prior指向priorNode剥扣。
插入結(jié)點(diǎn).png
- 添加至表尾
與添加到表中間的步驟只需要少掉步驟 1。因?yàn)閜riorNode->next是Null铝穷，不能用它執(zhí)行操作朦乏，否則會(huì)崩潰。
//3氧骤、根據(jù)索引位置插入數(shù)據(jù)至鏈表中
Status insertLinkList(LinkList *list, int index, ElemType data){
if (list == NULL || index < 0) {
return ERROR;
}
int i = 0;
LinkList priorNode = *list;
//判斷插入的位置，這里開始位置是0吃引，index超過鏈表長(zhǎng)度則插入末尾
while (i < index && priorNode->next != NULL) {
priorNode = priorNode->next;
I++;
}
LinkList newNode = malloc(sizeof(Node));
if (newNode == NULL) {
return ERROR;
}
newNode->data = data;
//插入操作共四步筹陵，看好了刽锤，別眨眼
//1.將priorNode->next節(jié)點(diǎn)的前驅(qū)指向新節(jié)點(diǎn)
if (priorNode->next) {
priorNode->next->prior = newNode;
}
//2.將新節(jié)點(diǎn)->next指向原來的priorNode->next
newNode->next = priorNode->next;
//3.將priorNode->next指向新節(jié)點(diǎn)
priorNode->next = newNode;
//4.新節(jié)點(diǎn)的前驅(qū)指向priorNode
newNode->prior = priorNode;
return OK;
}
4、根據(jù)索引位置刪除節(jié)點(diǎn)
根據(jù)索引刪除節(jié)點(diǎn)時(shí)朦佩，只需遍歷鏈表找到要?jiǎng)h除的結(jié)點(diǎn)并思，更改前驅(qū)節(jié)點(diǎn)的next和后繼節(jié)點(diǎn)的prior即可。
//4语稠、根據(jù)索引位置刪除節(jié)點(diǎn)
Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){
if (*list == NULL || index < 0) {
return ERROR;
}
LinkList locaNode = *list;
int i = 0;
while (i <= index) {
locaNode = locaNode->next;
if (locaNode == NULL) {
printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
return ERROR;
}
I++;
}
//開始刪除宋彼，只需要做兩步
//1、更改前驅(qū)節(jié)點(diǎn)的next
locaNode->prior->next = locaNode->next;
//2仙畦、更改后繼節(jié)點(diǎn)的prior输涕。
if (locaNode->next) {
locaNode->next->prior = locaNode->prior;
}
*data = locaNode->data;
free(locaNode);
return OK;
}
5、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
根據(jù)值刪除節(jié)點(diǎn)時(shí)慨畸，只需遍歷鏈表找到要?jiǎng)h除的結(jié)點(diǎn)莱坎，更改前驅(qū)節(jié)點(diǎn)的next和后繼節(jié)點(diǎn)的prior即可。
//5寸士、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
Status deleteLinkListByData(LinkList *list, ElemType data){
if (*list == NULL) {
return ERROR;
}
LinkList locaNode = (*list)->next;
while (locaNode) {
if (locaNode->data == data) {
break;
}
locaNode = locaNode->next;
}
if (locaNode == NULL) {
printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
return ERROR;
}
//開始刪除檐什，只需要做兩步
locaNode->prior->next = locaNode->next;
if (locaNode->next) {
locaNode->next->prior = locaNode->prior;
}
free(locaNode);
return OK;
}
6、根據(jù)值查找節(jié)點(diǎn)
方法同單向鏈表
//6弱卡、查找元素
Status selectNode(LinkList list, ElemType data, LinkList *locaNode){
if (list == NULL) {
return ERROR;
}
LinkList p = list->next;
while (p) {
if (p->data == data) {
*locaNode = p;
break;
}
p = p->next;
}
if (*locaNode == NULL) {
printf("沒有這個(gè)你想要的節(jié)點(diǎn)\n");
return ERROR;
}
else {
return OK;
}
}
其它輔助代碼
#include "stdlib.h"
#define OK 1
#define ERROR 0
//元素類型
typedef int ElemType;
//狀態(tài)類型
typedef int Status;
//定義節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node {
struct Node *prior;
ElemType data;
struct Node *next;
} Node;
typedef Node *LinkList;
int main(int argc, const char * argv[]) {
LinkList list;
initLinkList(&list);
for (int i = 0; i < 10; i ++) {
insertLinkList(&list, i, i);
}
printfLinkLisk(list);
int index, data;
printf("輸入你想插入的位置（從0開始）和存儲(chǔ)的值:");
scanf("%d %d",&index,&data);
insertLinkList(&list, index, data);
printfLinkLisk(list);
printf("輸入你想刪除的位置（從0開始）:");
scanf("%d",&index);
deleteLinkListByIndex(&list, index, &data);
printfLinkLisk(list);
printf("輸入你想刪除的節(jié)點(diǎn)的值（只刪最前的那個(gè)）:");
scanf("%d",&data);
deleteLinkListByData(&list, data);
printfLinkLisk(list);
printf("\n");
return 0;
}
輸出結(jié)果：
雙向循環(huán)鏈表
定義
雙向循環(huán)鏈表和它名字的表意一樣乃正，就是把雙向鏈表的兩頭連接，使其成為了一個(gè)環(huán)狀鏈表婶博。只需要將表中最后一個(gè)節(jié)點(diǎn)的next指針指向頭節(jié)點(diǎn)瓮具，頭節(jié)點(diǎn)的prior指針指向尾節(jié)點(diǎn)，鏈表就能成環(huán)兒凡蜻，如圖所示：
需要注意的是搭综，雖然雙向循環(huán)鏈表成環(huán)狀，但本質(zhì)上還是雙向鏈表划栓，因此在雙向循環(huán)鏈表中兑巾，依然能夠找到頭指針和頭節(jié)點(diǎn)等。雙向循環(huán)鏈表和雙向鏈表相比忠荞，唯一的不同就是雙向循環(huán)鏈表首尾相連蒋歌，其他都完全一樣。
注意：因?yàn)槲疑厦嬉呀?jīng)講了雙向鏈表委煤，所以這里只注重講他們的實(shí)現(xiàn)差異堂油。另因?yàn)閹ь^節(jié)點(diǎn)會(huì)更好操作，所以我的代碼都有頭節(jié)點(diǎn)碧绞。
1府框、雙向循環(huán)鏈表的創(chuàng)建
初始化時(shí)需要將頭節(jié)點(diǎn)的next和prior都指向自己。
//1讥邻、初始化雙向循環(huán)鏈表（帶頭節(jié)點(diǎn)）
Status initLinkList(LinkList *list){
//創(chuàng)建頭節(jié)點(diǎn)
*list = malloc(sizeof(Node));
if (*list == NULL) {
return ERROR;
}
//前驅(qū)和后繼都指向自己
(*list)->prior = *list;
(*list)->data = -1;
(*list)->next = *list;
printf("已初始化鏈表~\n");
return OK;
}
2迫靖、遍歷雙向循環(huán)鏈表
注意它的尾節(jié)點(diǎn)的next不再是Null院峡，而是頭節(jié)點(diǎn)
//2、遍歷雙向循環(huán)鏈表
void printfLinkLisk(LinkList list){
printf("遍歷鏈表：\n");
if (list == NULL || list->next == list) {
printf("這是一個(gè)空鏈表\n");
return;
}
LinkList p = list;
//判斷next是否全部正確
printf("根據(jù)next從前往后遍歷：");
while (p->next != list) {
printf("%d ",p->next->data);
p = p->next;
}
printf("\n");
//判斷prior是否全部正確
printf("根據(jù)prior從后往前遍歷：");
while (p != list) {
printf("%d ",p->data);
p = p->prior;
}
printf("\n");
}
3系宜、根據(jù)索引位置添加節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null照激，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)。
//3盹牧、根據(jù)索引位置插入數(shù)據(jù)至鏈表中
Status insertLinkList(LinkList *list, int index, ElemType data){
if (list == NULL || index < 0) {
return ERROR;
}
int i = 0;
LinkList priorNode = *list;
//判斷插入的位置俩垃，這里開始位置是0，index超過鏈表長(zhǎng)度則插入末尾
while (i < index && priorNode->next != *list) {
priorNode = priorNode->next;
I++;
}
LinkList newNode = malloc(sizeof(Node));
if (newNode == NULL) {
return ERROR;
}
newNode->data = data;
//插入操作共四步汰寓，看好了口柳，別眨眼
//1.將priorNode->next節(jié)點(diǎn)的前驅(qū)指向新節(jié)點(diǎn)
priorNode->next->prior = newNode;
//2.將新節(jié)點(diǎn)->next指向原來的priorNode->next
newNode->next = priorNode->next;
//3.將priorNode->next指向新節(jié)點(diǎn)
priorNode->next = newNode;
//4.新節(jié)點(diǎn)的前驅(qū)指向priorNode
newNode->prior = priorNode;
return OK;
}
4、根據(jù)索引位置刪除節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null踩寇，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)啄清。
//4、根據(jù)索引位置刪除節(jié)點(diǎn)
Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){
if (*list == NULL || index < 0) {
return ERROR;
}
LinkList locaNode = *list;
int i = 0;
//注意別刪了頭節(jié)點(diǎn)
while (i <= index) {
locaNode = locaNode->next;
if (locaNode == *list) {
printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
return ERROR;
}
I++;
}
//開始刪除俺孙，只需要做兩步
locaNode->prior->next = locaNode->next;
locaNode->next->prior = locaNode->prior;
*data = locaNode->data;
free(locaNode);
return OK;
}
5辣卒、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
這里不需要判斷尾節(jié)點(diǎn)的next是否為Null，因?yàn)樗鼤?huì)指向頭節(jié)點(diǎn)睛榄。
//5荣茫、根據(jù)存儲(chǔ)的值刪除節(jié)點(diǎn)
Status deleteLinkListByData(LinkList *list, ElemType data){
if (*list == NULL) {
return ERROR;
}
LinkList locaNode = (*list)->next;
while (locaNode != *list) {
if (locaNode->data == data) {
break;
}
locaNode = locaNode->next;
}
if (locaNode == *list) {
printf("沒有這個(gè)你想要?jiǎng)h除的節(jié)點(diǎn)\n");
return ERROR;
}
//開始刪除，只需要做兩步
locaNode->prior->next = locaNode->next;
locaNode->next->prior = locaNode->prior;
free(locaNode);
return OK;
}
6场靴、根據(jù)值查找節(jié)點(diǎn)
尾節(jié)點(diǎn)的next可是頭節(jié)點(diǎn)哦啡莉，找到它就是最后一個(gè)了。
//6旨剥、查找元素
Status selectNode(LinkList list, ElemType data, LinkList *locaNode){
if (list == NULL) {
return ERROR;
}
LinkList p = list->next;
while (p != list) {
if (p->data == data) {
*locaNode = p;
break;
}
p = p->next;
}
if (*locaNode == NULL) {
printf("沒有這個(gè)你想要的節(jié)點(diǎn)\n");
return ERROR;
}
else {
return OK;
}
}
其它輔助代碼
#include "stdlib.h"
#define OK 1
#define ERROR 0
//元素類型
typedef int ElemType;
//狀態(tài)類型
typedef int Status;
//定義節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node {
struct Node *prior;
ElemType data;
struct Node *next;
} Node;
typedef Node *LinkList;
int main(int argc, const char * argv[]) {
LinkList list;
initLinkList(&list);
for (int i = 0; i < 10; i ++) {
insertLinkList(&list, i, i);
}
printfLinkLisk(list);
int index, data;
printf("輸入你想插入的位置（從0開始）和存儲(chǔ)的值:");
scanf("%d %d",&index,&data);
insertLinkList(&list, index, data);
printfLinkLisk(list);
printf("輸入你想刪除的位置（從0開始）:");
scanf("%d",&index);
deleteLinkListByIndex(&list, index, &data);
printfLinkLisk(list);
printf("輸入你想刪除的節(jié)點(diǎn)的值（只刪最前的那個(gè)）:");
scanf("%d",&data);
deleteLinkListByData(&list, data);
printfLinkLisk(list);
printf("\n");
return 0;
}
輸出結(jié)果
如有不對(duì)的地方咧欣，請(qǐng)指正，謝謝您的閱讀～
