Day 5 - 核心概念：單向鏈表、雙向鏈表

在昨天，我們建立了響應式的基本運作模式。在繼續深入之前，要先了解 Vue 內部用來優化效能的一個核心概念：資料結構。Vue 3 的響應式系統之所以效率高，內部對資料結構的選擇是關鍵。

一個理想的資料結構需要能有效處理以下操作：

動態關聯： effect 與資料之間的依賴關係是能動態建立與解除。
快速增刪：當依賴關係變化時，需要快速地執行新增或移除操作。

為了滿足這些高效能要求，Vue 選擇了鏈表 (Linked List) 作為解決方案。本文將深入探討其運作原理。

單向鏈表

型別是物件
第一個節點是頭節點、最後一個節點稱為尾節點
所有節點都透過 next 屬性連結起來。

1
// 頭節點是 head
2
let head = { value: 1, next: undefined }
3
const node2 = { value: 2, next: undefined }
4
const node3 = { value: 3, next: undefined }
5
const node4 = { value: 4, next: undefined }
6

7
// 建立鏈表之間的關系
8
head.next = node2
9
node2.next = node3
10
node3.next = node4

刪除中間節點

假設我們要刪除 node3，但在單向鏈表中，只有 node3 本身的參考是無法直接進行操作，因為我們無法存取到它的前一個節點 (node2)。因此，我們必須從頭節點 (head) 開始遍歷，直到找到 node2 為止：

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

3
let current = head
4
while (current) {
5
  // 找到 node3 的上一個節點
6
  if (current.next === node3) {
7
    // 把 node3 的上一個指向 node3 的下一個
8
    current.next = node3.next
9
    break
10
  }
11
  current = current.next
12
}
13

14
console.log(head) // 輸出新的鏈表 1->2->4

雙向鏈表

每個節點都有：
- value: 儲存的值
- next: 指向下一個節點
- prev: 指向上一個節點
雙向鏈表，沒有尾節點就沒有頭節點。

它最大的優勢在於，從任何一個節點出發，都能夠雙向遍歷，這在特定節點前後進行新增或刪除都能非常快速。

1
// 假設鏈表的頭節點是 head
2

3
let head = { value: 1, next: undefined, prev: undefined }
4

5
const node2 = { value: 2, next: undefined, prev: undefined }
6

7
const node3 = { value: 3, next: undefined, prev: undefined }
8

9
const node4 = { value: 4, next: undefined, prev: undefined }
10

11
// 建立鏈表之間的關系
12
head.next = node2
13
// node2 的上一個節點指向 head
14
node2.prev = head
15
// node2 的下一個指向 node3
7 collapsed lines
16
node2.next = node3
17
// node3 的上一個節點指向 node2
18
node3.prev = node2
19
// node3 的下一個指向 node4
20
node3.next = node4
21
// node4 的上一個指向 node3
22
node4.prev = node3

刪除中間節點

假設我們現在手上有中間節點 node3要刪除，該怎麼做：

1
const node3 = { value: 3, next: undefined, prev: undefined }
2

3
// 如果 node3 有上一個，那就把上一個節點的下一個指向 node3 的下一個
4
if (node3.prev) {
5
  node3.prev.next = node3.next
6
} else {
7
  head = node3.next
8
}
9

10
if (node3.next) {
11
  node3.next.prev = node3.prev
12
}
13
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 指針找到前一個節點

步驟 2：建立新節點 X

步驟 3：設定 X.next = C, X.prev = B

步驟 4：設定 B.next = X, C.prev = X

我們可以發現：

單向鏈表：結構簡單，適合只需要向前遍歷的場景。
雙向鏈表：更靈活但佔用更多記憶體，適合需要雙向操作的場景。

到目前為止，我們已經了解了鏈表的原理。然而在許多可以用來儲存資料集合的結構中，為什麼 Vue 的響應式系統會選擇鏈表，而不是我們更常用的陣列 (Array) 呢？

鏈表與陣列的比較

特性

陣列 (Array) 最大的優點是讀取效能極佳。由於內存空間是連續的，我們可以透過索引 [i] 直接定位到任何元素，時間複雜度為 O(1)。

1
const arr = ['a', 'b', 'c', 'd'] // a=>0  b=>1  c=>2  d=>3
2

3
// 刪除陣列的第一項
4
arr.shift()
5

6
console.log(arr) // ['b', 'c', 'd'] b=>0  c=>1  d=>2

鏈表：新增、刪除元素更快 (O(1))，但查找元素需要遍歷整個鏈表（O（n））。

1
// 頭節點是 head
2
let head = {
3
  value: 1,
4
  next: {
5
    value: 2,
6
    next: {
7
      value: 3,
8
      next: {
9
        value: 4,
10
        next: null
11
      }
12
    }
13
  }
14
}
15
// 刪除鏈表第一個節點
3 collapsed lines
16
head = head.next // 將頭節點指向下一個節點 node2
17
console.log (head)
18
// 輸出新的頭節點［2, 3， 4］

刪除頭、尾項

陣列

新增操作需要移動後續元素，可能導致效能下降（O(n)）。
刪除操作同樣需要移動後續元素，效能也為（O(n））。

鏈表

新增操作只需修改指針，性能為（O(1)）。
刪除操作也只需修改指針，性能為（O(1)）。

總結來說，雖然雙向鏈表在記憶體佔用上略高於單向鏈表，但它可以提供的 O(1) 複雜度的新增與刪除方法，這對於需要頻繁操作依賴集合的響應式系統來說，是非常重要的。我們理解了鏈表的運作原理後，明天我們會繼續ref的實作中，結合我們今天學到的鏈表知識來改造響應式系統。