@[TOC]
1.雙向鏈表的定義
上一節(jié)學(xué)習(xí)了單向鏈表單鏈表詳解。今天學(xué)習(xí)雙鏈表。學(xué)習(xí)之前先對(duì)單向鏈表和雙向鏈表做個(gè)回顧。
單向鏈表特點(diǎn)：
??1.我們可以輕松的到達(dá)下一個(gè)節(jié)點(diǎn), 但是回到前一個(gè)節(jié)點(diǎn)是很難的.
??2.只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)
雙向鏈表特點(diǎn)
??1.每次在插入或刪除某個(gè)節(jié)點(diǎn)時(shí), 需要處理四個(gè)節(jié)點(diǎn)的引用, 而不是兩個(gè). 實(shí)現(xiàn)起來(lái)要困難一些
??2.相對(duì)于單向鏈表, 必然占用內(nèi)存空間更大一些.
??3.既可以從頭遍歷到尾, 又可以從尾遍歷到頭
雙向鏈表的定義:
??雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。下圖為雙向鏈表的結(jié)構(gòu)圖。
??從上中可以看到，雙向鏈表中各節(jié)點(diǎn)包含以下 3 部分信息：
??指針域：用于指向當(dāng)前節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)；
??數(shù)據(jù)域：用于存儲(chǔ)數(shù)據(jù)元素。
??指針域：用于指向當(dāng)前節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)；
雙向循環(huán)鏈表的定義:
??雙向鏈表也可以進(jìn)行首尾連接，構(gòu)成雙向循環(huán)鏈表,如下圖所示
在創(chuàng)建鏈表時(shí)，只需要在最后將收尾相連即可（創(chuàng)建鏈表代碼中已經(jīng)標(biāo)出）。其他代碼稍加改動(dòng)即可。
雙鏈表的節(jié)點(diǎn)結(jié)構(gòu)用 C 語(yǔ)言實(shí)現(xiàn)為：
/*隨機(jī)數(shù)的范圍*/
#define MAX 100
/*節(jié)點(diǎn)結(jié)構(gòu)*/
typedef struct Node{
struct Node *pre;
int data;
struct Node *next;
}Node;
2.雙向鏈表的創(chuàng)建
??同單鏈表相比，雙鏈表僅是各節(jié)點(diǎn)多了一個(gè)用于指向直接前驅(qū)的指針域。因此，我們可以在單鏈表的基礎(chǔ)輕松實(shí)現(xiàn)對(duì)雙鏈表的創(chuàng)建。
??需要注意的是，與單鏈表不同，雙鏈表創(chuàng)建過(guò)程中，每創(chuàng)建一個(gè)新節(jié)點(diǎn)，都要與其前驅(qū)節(jié)點(diǎn)建立兩次聯(lián)系，分別是：
??將新節(jié)點(diǎn)的 prior 指針指向直接前驅(qū)節(jié)點(diǎn)；
??將直接前驅(qū)節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn)；
??這里給出創(chuàng)建雙向鏈表的 C 語(yǔ)言實(shí)現(xiàn)代碼：
Node* CreatList(Node * head,int length)
{
if (length == 1)
{
return( head = CreatNode(head));
}
else
{
head = CreatNode(head);
Node * list=head;
for (int i=1; i<length; i++)
/*創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)*/
{
Node * body=(Node*)malloc(sizeof(Node));
body->pre=NULL;
body->next=NULL;
body->data=rand()%MAX;
/*直接前趨結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)*/
list->next=body;
/*新結(jié)點(diǎn)指向直接前趨結(jié)點(diǎn)*/
body->pre=list;
/*把body指針給list返回*/
list=list->next;
}
}
/*加上以下兩句就是雙向循環(huán)鏈表*/
// list->next=head;
// head->prior=list;
return head;
}
3.雙向鏈表的插入
??根據(jù)數(shù)據(jù)添加到雙向鏈表中的位置不同，可細(xì)分為以下 3 種情況：
1.添加至表頭
??將新數(shù)據(jù)元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關(guān)系即可。
??換句話說(shuō)，假設(shè)新元素節(jié)點(diǎn)為 temp，表頭節(jié)點(diǎn)為 head，則需要做以下 2 步操作即可：
??temp->next=head; head->prior=temp;
??將 head 移至 temp，重新指向新的表頭；
??將新元素 7 添加至雙鏈表的表頭，則實(shí)現(xiàn)過(guò)程如下圖所示：
2.添加至表的中間位置
??同單鏈表添加數(shù)據(jù)類似，雙向鏈表中間位置添加數(shù)據(jù)需要經(jīng)過(guò)以下 2 個(gè)步驟，如下圖所示：
??新節(jié)點(diǎn)先與其直接后繼節(jié)點(diǎn)建立雙層邏輯關(guān)系；
??新節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)與之建立雙層邏輯關(guān)系；
3.添加至表尾
??與添加到表頭是一個(gè)道理，實(shí)現(xiàn)過(guò)程如下：
??找到雙鏈表中最后一個(gè)節(jié)點(diǎn)；
??讓新節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)進(jìn)行雙層邏輯關(guān)系；
/*在第add位置的前面插入data節(jié)點(diǎn)*/
Node * InsertListHead(Node * head,int add,int data)
{
/*新建數(shù)據(jù)域?yàn)閐ata的結(jié)點(diǎn)*/
Node * temp=(Node*)malloc(sizeof(Node));
if(head == NULL)
{
printf("malloc error!\r\n");
return NULL;
}
else
{
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
}
/*插入到鏈表頭，要特殊考慮*/
if (add==1)
{
temp->next=head;
head->pre=temp;
head=temp;
}
else
{
Node * body=head;
/*找到要插入位置的前一個(gè)結(jié)點(diǎn)*/
for (int i=1; i<add-1; i++)
{
body=body->next;
}
/*判斷條件為真，說(shuō)明插入位置為鏈表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
}
else
{
body->next->pre=temp;
temp->next=body->next;
body->next=temp;
temp->pre=body;
}
}
return head;
}
```c
/*在第add位置的后面插入data節(jié)點(diǎn)*/
Node * InsertListEnd(Node * head,int add,int data)
{
int i = 1;
/*新建數(shù)據(jù)域?yàn)閐ata的結(jié)點(diǎn)*/
Node * temp=(Node*)malloc(sizeof(Node));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
Node * body=head;
while ((body->next)&&(i<add+1))
{
body=body->next;
i++;
}
/*判斷條件為真，說(shuō)明插入位置為鏈表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
temp->next=NULL;
}
else
{
temp->next=body->pre->next;
temp->pre=body->pre;
temp->pre=body->pre;
body->pre->next=temp;
}
return head;
}
4.雙向鏈表的刪除
??雙鏈表刪除結(jié)點(diǎn)時(shí)，只需遍歷鏈表找到要?jiǎng)h除的結(jié)點(diǎn)，然后將該節(jié)點(diǎn)從表中摘除即可。
??例如，刪除元素 2 的操作過(guò)程如圖 所示：
Node * DeleteList(Node * head,int data)
{
Node * temp=head;
/*遍歷鏈表*/
while (temp)
{
/*判斷當(dāng)前結(jié)點(diǎn)中數(shù)據(jù)域和data是否相等，若相等，摘除該結(jié)點(diǎn)*/
if (temp->data==data)
{
/*判斷是否是頭結(jié)點(diǎn)*/
if(temp->pre == NULL)
{
head=temp->next;
temp->next = NULL;
free(temp);
return head;
}
/*判斷是否是尾節(jié)點(diǎn)*/
else if(temp->next == NULL)
{
temp->pre->next=NULL;
free(temp);
return head;
}
else
{
temp->pre->next=temp->next;
temp->next->pre=temp->pre;
free(temp);
return head;
}
}
temp=temp->next;
}
printf("Can not find %d!\r\n",data);
return head;
}
5.雙向鏈表更改節(jié)點(diǎn)數(shù)據(jù)
??更改雙鏈表中指定結(jié)點(diǎn)數(shù)據(jù)域的操作是在查找的基礎(chǔ)上完成的。實(shí)現(xiàn)過(guò)程是：通過(guò)遍歷找到存儲(chǔ)有該數(shù)據(jù)元素的結(jié)點(diǎn)，直接更改其數(shù)據(jù)域即可。
/*更新函數(shù)，其中，add 表示更改結(jié)點(diǎn)在雙鏈表中的位置，newElem 為新數(shù)據(jù)的值*/
Node *ModifyList(Node * p,int add,int newElem)
{
Node * temp=p;
/*遍歷到被刪除結(jié)點(diǎn)*/
for (int i=1; i<add; i++)
{
temp=temp->next;
}
temp->data=newElem;
return p;
}
6.雙向鏈表的查找
??通常，雙向鏈表同單鏈表一樣，都僅有一個(gè)頭指針。因此，雙鏈表查找指定元素的實(shí)現(xiàn)同單鏈表類似，都是從表頭依次遍歷表中元素。
/*head為原雙鏈表，elem表示被查找元素*/
int FindList(Node * head,int elem)
{
/*新建一個(gè)指針t，初始化為頭指針 head*/
Node * temp=head;
int i=1;
while (temp)
{
if (temp->data==elem)
{
return i;
}
i++;
temp=temp->next;
}
/*程序執(zhí)行至此處，表示查找失敗*/
return -1;
}
7.雙向鏈表的打印
/*輸出鏈表的功能函數(shù)*/
void PrintList(Node * head)
{
Node * temp=head;
while (temp)
{
/*如果該節(jié)點(diǎn)無(wú)后繼節(jié)點(diǎn)，說(shuō)明此節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)*/
if (temp->next==NULL)
{
printf("%d\n",temp->data);
}
else
{
printf("%d->",temp->data);
}
temp=temp->next;
}
}
8.測(cè)試函數(shù)及結(jié)果
int main()
{
Node * head=NULL;
//創(chuàng)建雙鏈表
head=CreatList(head,5);
printf("新創(chuàng)建雙鏈表為\t");
PrintList(head);
//在表中第 5 的位置插入元素 1
head=InsertListHead(head, 5,1);
printf("在表中第 5 的位置插入元素 1\t");
PrintList(head);
//在表中第 3 的位置插入元素 7
head=InsertListEnd(head, 3, 7);
printf("在表中第 3 的位置插入元素 7\t");
PrintList(head);
// //表中刪除元素 7
head=DeleteList(head, 7);
printf("表中刪除元素 7\t\t\t");
PrintList(head);
printf("元素 1 的位置是\t：%d\n",FindList(head,1));
//表中第 3 個(gè)節(jié)點(diǎn)中的數(shù)據(jù)改為存儲(chǔ) 6
head = ModifyList(head,3,6);
printf("表中第 3 個(gè)節(jié)點(diǎn)中的數(shù)據(jù)改為存儲(chǔ)6\t");
PrintList(head);
return 0;
}
??大家的鼓勵(lì)是我繼續(xù)創(chuàng)作的動(dòng)力，如果覺(jué)得寫的不錯(cuò)，歡迎關(guān)注，點(diǎn)贊，收藏，轉(zhuǎn)發(fā)，謝謝！
以上代碼均為測(cè)試后的代碼。如有錯(cuò)誤和不妥的地方，歡迎指出。
部分內(nèi)容參考網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系刪除。
如遇到排版錯(cuò)亂的問(wèn)題，可以通過(guò)以下鏈接訪問(wèn)我的CSDN。
CSDN:CSDN搜索“嵌入式與Linux那些事
我的GZH：嵌入式與Linux那些事，領(lǐng)取秋招筆試面試大禮包（華為小米等大廠面經(jīng)，嵌入式知識(shí)點(diǎn)總結(jié)，筆試題目，簡(jiǎn)歷模版等）和2000G學(xué)習(xí)資料。
