雙向鏈表哈蝇，也稱(chēng)為雙鏈表棺妓，是一種線性數(shù)據(jù)結(jié)構(gòu)，與單向鏈表類(lèi)似炮赦，但它在每個(gè)節(jié)點(diǎn)中額外存儲(chǔ)了一個(gè)指針怜跑，這個(gè)指針指向該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。因此，在雙向鏈表中性芬，每個(gè)節(jié)點(diǎn)都有兩個(gè)鏈接域峡眶，一個(gè)指向前一個(gè)節(jié)點(diǎn)（prev或previous），另一個(gè)指向下一個(gè)節(jié)點(diǎn)（next）植锉。這樣的設(shè)計(jì)使得在鏈表中雙向遍歷成為可能辫樱，即可以從頭到尾或從尾到頭地遍歷鏈表。
雙向鏈表的主要特點(diǎn)包括：
雙向遍歷：由于每個(gè)節(jié)點(diǎn)都保存了其前后節(jié)點(diǎn)的引用俊庇，所以可以在鏈表中雙向移動(dòng)狮暑，這在某些應(yīng)用場(chǎng)景下非常有用，比如快速反向遍歷或高效地在鏈表中間插入和刪除節(jié)點(diǎn)辉饱。
高效插入和刪除：相比于單向鏈表搬男，雙向鏈表在插入和刪除操作時(shí)可以更快地調(diào)整指針。特別是對(duì)于需要在某個(gè)節(jié)點(diǎn)之后插入新節(jié)點(diǎn)或者刪除該節(jié)點(diǎn)的情況彭沼，雙向鏈表可以直接通過(guò)當(dāng)前節(jié)點(diǎn)訪問(wèn)其前驅(qū)節(jié)點(diǎn)缔逛，無(wú)需從頭開(kāi)始遍歷。
內(nèi)存消耗：由于每個(gè)節(jié)點(diǎn)多了一個(gè)指針溜腐，雙向鏈表相比單向鏈表會(huì)占用更多的內(nèi)存空間。
頭部和尾部的標(biāo)識(shí)：雙向鏈表可以很容易地維護(hù)對(duì)頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的引用瓜喇，這在實(shí)現(xiàn)隊(duì)列等數(shù)據(jù)結(jié)構(gòu)時(shí)特別有用挺益。
結(jié)構(gòu)示例：
一個(gè)簡(jiǎn)單的雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)可以定義如下：
class Node {
int data; // 數(shù)據(jù)域
Node prev; // 指向前一個(gè)節(jié)點(diǎn)的指針
Node next; // 指向下一個(gè)節(jié)點(diǎn)的指針
}
在雙向鏈表中，通常還會(huì)有一個(gè)表示鏈表本身的類(lèi)乘寒，它包含對(duì)頭節(jié)點(diǎn)和可能的尾節(jié)點(diǎn)的引用望众，以及實(shí)現(xiàn)各種鏈表操作的方法，如添加伞辛、刪除烂翰、查找等。
應(yīng)用場(chǎng)景：
- 實(shí)現(xiàn)LRU緩存：雙向鏈表結(jié)合哈希表可以高效地實(shí)現(xiàn)最近最少使用（LRU）緩存策略蚤氏。
- undo/redo功能：在文本編輯器或圖形編輯軟件中甘耿，雙向鏈表可以用來(lái)高效地支持撤銷(xiāo)/重做操作。
- 雙向隊(duì)列（deque）：雙向鏈表自然適合實(shí)現(xiàn)允許兩端插入和刪除的隊(duì)列竿滨。
總之佳恬，雙向鏈表通過(guò)犧牲一定的內(nèi)存空間，換取了在特定操作上的效率提升和功能靈活性于游，是解決某些問(wèn)題時(shí)的理想選擇毁葱。
示例解析：
package com.dongf.chapter;
public class Node {
int id;
String name;
int score;
Node prev;
Node next;
public Node(int id, String name, int score) {
this.id = id;
this.name = name;
this.score = score;
}
}
package com.dongf.chapter;
public class DoublyLinkedList {
Node head;
Node tail;
public void append(int id, String name, int score) {
Node newNode = new Node(id, name, score);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
public void deleteById(int id) {
Node current = head;
while (current != null) {
if (current.id == id) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
}
public void updateById(int id, int newScore) {
Node current = head;
while (current != null) {
if (current.id == id) {
current.score = newScore;
return;
}
current = current.next;
}
}
public Node findById(int id) {
Node current = head;
while (current != null) {
if (current.id == id) {
return current;
}
current = current.next;
}
return null; // 如果沒(méi)找到返回null
}
public void printList() {
Node current = head;
while (current != null) {
System.out.println("ID: " + current.id + ", Name: " + current.name + ", Score: " + current.score);
current = current.next;
}
}
}
package com.dongf.chapter;
public class DoublyLinkedListMain {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// 添加數(shù)據(jù)
list.append(1, "張偉", 90);
list.append(2, "李華", 88);
list.append(3, "王芳", 92);
list.append(4, "趙六", 76);
list.append(5, "劉洋", 64);
// 打印鏈表
System.out.println("初始鏈表:");
list.printList();
// 更新張偉的成績(jī)?yōu)?3
list.updateById(1, 93);
System.out.println("\n更新張偉成績(jī)后的鏈表:");
list.printList();
// 刪除ID為4的節(jié)點(diǎn)
list.deleteById(4);
System.out.println("\n刪除ID為4的節(jié)點(diǎn)后的鏈表:");
list.printList();
// 查詢(xún)ID為3的節(jié)點(diǎn)
Node foundNode = list.findById(3);
if (foundNode != null) {
System.out.println("\n找到了節(jié)點(diǎn)：" + foundNode.name);
} else {
System.out.println("\n未找到指定ID的節(jié)點(diǎn)");
}
}
}
這段代碼定義了一個(gè)Node類(lèi)用于表示鏈表中的每個(gè)元素，以及一個(gè)DoublyLinkedList類(lèi)贰剥，實(shí)現(xiàn)了添加倾剿、刪除、更新和查詢(xún)節(jié)點(diǎn)的方法蚌成。在main方法中前痘，我們創(chuàng)建了一個(gè)雙向鏈表實(shí)例凛捏，執(zhí)行了增刪改查操作，并打印了相應(yīng)的結(jié)果际度。
