链表是一种通过指针连接节点的灵活数据结构，节点包含数据和指向下一节点的引用，内存中无需连续存放。与数组相比，链表在插入和删除操作上更高效，尤其在头部或中间位置，时间复杂度为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
，而是指回链表的头部（或第一个节点）。这形成了一个闭环。循环链表在某些需要“循环”访问数据的场景中非常有用，比如任务调度器中的“轮询”机制，或者处理环形缓冲区。它最大的优点是，从任何一个节点开始，你都可以遍历整个链表，并且没有明确的“尾部”概念，这简化了某些操作。但同时，在遍历时，你需要特别注意终止条件，以避免无限循环。比如，你可能需要记录遍历的起始点，并在再次回到起始点时停止。
总的来说，选择哪种链表类型，取决于你的具体需求：是需要快速的随机访问（数组），还是频繁的插入/删除且顺序访问即可（单向链表），亦或是需要双向遍历的灵活性（双向链表），还是需要循环访问数据的特性（循环链表）。每种都有其适用场景和相应的权衡。
评论（已关闭）
评论已关闭