双向链表通过prev和next指针实现前后遍历，适用于需高效删除、插入及反向遍历的场景，如LRU缓存、操作历史记录；相比单向链表，其操作更复杂且内存开销更大，实现时需注意边界条件、指针完整性、索引越界及垃圾回收等问题。
双向链表在JavaScript中，本质上是一种数据结构，每个节点不仅知道它后面是谁，还知道它前面是谁。这就像你翻一本书，不仅能往后翻页，也能轻松地往前翻页。实现上，它意味着每个节点除了包含数据本身，还会有一个指向下一个节点的引用（
next），以及一个指向前一个节点的引用（
prev）。它的主要优势在于，某些操作（比如删除一个已知节点，或者在某个节点前插入）的效率会比单向链表高得多。
解决方案
在JavaScript中实现一个双向链表，我们通常会定义一个
Node类和一个
DoublyLinkedList类。
Node负责存储数据和前后指针，
DoublyLinkedList则管理整个链表的头尾节点和长度，并提供操作方法。
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(value) {
// 如果提供了初始值，则创建第一个节点
if (value !== undefined) {
this.head = new Node(value);
this.tail = this.head;
this.length = 1;
} else {
this.head = null;
this.tail = null;
this.length = 0;
}
}
// 在链表末尾添加节点
append(value) {
const newNode = new Node(value);
if (!this.head) { // 链表为空
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
return this; // 链式调用
}
// 在链表开头添加节点
prepend(value) {
const newNode = new Node(value);
if (!this.head) { // 链表为空
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length++;
return this;
}
// 打印链表所有值
printList() {
const arr = [];
let currentNode = this.head;
while (currentNode !== null) {
arr.push(currentNode.value);
currentNode = currentNode.next;
}
console.log(arr.join(' <-> '));
return arr;
}
// 根据索引查找节点
_traverseToIndex(index) {
// 简单的优化：根据索引判断从头还是从尾开始遍历
let currentNode;
if (index < this.length / 2) {
currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
} else {
currentNode = this.tail;
for (let i = this.length - 1; i > index; i--) {
currentNode = currentNode.prev;
}
}
return currentNode;
}
// 在指定索引处插入节点
insert(index, value) {
if (index >= this.length) { // 如果索引超出范围，直接在末尾添加
return this.append(value);
}
if (index === 0) { // 在开头插入
return this.prepend(value);
}
const newNode = new Node(value);
const leader = this._traverseToIndex(index - 1); // 找到前一个节点
const follower = leader.next; // 找到后一个节点
leader.next = newNode;
newNode.prev = leader;
newNode.next = follower;
follower.prev = newNode; // 别忘了更新follower的prev指针
this.length++;
return this;
}
// 根据索引删除节点
remove(index) {
if (index < 0 || index >= this.length) {
console.error("Invalid index for removal.");
return null;
}
if (index === 0) { // 删除头节点
const removedNode = this.head;
this.head = this.head.next;
if (this.head) { // 如果链表不为空
this.head.prev = null;
} else { // 链表变空了
this.tail = null;
}
this.length--;
return removedNode;
}
if (index === this.length - 1) { // 删除尾节点
const removedNode = this.tail;
this.tail = this.tail.prev;
if (this.tail) { // 如果链表不为空
this.tail.next = null;
} else { // 链表变空了
this.head = null;
}
this.length--;
return removedNode;
}
const removedNode = this._traverseToIndex(index);
const leader = removedNode.prev;
const follower = removedNode.next;
leader.next = follower;
follower.prev = leader; // 更新follower的prev指针
this.length--;
return removedNode;
}
}
// 示例用法
// const myDoublyLinkedList = new DoublyLinkedList(10);
// myDoublyLinkedList.append(5);
// myDoublyLinkedList.append(16);
// myDoublyLinkedList.prepend(1);
// myDoublyLinkedList.insert(2, 99);
// myDoublyLinkedList.printList(); // 1 <-> 10 <-> 99 <-> 5 <-> 16
// myDoublyLinkedList.remove(2);
// myDoublyLinkedList.printList(); // 1 <-> 10 <-> 5 <-> 16
// myDoublyLinkedList.remove(0);
// myDoublyLinkedList.printList(); // 10 <-> 5 <-> 16
// myDoublyLinkedList.remove(2);
// myDoublyLinkedList.printList(); // 10 <-> 5双向链表的应用场景：它解决了哪些实际问题？
双向链表最显著的优势在于其“双向性”，这使得某些操作变得异常高效。在我看来，它并非万金油，但在特定场景下，简直是量身定制的解决方案。
首先，最直观的，高效的删除操作。假设你有一个指向某个节点的引用，在单向链表中，要删除这个节点，你得先找到它的前一个节点，这通常意味着从头开始遍历，时间复杂度是O(N)。但在双向链表中，因为每个节点都知道它的
prev，所以你可以直接通过
node.prev拿到前一个节点，然后调整前后指针，整个过程是O(1)的。这在需要频繁删除特定元素的场景下，比如实现一个LRU（Least Recently Used）缓存时，就显得尤为关键。LRU缓存需要快速将最近访问的元素移到链表头部，并将最久未使用的元素从尾部移除，双向链表的O(1)删除能力在这里发挥了核心作用。
其次，灵活的插入操作。在某个节点之前插入一个新节点，在单向链表中同样需要找到前一个节点，然后才能操作。双向链表则可以直接通过
node.prev定位，实现O(1)的插入。这对于需要维护特定顺序，并且频繁在中间位置进行增删的列表非常有用。
再来，反向遍历的便捷性。虽然不是所有应用都要求反向遍历，但当需要时，双向链表提供了原生的支持。比如浏览器的前进/后退历史功能，或者文本编辑器中的撤销/重做栈，都可以用双向链表来模拟，因为它们都需要在时间轴上前后移动。我曾在一个小型项目里用它来管理用户操作的历史记录，方便用户回溯，那种丝滑的体验是单向链表无法比拟的。
双向链表与单向链表：性能与资源消耗的权衡
任何数据结构的选择，都伴随着取舍。双向链表固然强大，但它并非没有代价。这就像你买一辆配置更全的车，享受更多便利的同时，也要付出更高的价格和油耗。
内存占用是双向链表最直接的“额外开销”。每个节点都多了一个
prev指针，这意味着在存储相同数量的数据时，双向链表会比单向链表占用更多的内存。对于数据量特别庞大，且内存资源极其敏感的应用，这可能是一个需要认真考虑的因素。虽然在现代JavaScript应用中，这点内存通常不是瓶颈，但理论上和大规模数据场景下，它依然是个事实。
操作复杂性也是一个需要注意的点。虽然某些操作（如删除已知节点）变得更简单，但整体而言，维护双向链表的完整性比单向链表要复杂一些。在进行插入或删除操作时，你不仅要更新
next指针，还得同时更新
prev指针。这意味着更多的指针操作，更多的潜在错误点。如果你不小心忘记更新其中一个指针，整个链表结构就可能被破坏，导致难以追踪的bug。比如，我自己在实现
remove方法时，就曾忘记更新被删除节点邻居的
prev指针，结果导致链表从那个点开始就无法反向遍历了。
所以，选择哪种链表，最终还是取决于你的具体需求。如果你的应用场景确实需要频繁地在中间位置删除或插入元素，或者需要反向遍历，那么双向链表的优势会远远盖过它的劣势。但如果你的需求仅仅是“添加”和“从头遍历”，那么单向链表会是更轻量、更简单的选择。
在JavaScript中实现双向链表时，有哪些需要避免的常见陷阱？
实现双向链表，尤其是在JavaScript这种动态语言中，虽然概念不复杂，但实际操作起来，还是有一些小坑需要留心，不然分分钟就能把链表搞得一团糟。
首先，空链表和单节点链表的边界情况。这是最容易出错的地方。当你
append第一个节点时，
head和
tail都应该指向它；当你
prepend到空链表时也一样。同样，当链表中只剩一个节点，然后你
remove掉它时，
head和
tail都应该设为
null。很多时候，代码写着写着，就只考虑了链表有多个节点的情况，而忽略了这些边缘状态，导致
head或
tail指针错误，进而整个链表崩坏。我通常会在每次操作后，在脑海里“跑一遍”空链表和单节点链表的情况，确保所有指针都更新正确。
其次，指针更新的完整性与顺序。这是双向链表的核心，也是最容易出错的地方。每一次插入或删除，都涉及到至少四个指针的更新（两个
next，两个
prev）。比如，在中间插入一个新节点
newNode，它位于
leader和
follower之间，你需要：
leader.next = newNode
newNode.prev = leader
newNode.next = follower
follower.prev = newNode
这四个步骤，一个都不能少，而且顺序也需要合理。如果顺序不对，或者少更新了一个，链表的双向连接就会被破坏。例如，你可能把leader.next
指向了newNode
，但follower.prev
仍然指向leader
，那么从follower
往回走，就会发现它“不认识”newNode
。这种不一致性是调试的噩梦。
再者，索引越界处理。虽然这不是双向链表特有的问题，但在实现
insert或
remove方法时，务必对传入的
index进行校验。比如，
index < 0或者
index >= this.length的情况，应该给出明确的错误提示或者采取默认行为（比如
insert时
index >= length就直接
append）。一个健壮的链表实现，必须能优雅地处理这些异常输入。
最后，一个可能被忽略但很重要的小点：JavaScript的垃圾回收机制。当你删除一个节点时，你需要确保所有指向这个节点的引用都被清除了。在我们的实现中，通过调整
next和
prev指针，被删除的节点自然就从链表中断开了，不再有外部引用指向它，JavaScript的垃圾回收器最终会清理掉它。但如果你的逻辑复杂，比如一个节点同时被多个结构引用，那么在删除链表节点时，可能还需要手动断开其他引用，以避免内存泄漏。不过对于基础的双向链表实现，这通常不是问题。
