双向链表通过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的垃圾回收器最终会清理掉它。但如果你的逻辑复杂，比如一个节点同时被多个结构引用，那么在删除链表节点时，可能还需要手动断开其他引用，以避免内存泄漏。不过对于基础的双向链表实现，这通常不是问题。
评论（已关闭）
评论已关闭