目前我們所學(xué)到的鏈表，無論是動(dòng)態(tài)鏈表還是靜態(tài)鏈表，表中各個(gè)節(jié)點(diǎn)都只包含一個(gè)指針（游標(biāo)），且都統(tǒng)一指向直接后繼節(jié)點(diǎn)，這類鏈表又統(tǒng)稱為單向鏈表或單鏈表。雖然單鏈表能 100% 存儲(chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但在解決某些實(shí)際問題時(shí)，單鏈表的執(zhí)行效率并不高。例如，若實(shí)際問題中需要頻繁地查找某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，使用單鏈表存儲(chǔ)數(shù)據(jù)顯然沒有優(yōu)勢(shì)，因?yàn)閱捂湵淼膹?qiáng)項(xiàng)是從前往后查找目標(biāo)元素，不擅長(zhǎng)從后往前查找元素。解決此類問題，可以建立雙向鏈表（簡(jiǎn)稱雙鏈表）。

(資料圖片僅供參考)

雙向鏈表是什么

從名字上理解雙向鏈表，即鏈表是 "雙向" 的，如圖?1 所示：

“雙向”指的是各節(jié)點(diǎn)之間的邏輯關(guān)系是雙向的，頭指針通常只設(shè)置一個(gè)。

從圖 1 中可以看到，雙向鏈表中各節(jié)點(diǎn)包含以下 3 部分信息（如圖 2 所示）：

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

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

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

因此，雙鏈表的節(jié)點(diǎn)結(jié)構(gòu)用 C 語言實(shí)現(xiàn)為：

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

同單鏈表相比，雙鏈表僅是各節(jié)點(diǎn)多了一個(gè)用于指向直接前驅(qū)的指針域。因此，我們可以在單鏈表的基礎(chǔ)輕松實(shí)現(xiàn)對(duì)雙鏈表的創(chuàng)建。需要注意的是，與單鏈表不同，雙鏈表創(chuàng)建過程中，每創(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 語言實(shí)現(xiàn)代碼：

我們可以嘗試著在 main 函數(shù)中輸出創(chuàng)建的雙鏈表，C 語言代碼如下：

程序運(yùn)行結(jié)果：

1 <-> 2 <-> 3 <-> 4 <-> 5鏈表中第 4 個(gè)節(jié)點(diǎn)的直接前驅(qū)是：3

關(guān)鍵詞：