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