登录从零到一打造 Vue3 响应式系统 Day 5 - 核心概念：单向链表、双向链表
在昨天，我们建立了响应式的基本运作模式。在继续深入之前，要先了解 Vue 内部用来优化性能的一个核心概念：数据结构。Vue 3 的响应式系统之所以效率高，其内部对数据结构的选择是关键。
一个理想的数据结构需要能有效处理以下操作：
- 动态关联：effect 与数据之间的依赖关系是能动态建立与解除的。
- 快速增删：当依赖关系变化时，需要快速地执行新增或移除操作。
为了满足这些高性能要求，Vue 选择了链表 (Linked List) 作为解决方案。本文将深入探讨其运作原理。
单向链表
- 类型是对象
- 第一个节点是头节点、最后一个节点称为尾节点
- 所有节点都通过
next属性连接起来。
// 头节点是 head
let head = { value: 1, next: undefined }
const node2 = { value: 2, next: undefined }
const node3 = { value: 3, next: undefined }
const node4 = { value: 4, next: undefined }
// 建立链表之间的关系
head.next = node2
node2.next = node3
node3.next = node4
删除中间节点
假设我们要删除 node3，但在单向链表中，仅凭 node3 本身的引用是无法直接进行操作的，因为我们无法访问到它的前一个节点 (node2) 。因此，我们必须从头节点 (head) 开始遍历，直到找到 node2 为止：
const node3 = { value: 3, next: undefined }
let current = head
while (current) {
// 找到 node3 的上一个节点
if (current.next === node3) {
// 把 node3 的上一个节点指向 node3 的下一个节点
current.next = node3.next
break
}
current = current.next
}
console.log(head) // 输出新的链表 1->2->4
双向链表
-
每个节点都有：
-
value: 存储的值 -
next: 指向下一个节点 -
prev: 指向上一个节点
-
-
双向链表中，通常头节点没有
prev，尾节点没有next。
它最大的优势在于，从任何一个节点出发，都能够双向遍历，这使得在特定节点前后进行新增或删除操作都非常快速。
// 假设链表的头节点是 head
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 node4 = { value: 4, next: undefined, prev: undefined }
// 建立链表之间的关系
head.next = node2
// node2 的上一个节点指向 head
node2.prev = head
// node2 的下一个节点指向 node3
node2.next = node3
// node3 的上一个节点指向 node2
node3.prev = node2
// node3 的下一个节点指向 node4
node3.next = node4
// node4 的上一个节点指向 node3
node4.prev = node3
删除中间节点
假设我们现在手上有中间节点 node3 要删除，该怎么做：
const node3 = { value: 3, next: undefined, prev: undefined }
// 如果 node3 有上一个节点，就把上一个节点的 next 指向 node3 的下一个节点
if (node3.prev) {
node3.prev.next = node3.next
} else {
// 如果 node3 没有上一个节点，说明它是头节点
head = node3.next
}
// 如果 node3 有下一个节点，就把下一个节点的 prev 指向 node3 的上一个节点
if (node3.next) {
node3.next.prev = node3.prev
}
console.log(head) // 输出新的链表 1->2->4
可以看到，在已知目标节点的前提下，执行删除操作完全不需要从头遍历，时间复杂度为 O(1)。
单向链表与双向链表比较
现在我们要在 C 节点之前新增一个 X 节点。
单向链表
- 时间复杂度：O(n)
- 原因：需要遍历才能找到前一个节点。
执行步骤
步骤 1：从头节点开始遍历查找。
步骤 2：检查节点 A，不是目标节点的前一个，继续遍历。
步骤 3：找到目标节点 C 的前一个节点 B（因为 B 的 next 属性是 C）。
步骤 4：创建新节点 X。
步骤 5：设置 X.next = C。
步骤 6：设置 B.next = X。
双向链表
- 时间复杂度：O(1)
-
原因：直接通过
prev指针访问前一个节点。
执行步骤
步骤 1：直接通过目标节点的 prev 指针找到前一个节点 B。
步骤 2：创建新节点 X。
步骤 3：设置 X.next = C, X.prev = B。
步骤 4：设置 B.next = X, C.prev = X。
我们可以发现：
- 单向链表：结构简单，适合只需要向前遍历的场景。
- 双向链表：更灵活但占用更多内存，适合需要双向操作的场景。
到目前为止，我们已经了解了链表的原理。然而在许多可以用来存储数据集合的结构中，为什么 Vue 的响应式系统会选择链表，而不是我们更常用的数组 (Array) 呢？
链表与数组的比较
特性
数组 (Array) 最大的优点是读取性能极佳。由于内存空间是连续的，我们可以通过索引 [i] 直接定位到任何元素，时间复杂度为 O(1)。
const arr = ['a', 'b', 'c', 'd'] // a=>0 b=>1 c=>2 d=>3
// 删除数组的第一项
arr.shift()
console.log(arr) // ['b', 'c', 'd'] b=>0 c=>1 d=>2
链表：新增、删除元素更快 (O(1))，但查找元素需要遍历整个链表（O(n)）。
// 头节点是 head
let head = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
}
// 删除链表第一个节点
head = head.next // 将头节点指向下一个节点 node2
console.log(head)
// 输出新的头节点 [2, 3, 4]
删除头、尾项
数组
- 新增操作（如
unshift）需要移动后续所有元素，可能导致性能下降（O(n)）。 - 删除操作（如
shift）同样需要移动后续所有元素，性能也为（O(n)）。
链表
- 新增操作只需修改指针，性能为 O(1)。
- 删除操作也只需修改指针，性能为 O(1)。
总的来说，虽然双向链表在内存占用上略高于单向链表，但它提供的 O(1) 复杂度的新增与删除方法，对于需要频繁操作依赖集合的响应式系统来说，是非常重要的。
我们理解了链表的运作原理后，明天我们会继续在 ref 的实现中，结合今天学到的链表知识来改造响应式系统。
想了解更多 Vue 的相关知识，抖音、B站搜索我师父「远方os」，一起跟日安当同学。
