1.雙向鏈表的定義

單向鏈表特點：

1.我們可以輕松的到達下一個節(jié)點, 但是回到前一個節(jié)點是很難的.

2.只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)

雙向鏈表特點：

1.每次在插入或刪除某個節(jié)點時, 需要處理四個節(jié)點的引用, 而不是兩個. 實現(xiàn)起來要困難一些

2.相對于單向鏈表, 必然占用內(nèi)存空間更大一些.

3.既可以從頭遍歷到尾, 又可以從尾遍歷到頭

雙向鏈表的定義：

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。下圖為雙向鏈表的結(jié)構(gòu)圖。

從上中可以看到，雙向鏈表中各節(jié)點包含以下 3 部分信息：

指針域：用于指向當(dāng)前節(jié)點的直接前驅(qū)節(jié)點；

數(shù)據(jù)域：用于存儲數(shù)據(jù)元素。

指針域：用于指向當(dāng)前節(jié)點的直接后繼節(jié)點；

雙向循環(huán)鏈表的定義:

雙向鏈表也可以進行首尾連接，構(gòu)成雙向循環(huán)鏈表,如下圖所示

在創(chuàng)建鏈表時，只需要在最后將收尾相連即可（創(chuàng)建鏈表代碼中已經(jīng)標(biāo)出）。其他代碼稍加改動即可。

雙鏈表的節(jié)點結(jié)構(gòu)用 C 語言實現(xiàn)為：

2.雙向鏈表的創(chuàng)建

同單鏈表相比，雙鏈表僅是各節(jié)點多了一個用于指向直接前驅(qū)的指針域。因此，我們可以在單鏈表的基礎(chǔ)輕松實現(xiàn)對雙鏈表的創(chuàng)建。

需要注意的是，與單鏈表不同，雙鏈表創(chuàng)建過程中，每創(chuàng)建一個新節(jié)點，都要與其前驅(qū)節(jié)點建立兩次聯(lián)系，分別是：

將新節(jié)點的 prior 指針指向直接前驅(qū)節(jié)點；

將直接前驅(qū)節(jié)點的 next 指針指向新節(jié)點；

這里給出創(chuàng)建雙向鏈表的 C 語言實現(xiàn)代碼：

3.雙向鏈表的插入

根據(jù)數(shù)據(jù)添加到雙向鏈表中的位置不同，可細分為以下 3 種情況：

1.添加至表頭

將新數(shù)據(jù)元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關(guān)系即可。

換句話說，假設(shè)新元素節(jié)點為 temp，表頭節(jié)點為 head，則需要做以下 2 步操作即可：

temp->next=head; head->prior=temp;

將 head 移至 temp，重新指向新的表頭；

將新元素 7 添加至雙鏈表的表頭，則實現(xiàn)過程如下圖所示：

2.添加至表的中間位置

同單鏈表添加數(shù)據(jù)類似，雙向鏈表中間位置添加數(shù)據(jù)需要經(jīng)過以下 2 個步驟，如下圖所示：

新節(jié)點先與其直接后繼節(jié)點建立雙層邏輯關(guān)系；

新節(jié)點的直接前驅(qū)節(jié)點與之建立雙層邏輯關(guān)系；

3.添加至表尾

與添加到表頭是一個道理，實現(xiàn)過程如下：

找到雙鏈表中最后一個節(jié)點；

讓新節(jié)點與最后一個節(jié)點進行雙層邏輯關(guān)系；

本次分享就到這里了！學(xué)習(xí)知識并不能一蹴而就，一步步來喲~

下篇文章為大家分享雙向鏈表的刪除以及查找，一定要看哦！

另外如果你想更好的提升你的編程能力，學(xué)好C語言C++編程！彎道超車，快人一步！筆者這里或許可以幫到你~

UP在主頁上傳了一些學(xué)習(xí)C/C++編程的視頻教程，有興趣或者正在學(xué)習(xí)的小伙伴一定要去看一看哦！會對你有幫助的~

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！

編程學(xué)習(xí)書籍分享：

編程學(xué)習(xí)視頻分享：