前文梳理了响应式的工作模式。要继续深入，需要先了解 Vue 在性能优化中的关键：选择合适的「数据结构」。

Vue 3 的高效，本质上离不开对数据结构的合理取舍与约束。

一个理想的数据结构需要满足：

• 动态关联：effect 与数据之间的依赖关系能动态建立与解除。
• 快速增删：当依赖关系变化时，能快速完成新增/删除。

为满足上述诉求，Vue 选择了链表（Linked List）作为核心手段之一。

什么是链表

链表是一种线性数据结构，由一系列节点（Node）组成。每个节点存储数据，并指向下一个节点。它与数组同为线性结构，但在增删方面具有明显不同的性能特征。

数组 vs 链表（复杂度对比）

操作	数组	链表
访问	O(1)（按索引）	O(n)（需遍历）
头部插入	O(n)	O(1)
头部删除	O(n)	O(1)
中部插入	O(n)	O(1)（已在节点处）
中部删除	O(n)	O(1)（已在节点处）
尾部插入	均摊 O(1)	O(1)/O(n) 视实现

链表在“已定位到目标节点”的前提下，中部插入/删除为 O(1)；定位本身通常为 O(n)。

单向链表（Singly Linked List）

特征：

• 第一个节点是头节点（head）
• 节点通过 next 指向后继节点
• 最后一个节点尾部的 next 为 undefined（或 null）

let head = {value: 1, next: undefined}
const node2 = {value: 2, next: undefined}
const node3 = {value: 3, next: undefined}

head.next = node2
node2.next = node3

与数组的直观对比（以“删除首元素”为例）

数组：

const arr = ['a', 'b', 'c'] // a->0, b->1, c->2
arr.shift()
console.log(arr) // ['b', 'c']，元素整体前移，索引重排

链表：

let head = {value: 1, next: undefined}
const node2 = {value: 2, next: undefined}
const node3 = {value: 3, next: undefined}

head.next = node2
node2.next = node3

head = head.next // 删除首节点，仅修改指针


// --------删除中间节点如 node2------------
let current = head
while (current) {
  if (current.next === node3) {
    current.next = node3.next
    break
  }
  current = current.next
}

删除首元素时，数组需要移动后续元素（O(n)）；链表只需修改指针（O(1)）。

---

双向链表（Doubly Linked List）

在单向链表中，无法在已知节点的“前面”进行 O(1) 插入，通常需要从头遍历到它的前节点，时间复杂度较高。为此，可以使用“双向链表”。

let head = {value: 1, next: undefined, prev: undefined}
const node2 = {value: 2, next: undefined, prev: undefined}
const node3 = {value: 3, next: undefined, prev: undefined}
const node5 = {value: 5, next: undefined, prev: undefined}

// 建立 1 <-> 2 <-> 3
head.next = node2
node2.prev = head
node2.next = node3
node3.prev = node2

// --------删除中间节点如 node2------------
if (node2.prev) { // 如果有前节点
  node2.prev.next = node2.next // 将前一个节点的下个节点指向node2的下个节点 也就是将 1 的 next 指向 3
} else {
  head = node2.next // 说明是头节点，更换头节点为下个节点
}

if (node2.next) { // 如果后续还有下个节点
  node2.next.prev = node2.prev // 将上个节点的下个节点指向node2的下个节点 也就是将 3 的 prev 指向 1
}

这样增、删更高效，

---