一、什么是雙向鏈表

我們來(lái)看一下這個(gè)例子：

在一個(gè)教室里，所有的課桌排成一列，如圖

相信在你們的讀書(shū)生涯中，老師肯定有要求你們記住自己的前后桌是誰(shuí)。所以該例子中，老師就要求學(xué)生們記住自己的前后桌，其中坐在第一排的學(xué)生需要記住自己是第一排的學(xué)生以及自己的后桌是誰(shuí)；最后一排的學(xué)生要記住自己的前桌是誰(shuí)以及自己是最后一排的學(xué)生。如圖：

這一列座位就相當(dāng)于一個(gè) 雙向鏈表。

假如有一天，老師還沒(méi)記住每個(gè)學(xué)生的名字，于是就問(wèn)：這一列第三個(gè)人叫什么名字？這時(shí)就要從第一個(gè)學(xué)生開(kāi)始數(shù)，例如從圖中坐在第一個(gè)的 小5 開(kāi)始數(shù)：第一個(gè)人是 小5，他的后桌是 小7；因此第二個(gè)人就是 小7，他的后桌是 小1；因此第三個(gè)人就是 小1 了。此時(shí)老師問(wèn) 小1：你的前桌叫什么名字？你的后桌叫什么名字？

因?yàn)閯傞_(kāi)始老師就讓每個(gè)學(xué)生記住了自己的前桌以及后桌，所以此時(shí) 小1 能很快地告訴老師他的前桌是 小7，他的后桌是 小6。

但是，我們?cè)O(shè)想一下，如果是上一篇文章的 鏈表結(jié)構(gòu) 的例子中，如果老師在得知了第三個(gè)人是 小1 以后，詢問(wèn) 小1 的前桌叫什么名字，小1 能回答上來(lái)嗎？并不能，因?yàn)槔蠋熤蛔屆總€(gè)學(xué)生記住了自己的后桌，所以此時(shí)想要得知 小1 的前桌叫什么名字，只能這樣：第三個(gè)學(xué)生叫 小1，那么他的前桌就坐在第二個(gè)位置，所以從第一個(gè)學(xué)生開(kāi)始數(shù)，第一個(gè)學(xué)生是 小5，他的后桌是 小7；因此第二個(gè)學(xué)生就是 小7。當(dāng)然本文舉得例子中學(xué)生數(shù)量有點(diǎn)少，但一旦數(shù)量多起來(lái)了，每次問(wèn)一個(gè)學(xué)生他的前桌叫什么名字的時(shí)候，都要從頭開(kāi)始數(shù)。

從中可以看出，讓每個(gè)學(xué)生記住自己的前桌后桌是非常有必要的，因?yàn)樵谀承┣闆r下，可以快速地解決問(wèn)題。

上面講了那么多，接下來(lái)我們就來(lái)看一下 雙向鏈表 是什么樣的，如圖

可以看到，對(duì)比 鏈表結(jié)構(gòu)，雙向鏈表 多了一個(gè)指針 tail，它是指向最后一個(gè)元素的，就相當(dāng)于例子中的學(xué)生記住了自己是最后一排。

雙向鏈表與單鏈表基本相似，但是最大的區(qū)別在于雙向鏈表在節(jié)點(diǎn)中除了指向下一節(jié)點(diǎn)的next指針外，還有指向前一節(jié)點(diǎn)的prev指針，這使得雙向鏈表在可以在任意節(jié)點(diǎn)從頭尾兩個(gè)方向進(jìn)行遍歷，是“雙向”的。

和單鏈表相比，雙向鏈表在刪除和查詢等方面明顯在操作上更具有靈活性，但是會(huì)消耗更多的內(nèi)存，需要根據(jù)使用條件進(jìn)行取舍。

java中的LinkedHashMap的本質(zhì)即是一個(gè)雙向鏈表。

二、雙向鏈表的簡(jiǎn)單實(shí)現(xiàn)

修改原來(lái)的Node類，在里面添加一個(gè)新成員變量Node prev

/*** @Author：huang* @Date：2023-03-23 20:10* @Description：節(jié)點(diǎn)類*/
public class Node {//節(jié)點(diǎn)序號(hào)int num;//數(shù)據(jù)Object data;//下一個(gè)節(jié)點(diǎn)Node next;//上一節(jié)點(diǎn)Node prev;public Node(int num, Object data) {this.num = num;this.data = data;}@Overridepublic String toString() {return "Node{" +"num=" + num +", data=" + data +'}';}
}

1. 添加
   添加與單向鏈表代碼邏輯一樣，但是新節(jié)點(diǎn)在添加時(shí)需要修改prev指針指向原來(lái)的尾節(jié)點(diǎn)。
   舉個(gè)例子，對(duì)于無(wú)排序插入，原本有節(jié)點(diǎn)A，現(xiàn)在要插入一個(gè)B：

• 找到A，然后讓A.next指向B
• 讓B.prev指向A

而對(duì)于排序插入，就是原有節(jié)點(diǎn)A，C，要在中間插入B：

