算法 - 10. 链表

何时使用链表

当你需要在已知位置进行高效插入/删除的动态大小时，使用链表。虽然数组在随机访问方面表现出色，但链表在以下情况下更适合：

• 在前端频繁插入/删除（经典用例）
• 实现栈和队列（具有O(1)操作）
• 撤销功能（维护操作历史）
• 音乐播放列表（下一个/上一个导航）
• 浏览器历史（前进/后退导航）
• 任何频繁添加/删除元素且不需要随机访问的问题

示例问题

文本编辑器撤销系统：你正在构建一个需要跟踪每个编辑操作以实现无限撤销/重做功能的文本编辑器。

• 用户输入"Hello"（5个操作）
• 用户删除"lo"（2个操作）
• 用户输入" World"（6个操作）
• 用户想要撤销最后3个操作

答案：链表完美地维护操作序列，允许O(1)插入新操作，并轻松地向后遍历以进行撤销操作。与数组不同，我们不会预先分配可能不使用的空间而浪费内存。

最重要的洞察

链表用在任何位置O(1)时间内插入/删除的能力换取了随机访问 - 通过在边界使用虚拟节点，我们消除了所有边缘情况，因为在我们的操作点之前和之后总是有一个节点。

心智笔记：链表的天才之处在于其基于指针的连接。每个节点只知道其直接邻居，创建一个链条。这种局部知识意味着我们可以通过更新几个指针来插入或删除节点 - 不需要移动元素。虚拟节点模式确保我们永远不会处理空的头/尾，使每个操作都是统一的。

决策框架

在每个链表操作中，决策都是关于指针操作的：

• 插入：更新指针以将新节点编织到链中
• 删除：更新指针以绕过目标节点
• 遍历：一次跟随链条一个节点
• 边缘情况消除：使用虚拟节点确保统一操作

代码

带虚拟节点的单向链表

// 列表中的每个元素都是一个带有值和指向下一个的指针的"节点"
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // 指向链中的下一个节点
  }
}

class LinkedList {
  constructor() {
    // 虚拟头充当永久的"开始"标记
    this.dummyHead = new ListNode("START");
    this.tail = this.dummyHead; // 尾部跟踪最后一个节点
  }

  // push：添加到末尾（像array.push）
  push(value) {
    const newNode = new ListNode(value);

    // 决策框架：简单地连接到尾部
    this.tail.next = newNode; // 当前最后一个节点指向新节点
    this.tail = newNode; // 将尾部更新为新的最后一个节点
  }

  // pop：从末尾删除（像array.pop）
  pop() {
    // 决策框架：检查列表是否为空
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // 找到倒数第二个节点
    let current = this.dummyHead;
    while (current.next !== this.tail) {
      current = current.next;
    }

    // 保存要返回的值
    const poppedValue = this.tail.value;

    // 删除最后一个节点
    current.next = null;
    this.tail = current;

    return poppedValue;
  }

  // unshift：添加到前面（像array.unshift）
  unshift(value) {
    const newNode = new ListNode(value);

    // 决策框架：在虚拟节点之后立即插入
    const oldFirst = this.dummyHead.next;
    newNode.next = oldFirst; // 新节点指向旧的第一个
    this.dummyHead.next = newNode; // 虚拟节点指向新节点

    // 如果列表为空，更新尾部
    if (this.tail === this.dummyHead) {
      this.tail = newNode;
    }
  }

  // shift：从前面删除（像array.shift）
  shift() {
    // 决策框架：检查列表是否为空
    if (this.dummyHead.next === null) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const shiftedValue = firstNode.value;

    // 绕过第一个节点
    this.dummyHead.next = firstNode.next;

    // 如果我们删除了唯一的节点，重置尾部
    if (firstNode === this.tail) {
      this.tail = this.dummyHead;
    }

    return shiftedValue;
  }

  // 辅助：查看列表中有什么
  display() {
    const items = [];
    let current = this.dummyHead.next; // 跳过虚拟节点

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// 示例：管理待办事项列表
const todos = new LinkedList();

// 在末尾添加任务
todos.push("买牛奶");
todos.push("写代码");
todos.push("锻炼");
console.log(todos.display()); // 买牛奶 → 写代码 → 锻炼

// 在前面添加紧急任务
todos.unshift("给妈妈打电话");
console.log(todos.display()); // 给妈妈打电话 → 买牛奶 → 写代码 → 锻炼

// 完成第一个任务
const completed = todos.shift();
console.log(`已完成：${completed}`); // 已完成：给妈妈打电话
console.log(todos.display()); // 买牛奶 → 写代码 → 锻炼

// 删除最后一个任务
const removed = todos.pop();
console.log(`已删除：${removed}`); // 已删除：锻炼
console.log(todos.display()); // 买牛奶 → 写代码

带双虚拟节点的双向链表

// 每个节点都有指向下一个和上一个节点的指针
class DoublyListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // 向前指
    this.prev = null; // 向后指
  }
}

