链表在响应式系统中的应用

前文我们梳理了响应式的工作模式。要继续深入，我们需要探究 Vue 3 在实现卓越性能时所依赖的关键基石：对核心数据结构的选择与约束。

💡 性能基石: Vue 3 的高效依赖追踪，很大程度上归功于对链表这种数据结构的巧妙应用。

🎯 响应式系统对数据结构的要求

一个高效的依赖追踪系统（Dep）需要满足极高的性能标准，尤其是在管理 effect 与数据之间的依赖关系时：

需求	目的	性能目标
动态关联	`effect` 与数据间的依赖关系需要能灵活地建立 (`track`) 与解除 (`cleanup`)。	高度灵活的引用机制。
高效增删	当依赖关系变化时，必须能以最快速度完成新增或删除操作。	O(1) 复杂度
内存友好	在大型组件和应用中，要保证较低的内存占用。	简洁的节点结构。

为了满足高效增删的 O(1) 需求，Vue 选择了链表作为管理 effect 依赖集合的核心数据结构。

什么是链表？核心优势解析

链表是一种由节点（Node）通过引用连接而成的线性数据结构。它与数组最大的不同在于：物理存储位置不连续，靠指针串联逻辑顺序。

数组 vs 链表：操作性能对比

操作	数组(Array)	链表 (Linked List)	链表优势
随机访问	O(1) (通过索引)	O(n) (需从头遍历)	数组胜：适合查找
头部插入/删除	O(n) (需移动所有元素)	O(1) (仅修改指针)	链表胜：无需移动数据
中部插入/删除	O(n) (需移动后续元素)	O(1) (已知节点时)	链表胜：无需移动数据
尾部插入	均摊 O(1)	,O(1) (维护尾指针时)

🚀 在响应式系统中，依赖关系（effect）需要频繁地被添加和移除（例如，组件卸载或条件渲染），链表的 O(1) 增删特性完美匹配了这一高频操作的需求。

单向链表（Singly Linked List）

基本特征

每个节点只包含两个部分：数据 (value) 和一个指向下一节点的 next 引用。
遍历只能从头节点（head）开始，单向前进。

// 节点结构示意
const head = { value: 1, next: undefined }
const node2 = { value: 2, next: undefined }
const node3 = { value: 3, next: undefined }

// 建立链接: 1 -> 2 -> 3
head.next = node2
node2.next = node3

单向链表结构示意图

示例对比：删除首元素

数据结构	操作步骤	性能复杂度
数组	`arr.shift()`：需要将后续所有元素向前移动，并重新分配索引。	O(n)
链表	`head = head.next`：只需一步操作，将头指针指向第二个节点。	O(1)

链表删除中间节点 (O(1) 优化前提)

// 假设我们要删除 node2，且已知 head 是它的前驱
head.next = node2.next // 将 head 的 next 直接指向 node3
// node2 即被从链表中移除

这种操作仅仅修改了两个指针，效率极高。

双向链表（Doubly Linked List）

单向链表在处理“已知当前节点，想访问它的前驱节点”时，必须从头遍历。为了解决这个局限性，双向链表被引入。

双向链表结构示意图

结构升级

每个节点包含三个引用：
- value (数据)
- next (指向后继节点)
- prev (指向前驱节点)

// 建立双向链接 1 <-> 2 <-> 3
const head = { value: 1, next: node2, prev: undefined }
const node3 = { value: 3, next: undefined, prev: node2 }
const node2 = { value: 2, next: node3, prev: head }

关键优势：高效删除任意节点

双向链表的 prev 指针使得删除操作更加健壮和高效，即便在不确定前驱节点的情况下：

// 删除中间节点 node2，只需修改 node2 前后节点的指针
const prevNode = node2.prev // 获取前驱节点
const nextNode = node2.next // 获取后继节点

// 1. 修改前驱节点的 next 指针
if (prevNode) {
  prevNode.next = nextNode
}
else {
  // 如果 prevNode 不存在，说明 node2 是头节点
  head = nextNode
}

// 2. 修改后继节点的 prev 指针
if (nextNode) {
  nextNode.prev = prevNode
}
// node2 即被彻底从链表中移除