链表是什么？JS实现链表结构详解

目前golang学习网上已经有很多关于文章的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《链表是什么？JS如何实现链表结构》，也希望能帮助到大家，如果阅读完后真的对你学习文章有帮助，欢迎动动手指，评论留言并分享~

链表是一种通过指针连接节点的灵活数据结构，节点包含数据和指向下一节点的引用，内存中无需连续存放。与数组相比，链表在插入和删除操作上更高效，尤其在头部或中间位置，时间复杂度为O(1)（查找位置除外），而数组需移动元素，耗时O(n)。但链表访问元素需从头遍历，随机访问性能差，为O(n)，且每个节点额外占用内存存储指针。JavaScript中通过定义Node类和LinkedList类实现链表，支持append、prepend、insertAt、find、delete等操作。链表适用于频繁增删的场景，如LRU缓存、栈、队列、浏览器历史记录等。双向链表增加prev指针，支持前后双向遍历，删除更便捷，但内存开销更大；循环链表末尾节点指向头节点，形成闭环，适合轮询调度等循环访问场景，但遍历时需防止无限循环。选择链表还是数组，取决于应用对访问、插入、删除效率及内存的权衡。

链表，在我看来，它是一种相当基础但又极其灵活的数据结构，你可以把它想象成一系列通过“指针”或“引用”连接起来的节点，每个节点不仅存放着数据，还知道下一个节点在哪里。它不像数组那样在内存中是连续存放的，每个节点可以分散在任何地方，只要它们之间的连接关系是正确的就行。这正是它魅力所在，也是它与数组最本质的区别。

解决方案

在JavaScript中实现一个链表结构，我们通常需要定义两个核心部分：节点（Node）和链表本身（LinkedList）。

首先是节点，它很简单，就是一个包含数据和指向下一个节点引用的对象：

class Node {
    constructor(data) {
        this.data = data; // 节点存储的数据
        this.next = null; // 指向下一个节点的引用，初始为null
    }
}

接着是链表类，它需要管理这些节点，通常会有一个指向链表头部的引用：

class LinkedList {
    constructor() {
        this.head = null; // 链表的头部，初始为空
        this.size = 0;    // 链表中节点的数量
    }

    // 添加节点到链表末尾
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            // 如果链表为空，新节点就是头部
            this.head = newNode;
        } else {
            // 遍历到链表末尾，将新节点添加到最后
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // 在链表头部添加节点
    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head; // 新节点的next指向原头部
        this.head = newNode;      // 新节点成为新的头部
        this.size++;
    }

    // 在指定位置插入节点
    insertAt(data, index) {
        if (index < 0 || index > this.size) {
            console.error("插入位置无效");
            return;
        }
        if (index === 0) {
            this.prepend(data);
            return;
        }

        const newNode = new Node(data);
        let current = this.head;
        let previous;
        let count = 0;

        while (count < index) {
            previous = current;
            current = current.next;
            count++;
        }

        newNode.next = current;
        previous.next = newNode;
        this.size++;
    }

    // 查找节点（按数据）
    find(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) {
                return current; // 找到并返回节点
            }
            current = current.next;
        }
        return null; // 未找到
    }

    // 删除指定数据的节点
    delete(data) {
        if (!this.head) {
            return null;
        }

        if (this.head.data === data) {
            this.head = this.head.next; // 如果是头部，直接移动头部指针
            this.size--;
            return;
        }

        let current = this.head;
        let previous = null;
        while (current && current.data !== data) {
            previous = current;
            current = current.next;
        }

        if (current) {
            previous.next = current.next; // 跳过当前节点，实现删除
            this.size--;
        } else {
            console.warn(`未找到数据为 ${data} 的节点`);
        }
    }

    // 遍历链表并打印所有节点数据
    printList() {
        let current = this.head;
        let listStr = "";
        while (current) {
            listStr += current.data + " -> ";
            current = current.next;
        }
        listStr += "null";
        console.log(listStr);
    }
}

// 示例用法
const myList = new LinkedList();
myList.append(10);
myList.append(20);
myList.prepend(5);
myList.insertAt(15, 2); // 5 -> 10 -> 15 -> 20 -> null
myList.printList(); // 输出: 5 -> 10 -> 15 -> 20 -> null

myList.delete(10);
myList.printList(); // 输出: 5 -> 15 -> 20 -> null

console.log("查找 15:", myList.find(15)?.data); // 输出: 查找 15: 15

为什么我们需要链表，它和数组有什么不同？

