雙向鏈表，也稱為雙鏈表，是一種線性數(shù)據(jù)結(jié)構(gòu)，與單向鏈表類似，但它在每個節(jié)點中額外存儲了一個指針，這個指針指向該節(jié)點的前一個節(jié)點。因此，在雙向鏈表中，每個節(jié)點都有兩個鏈接域，一個指向前一個節(jié)點（prev或previous），另一個指向下一個節(jié)點（next）。這樣的設(shè)計使得在鏈表中雙向遍歷成為可能，即可以從頭到尾或從尾到頭地遍歷鏈表。
雙向鏈表的主要特點包括：
雙向遍歷：由于每個節(jié)點都保存了其前后節(jié)點的引用，所以可以在鏈表中雙向移動，這在某些應(yīng)用場景下非常有用，比如快速反向遍歷或高效地在鏈表中間插入和刪除節(jié)點。
高效插入和刪除：相比于單向鏈表，雙向鏈表在插入和刪除操作時可以更快地調(diào)整指針。特別是對于需要在某個節(jié)點之后插入新節(jié)點或者刪除該節(jié)點的情況，雙向鏈表可以直接通過當(dāng)前節(jié)點訪問其前驅(qū)節(jié)點，無需從頭開始遍歷。
內(nèi)存消耗：由于每個節(jié)點多了一個指針，雙向鏈表相比單向鏈表會占用更多的內(nèi)存空間。
頭部和尾部的標(biāo)識：雙向鏈表可以很容易地維護(hù)對頭節(jié)點和尾節(jié)點的引用，這在實現(xiàn)隊列等數(shù)據(jù)結(jié)構(gòu)時特別有用。
結(jié)構(gòu)示例：
一個簡單的雙向鏈表節(jié)點結(jié)構(gòu)可以定義如下：
class Node {
int data; // 數(shù)據(jù)域
Node prev; // 指向前一個節(jié)點的指針
Node next; // 指向下一個節(jié)點的指針
}
在雙向鏈表中，通常還會有一個表示鏈表本身的類，它包含對頭節(jié)點和可能的尾節(jié)點的引用，以及實現(xiàn)各種鏈表操作的方法，如添加、刪除、查找等。
應(yīng)用場景：
- 實現(xiàn)LRU緩存：雙向鏈表結(jié)合哈希表可以高效地實現(xiàn)最近最少使用（LRU）緩存策略。
- undo/redo功能：在文本編輯器或圖形編輯軟件中，雙向鏈表可以用來高效地支持撤銷/重做操作。
- 雙向隊列（deque）：雙向鏈表自然適合實現(xiàn)允許兩端插入和刪除的隊列。
總之，雙向鏈表通過犧牲一定的內(nèi)存空間，換取了在特定操作上的效率提升和功能靈活性，是解決某些問題時的理想選擇。
示例解析：
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; // 如果沒找到返回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();
// 更新張偉的成績?yōu)?3
list.updateById(1, 93);
System.out.println("\n更新張偉成績后的鏈表:");
list.printList();
// 刪除ID為4的節(jié)點
list.deleteById(4);
System.out.println("\n刪除ID為4的節(jié)點后的鏈表:");
list.printList();
// 查詢ID為3的節(jié)點
Node foundNode = list.findById(3);
if (foundNode != null) {
System.out.println("\n找到了節(jié)點：" + foundNode.name);
} else {
System.out.println("\n未找到指定ID的節(jié)點");
}
}
}
這段代碼定義了一個Node類用于表示鏈表中的每個元素，以及一個DoublyLinkedList類，實現(xiàn)了添加、刪除、更新和查詢節(jié)點的方法。在main方法中，我們創(chuàng)建了一個雙向鏈表實例，執(zhí)行了增刪改查操作，并打印了相應(yīng)的結(jié)果。
