在昨天，我們建立了響應式的基本運作模式。在繼續深入之前，要先了解 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: 指向上一個節點
• 雙向鏈表，沒有尾節點就沒有頭節點。

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

// 假設鏈表的頭節點是 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 有上一個，那就把上一個節點的下一個指向 node3 的下一個
if (node3.prev) {
  node3.prev.next = node3.next
} else {
  head = node3.next
}

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 指針找到前一個節點

步驟 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］

刪除頭、尾項

陣列

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

鏈表

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

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

同步更新《嘿，日安！》技術部落格