双向链表，也称为双链表，是一种线性数据结构，与单向链表类似，但它在每个节点中额外存储了一个指针，这个指针指向该节点的前一个节点。因此，在双向链表中，每个节点都有两个链接域，一个指向前一个节点（prev或previous），另一个指向下一个节点（next）。这样的设计使得在链表中双向遍历成为可能，即可以从头到尾或从尾到头地遍历链表。
双向链表的主要特点包括：
双向遍历：由于每个节点都保存了其前后节点的引用，所以可以在链表中双向移动，这在某些应用场景下非常有用，比如快速反向遍历或高效地在链表中间插入和删除节点。
高效插入和删除：相比于单向链表，双向链表在插入和删除操作时可以更快地调整指针。特别是对于需要在某个节点之后插入新节点或者删除该节点的情况，双向链表可以直接通过当前节点访问其前驱节点，无需从头开始遍历。
内存消耗：由于每个节点多了一个指针，双向链表相比单向链表会占用更多的内存空间。
头部和尾部的标识：双向链表可以很容易地维护对头节点和尾节点的引用，这在实现队列等数据结构时特别有用。
结构示例：
一个简单的双向链表节点结构可以定义如下：
class Node {
int data; // 数据域
Node prev; // 指向前一个节点的指针
Node next; // 指向下一个节点的指针
}
双向链表.png
在双向链表中，通常还会有一个表示链表本身的类，它包含对头节点和可能的尾节点的引用，以及实现各种链表操作的方法，如添加、删除、查找等。
应用场景：
- 实现LRU缓存：双向链表结合哈希表可以高效地实现最近最少使用（LRU）缓存策略。
- undo/redo功能：在文本编辑器或图形编辑软件中，双向链表可以用来高效地支持撤销/重做操作。
- 双向队列（deque）：双向链表自然适合实现允许两端插入和删除的队列。
总之，双向链表通过牺牲一定的内存空间，换取了在特定操作上的效率提升和功能灵活性，是解决某些问题时的理想选择。
示例解析：
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;
}
}
Image00482.png
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;
}
}
}
Image00483.png
Image00484.png
Image00485.png
Image00486.png
package com.dongf.chapter;
public class DoublyLinkedListMain {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// 添加数据
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();
// 更新张伟的成绩为93
list.updateById(1, 93);
System.out.println("\n更新张伟成绩后的链表:");
list.printList();
// 删除ID为4的节点
list.deleteById(4);
System.out.println("\n删除ID为4的节点后的链表:");
list.printList();
// 查询ID为3的节点
Node foundNode = list.findById(3);
if (foundNode != null) {
System.out.println("\n找到了节点：" + foundNode.name);
} else {
System.out.println("\n未找到指定ID的节点");
}
}
}
Image00487.png
Image00488.png
这段代码定义了一个Node类用于表示链表中的每个元素，以及一个DoublyLinkedList类，实现了添加、删除、更新和查询节点的方法。在main方法中，我们创建了一个双向链表实例，执行了增删改查操作，并打印了相应的结果。