class DoublyLinkedList {
  constructor() {
    // 两个虚拟节点充当永久的"书签"
    this.dummyHead = new DoublyListNode("START");
    this.dummyTail = new DoublyListNode("END");

    // 将书签相互连接
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  // push：添加到末尾（像array.push）
  push(value) {
    const newNode = new DoublyListNode(value);

    // 决策框架：在最后一个真实节点和dummyTail之间插入
    const lastNode = this.dummyTail.prev;

    // 连接所有4个连接
    newNode.prev = lastNode; // 新节点向后指向最后一个
    newNode.next = this.dummyTail; // 新节点向前指向虚拟尾部
    lastNode.next = newNode; // 最后一个节点向前指向新节点
    this.dummyTail.prev = newNode; // 虚拟尾部向后指向新节点

    return this; // 用于链式调用
  }

  // pop：从末尾删除（像array.pop）
  pop() {
    // 决策框架：检查列表是否为空
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const lastNode = this.dummyTail.prev;
    const secondToLast = lastNode.prev;
    const poppedValue = lastNode.value;

    // 绕过最后一个节点
    secondToLast.next = this.dummyTail;
    this.dummyTail.prev = secondToLast;

    return poppedValue;
  }

  // unshift：添加到前面（像array.unshift）
  unshift(value) {
    const newNode = new DoublyListNode(value);

    // 决策框架：在dummyHead和第一个真实节点之间插入
    const firstNode = this.dummyHead.next;

    // 连接所有4个连接
    newNode.prev = this.dummyHead; // 新节点向后指向虚拟头部
    newNode.next = firstNode; // 新节点向前指向第一个
    this.dummyHead.next = newNode; // 虚拟头部向前指向新节点
    firstNode.prev = newNode; // 第一个节点向后指向新节点

    return this; // 用于链式调用
  }

  // shift：从前面删除（像array.shift）
  shift() {
    // 决策框架：检查列表是否为空
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const secondNode = firstNode.next;
    const shiftedValue = firstNode.value;

    // 绕过第一个节点
    this.dummyHead.next = secondNode;
    secondNode.prev = this.dummyHead;

    return shiftedValue;
  }

  // 辅助：查看列表中有什么
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== this.dummyTail) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" ⟷ ");
  }

  // 奖励：向后导航
  displayReverse() {
    const items = [];
    let current = this.dummyTail.prev;

    while (current !== this.dummyHead) {
      items.push(current.value);
      current = current.prev;
    }

    return items.join(" ⟷ ");
  }
}

// 示例：带下一个/上一个的音乐播放列表
const playlist = new DoublyLinkedList();

// 添加歌曲
playlist.push("歌曲 A");
playlist.push("歌曲 B");
playlist.push("歌曲 C");
console.log(playlist.display()); // 歌曲 A ⟷ 歌曲 B ⟷ 歌曲 C

// 在开头添加歌曲
playlist.unshift("开场歌曲");
console.log(playlist.display()); // 开场歌曲 ⟷ 歌曲 A ⟷ 歌曲 B ⟷ 歌曲 C

// 反向播放
console.log("反向:", playlist.displayReverse()); // 歌曲 C ⟷ 歌曲 B ⟷ 歌曲 A ⟷ 开场歌曲

// 跳过第一首歌
const skipped = playlist.shift();
console.log(`已跳过：${skipped}`); // 已跳过：开场歌曲

// 删除最后一首歌
const removed = playlist.pop();
console.log(`已删除：${removed}`); // 已删除：歌曲 C

console.log(playlist.display()); // 歌曲 A ⟷ 歌曲 B

疑惑消除

常见疑惑："当数组看起来更简单时，为什么要使用链表？数组可以用索引直接访问任何元素！"

这是关于选择正确数据结构的基本问题。让我们检查一下权衡。

为什么你可能认为数组总是更好

考虑这些数组优势：

• "数组提供索引的O(1)随机访问"
• "数组具有更好的缓存局部性（元素连续存储）"
• "不需要额外的内存用于指针"
• "更简单的心智模型 - 只是一个连续块"

为什么这种想法错过了关键场景

关键认识：数组在插入和删除时有隐藏成本！

让我们追踪在数组中间插入时会发生什么：

数组：[A, B, C, D, E]
在索引2处插入X：

步骤1：通过向右移动所有内容来腾出空间
[A, B, _, C, D, E]  // C移动到索引3
[A, B, _, _, D, E]  // D移动到索引4
[A, B, _, _, _, E]  // E移动到索引5

步骤2：插入X
[A, B, X, C, D, E]

总操作：平均n/2次移动 = O(n)

具体示例：性能比较

在前面插入1000个元素：

数组方法：

• 第一次插入：移动0个元素
• 第二次插入：移动1个元素
• 第三次插入：移动2个元素
• ...
• 第1000次插入：移动999个元素
• 总移动：0 + 1 + 2 + ... + 999 = 499,500次操作！

链表方法：

• 每次插入：更新2个指针
• 总操作：1000 × 2 = 2,000次操作

链表减少了250倍的操作！

每种结构发光的时候

使用数组时：

• 需要随机访问（直接访问arr[500]）
• 数据大小相对固定
• 主要读取数据
• 缓存性能很重要

使用链表时：

• 在已知位置频繁插入/删除
• 数据大小变化很大
• 仅顺序遍历
• 内存碎片化（链表可以使用分散的内存）

为什么虚拟节点很天才

没有虚拟节点，每个操作都必须检查：

• "这是第一个节点吗？"（头部的特殊情况）
• "这是最后一个节点吗？"（尾部的特殊情况）
• "列表是空的吗？"（到处都有空检查）

有了虚拟节点：

• 目标之前总是有一个节点（dummyHead）
• 目标之后总是有一个节点（双向链表中的dummyTail）
• 空列表仍然有虚拟结构
• 每个操作都使用相同的模式 - 没有特殊情况！

保证：虚拟节点将充满边缘情况的数据结构转换为具有统一操作的结构。这不仅仅是方便 - 这是通过消除空指针错误和特殊情况处理的可能性来编写无错误代码。