JS实现双向链表及优势详解

怎么入门文章编程？需要学习哪些知识点？这是新手们刚接触编程时常见的问题；下面golang学习网就来给大家整理分享一些知识点，希望能够给初学者一些帮助。本篇文章就来介绍《JS中实现双向链表及优势解析》，涉及到，有需要的可以收藏一下

双向链表通过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之间，你需要：

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

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。