一、什么是双向链表？

双向链表（Doubly Linked List）是一种特殊的链表结构，每个节点除了存储数据和指向下一个节点的指针（next）外，还包含指向前一个节点的指针（prev）。这种设计使得链表可以双向遍历，为操作提供了更大的灵活性。

javascript class DoublyLinkedListNode { constructor(data) { this.data = data; this.next = null; this.prev = null; } }

二、完整实现方案

基础框架搭建

javascript
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}

// 方法实现将在这里展开
}

核心方法实现

1. 插入操作javascript
   // 头部插入
   insertAtHead(data) {
   const newNode = new DoublyLinkedListNode(data);

   if (!this.head) {
   this.head = newNode;
   this.tail = newNode;
   } else {
   newNode.next = this.head;
   this.head.prev = newNode;
   this.head = newNode;
   }

   this.length++;
   }

// 尾部插入
insertAtTail(data) {
const newNode = new DoublyLinkedListNode(data);

if (!this.tail) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}

this.length++;
}

1. 删除操作javascript
   // 删除头节点
   deleteHead() {
   if (!this.head) return null;

   const removedNode = this.head;

   if (this.head === this.tail) {
   this.head = null;
   this.tail = null;
   } else {
   this.head = this.head.next;
   this.head.prev = null;
   }

   this.length--;
   return removedNode.data;
   }

2. 查找与遍历javascript
   // 正向遍历
   forwardTraversal() {
   let current = this.head;
   while (current) {
   console.log(current.data);
   current = current.next;
   }
   }

// 反向遍历
backwardTraversal() {
let current = this.tail;
while (current) {
console.log(current.data);
current = current.prev;
}
}

三、性能优势解析

1. 双向遍历能力
   相比单向链表只能从头到尾遍历，双向链表支持：

- 从头到尾的正向遍历
- 从尾到头的反向遍历
- 任意节点开始的向两端遍历

1. 删除操作优化
   在删除特定节点时，双向链表时间复杂度可降至O(1)：javascript
   // 给定节点时的删除操作
   deleteNode(node) {
   if (node.prev) node.prev.next = node.next;
   else this.head = node.next;

   if (node.next) node.next.prev = node.prev;
   else this.tail = node.prev;

   this.length--;
   }

2. 实际应用场景

- 浏览器历史记录管理（前进/后退）
- 音乐播放器的播放列表
- 撤销/重做功能实现
- LRU缓存淘汰算法

四、与单向链表对比

| 操作类型 | 双向链表 | 单向链表 |
|----------------|----------|----------|
| 插入/删除头节点 | O(1) | O(1) |
| 插入/删除尾节点 | O(1) | O(n) |
| 反向遍历 | O(n) | 无法实现 |
| 内存占用 | 较高 | 较低 |

五、进阶优化技巧

1. 实现迭代器协议
   javascript [Symbol.iterator]() { let current = this.head; return { next() { if (current) { const value = current.data; current = current.next; return { value, done: false }; } return { done: true }; } }; }

2. 环形双向链表
   通过连接头尾节点形成环形结构，适合需要循环访问的场景：
   javascript makeCircular() { if (this.head && this.tail) { this.head.prev = this.tail; this.tail.next = this.head; } }

六、实际应用示例

浏览器历史记录实现javascript
class BrowserHistory {
constructor() {
this.pages = new DoublyLinkedList();
this.currentPage = null;
}

visit(url) {
this.pages.insertAtTail(url);
this.currentPage = this.pages.tail;
}

back() {
if (this.currentPage?.prev) {
this.currentPage = this.currentPage.prev;
return this.currentPage.data;
}
return null;
}

forward() {
if (this.currentPage?.next) {
this.currentPage = this.currentPage.next;
return this.currentPage.data;
}
return null;
}
}

七、注意事项

1. 指针维护成本
   每次插入/删除都需要维护prev和next指针，容易出错

2. 内存考虑
   每个节点多存储一个指针，在数据量极大时需要权衡

3. 边界条件处理
   特别注意头尾节点的特殊处理