我个人觉得，理解链表存在的价值，很大程度上要通过对比数组来体现。数组在内存中是连续分配的，这使得它在随机访问（通过索引直接获取元素）时效率极高，O(1) 的时间复杂度。但这种连续性也带来了它的痛点：如果你想在数组中间插入或删除一个元素，那可就麻烦了。你需要将插入点之后的所有元素都向后或向前移动，这在数据量大时，开销是巨大的，时间复杂度通常是 O(n)。

链表则完全不同。它的节点可以分散在内存的任何地方，它们之间靠“指针”或“引用”维系关系。这意味着，在链表头部或尾部（如果你维护了尾指针）进行插入和删除操作，效率非常高，通常是 O(1)。即使在链表中间插入或删除，也只需要找到目标位置的前一个节点，然后修改几个指针的指向即可，虽然查找目标位置本身可能需要 O(n) 的时间，但一旦找到，操作本身是 O(1)。

当然，链表也有它的不足。它不能像数组那样通过索引直接访问任意元素，你必须从头开始遍历。这使得它的随机访问能力是 O(n)。而且，每个节点除了数据本身，还需要额外的空间来存储指向下一个节点的引用，这在一定程度上增加了内存开销。所以，选择哪种数据结构，真的取决于你的具体应用场景，没有绝对的优劣，只有更适合。

链表在实际开发中有哪些应用场景？

链表在实际开发中，虽然不像数组那样随处可见，但它在某些特定场景下，表现出独特的优势。比如，我接触过的一些系统，在实现LRU（Least Recently Used）缓存淘汰策略时，就经常会用到双向链表。当一个缓存项被访问时，它会被移动到链表的头部，而当缓存空间不足时，就直接淘汰链表尾部的元素，这个操作非常高效。

另一个常见的例子是实现栈和队列。虽然数组也能实现，但链表在头部或尾部的插入/删除操作（对应栈的push/pop或队列的enqueue/dequeue）效率更高，尤其是在处理大量数据时，可以避免数组因扩容或缩容带来的性能抖耗。

还有一些场景，比如浏览器的前进/后退历史记录，也可以用双向链表来模拟。每次访问一个新页面，就添加一个节点；点击后退，就移动到前一个节点。此外，一些音乐播放列表或任务调度队列，也可能采用链表结构，因为它们的核心操作就是添加、删除和遍历。

甚至在更底层，像内存管理中的空闲块链表，或者某些文件系统中的文件分配表，其底层逻辑也与链表有异曲同工之妙。虽然这些概念可能不直接暴露给JavaScript开发者，但理解链表有助于我们更好地理解计算机科学的基石。

实现双向链表或循环链表有什么额外的考量？

当我们谈到链表时，通常指的是单向链表。但如果你的应用场景需要更灵活的遍历或删除操作，双向链表（Doubly Linked List）和循环链表（Circular Linked List）就值得考虑了。

双向链表，顾名思义，它的每个节点不仅有一个指向下一个节点的 next 指针，还有一个指向前一个节点的 prev 指针。这使得你可以从任意节点向前或向后遍历链表，大大增加了遍历的灵活性。同时，删除操作也变得更简单，因为你不需要为了找到前一个节点而从头开始遍历。代价是每个节点需要多存储一个指针，增加了内存开销，并且在插入和删除时，需要维护的指针关系也多了一个，逻辑上会稍微复杂一点。例如，在删除一个节点时，你需要同时更新其前一个节点的 next 指针和后一个节点的 prev 指针。

而循环链表则是一种特殊形式的链表，它的最后一个节点的 next 指针不是指向 null，而是指回链表的头部（或第一个节点）。这形成了一个闭环。循环链表在某些需要“循环”访问数据的场景中非常有用，比如任务调度器中的“轮询”机制，或者处理环形缓冲区。它最大的优点是，从任何一个节点开始，你都可以遍历整个链表，并且没有明确的“尾部”概念，这简化了某些操作。但同时，在遍历时，你需要特别注意终止条件，以避免无限循环。比如，你可能需要记录遍历的起始点，并在再次回到起始点时停止。

总的来说，选择哪种链表类型，取决于你的具体需求：是需要快速的随机访问（数组），还是频繁的插入/删除且顺序访问即可（单向链表），亦或是需要双向遍历的灵活性（双向链表），还是需要循环访问数据的特性（循环链表）。每种都有其适用场景和相应的权衡。

理论要掌握，实操不能落！以上关于《链表是什么？JS实现链表结构详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！