• 找到A，讓B.prev指向A
• 讓B.next指向A.next，也就是讓B的next指向C
• 讓A.next.prev指向B，也就是讓C的prev指向B
• 讓A.next指向B

/*** 添加節(jié)點(diǎn)到鏈表* @param node 要插入的節(jié)點(diǎn)*/
public void add(Node node) {Node temp = head;//遍歷鏈表while (true) {if (temp.next == null) {break;}//不是尾節(jié)點(diǎn)就繼續(xù)遍歷下一個(gè)節(jié)點(diǎn)temp = temp.next;}//將尾節(jié)點(diǎn)指向即將插入的新節(jié)點(diǎn)temp.next = node;node.prev = temp;
}/*** 按順序添加節(jié)點(diǎn)到鏈表* @param node 要插入的節(jié)點(diǎn)*/
public void addByOrder(Node node) {Node temp = head;//遍歷鏈表while (true) {//如果鏈表到底了就直接插入if (temp.next == null) {temp.next = node;node.prev = temp;return;}else if (temp.next.num > node.num){//如果后一節(jié)點(diǎn)比當(dāng)新節(jié)點(diǎn)大，就插入當(dāng)前節(jié)點(diǎn)node.prev = temp;node.next = temp.next;temp.next.prev = node;temp.next = node;return;}else if (temp.next.num == node.num){//如果后一節(jié)點(diǎn)等于新節(jié)點(diǎn)，拋異常throw new RuntimeException("插入節(jié)點(diǎn)與已有節(jié)點(diǎn)序號(hào)重復(fù)！");}//如果后一節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小，就繼續(xù)遍歷temp = temp.next;}
}

2. 刪除
   由于相對(duì)單鏈表，雙向鏈表的節(jié)點(diǎn)可以自己找到上一節(jié)點(diǎn)，所以刪除的時(shí)候可以直接找到要?jiǎng)h除的節(jié)點(diǎn)進(jìn)行操作。

舉個(gè)例子，假設(shè)有節(jié)點(diǎn)A，B，C，現(xiàn)在要?jiǎng)h除B：

• 找到B，讓B.prev.next=B.next，也就是讓A的next指向C
• 讓B.next.prev=B.prev，也就是讓C的prev指向A

如果要?jiǎng)h除的節(jié)點(diǎn)已經(jīng)是尾節(jié)點(diǎn)了，那就跟單鏈表一樣了。

/*** 刪除節(jié)點(diǎn)* @param num 要?jiǎng)h除的節(jié)點(diǎn)編號(hào)*/
public void delete(int num) {Node temp = head;//判斷鏈表是否為空if (temp.next == null) {throw new RuntimeException("鏈表為空！");}//遍歷鏈表while (true) {//如果鏈表到底了if (temp.next == null) {throw new RuntimeException("編號(hào)為" + num + "的節(jié)點(diǎn)不存在！");}//如果找到了待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)if (temp.num == num) {//判斷待刪除節(jié)點(diǎn)是否為尾節(jié)點(diǎn)if (temp.next == null){temp.prev.next = null;}else {temp.prev.next = temp.next;temp.next.prev = temp.prev;}return;}//繼續(xù)遍歷下一節(jié)點(diǎn)temp = temp.next;}
}

3. 修改，查詢（與單鏈表一致）
   由于修改和查詢與單鏈表基本一致，這里就不在贅述了，直接放代碼：

/*** 展示鏈表*/
public void show() {//判斷鏈表是否為空if (head.next == null) {throw new RuntimeException("鏈表為空！");}Node temp = head.next;//遍歷鏈表while (true) {if (temp == null) {break;}System.out.println(temp.toString());temp = temp.next;}
}/*** 根據(jù)序號(hào)獲取節(jié)點(diǎn)* @param num 要獲取的節(jié)點(diǎn)序號(hào)* @return*/
public Node get(int num){//判斷鏈表是否為空if (head.next == null) {throw new RuntimeException("鏈表為空！");}Node temp = head.next;//遍歷鏈表while (true) {if (temp == null) {throw new RuntimeException("編號(hào)為" + num + "的節(jié)點(diǎn)不存在！");}if (temp.num == num) {return temp;}temp = temp.next;}
}/*** 修改節(jié)點(diǎn)* @param node 要更新的節(jié)點(diǎn)*/
public void update(Node node) {Node temp = head;//判斷鏈表是否為空if (temp.next == null) {throw new RuntimeException("鏈表為空！");}//獲取要更新的節(jié)點(diǎn)序號(hào)int nodeNum = node.num;//遍歷鏈表while (true) {//如果已經(jīng)遍歷完鏈表if (temp == null) {throw new RuntimeException("編號(hào)為" + temp.num + "的節(jié)點(diǎn)不存在！");}//如果找到了該節(jié)點(diǎn)if (temp.num == nodeNum) {temp.data = node.data;return;}//繼續(xù)遍歷下一節(jié)點(diǎn)temp = temp.next;}
}