【譯】2019年JavaScript中的電腦科學：連結串列
早在2009年，我就挑戰自己一年內堅持每週寫一篇部落格文章。我曾經讀到過，堅持發表文章是為部落格帶來流量的最好的方法。基於我的所有文章的理念，一週發表一篇文章看起來是一個很實際的目標，而事實上我缺少了部落格文章的52個理念。（譯者注：不太清楚這裡的意思，查閱到 52 Ideas For Blog Posts 這篇文章比較符合語境）我挖掘了一些寫到一半的章節，並最終編撰了 JavaScript 高階程式設計 ，在其中發掘了很多關於經典電腦科學的材料，包括資料結構與演算法。我將這些材料在2009年及2012年加工成為了幾篇文章，並從其中得到了許多積極的反饋。
在這些文章釋出的十週年之際，我決定在2019年使用 JavaScript 更新、拓展並重新發表它們。去看看其中哪些內容變了，哪些沒有變也不失為一種樂趣，希望大家喜歡。
什麼是連結串列？
連結串列是一種使用線性的方式來儲存不同的值的資料結構。連結串列中的每個值都包含於自己的節點中，且這個節點包含了其指向連結串列中下一個節點的連結資料。這個連結為指向另一個節點物件的指標，如果沒有下一個節點，則為 null 。如果連結串列中每個節點只有一個指向另一個節點的指標（常見的為指向下一個節點），那麼這種連結串列稱作為 單鏈表（或就稱為連結串列） ；而如果連結串列中每個節點有兩個指標（常見的為指向上一個節點和下一個節點），通常我們稱之為雙向連結串列。本文中，我將主要探討單鏈表。
為什麼要使用單鏈表？
連結串列最主要的優點就是它可以儲存任意數量的值，同時只佔用這些值所需的記憶體大小。對於記憶體小的舊電腦來說，充分利用記憶體空間還是很重要的。相反，在 C 語言中的內建陣列型別要求你指定陣列的長度（有多少項），然後根據陣列長度來分配記憶體。預留記憶體空間意味著這部分記憶體不能用於執行任何其他程式，即使這部分記憶體從未被使用。你可以很輕鬆在一臺記憶體小的機器上使用陣列來耗盡記憶體；而連結串列就是用於解決這個問題的。
雖然最初的目的是為了更好的記憶體管理，但是當開發人員無法預估一個數組最終會包含多少項時，連結串列也就變得更受歡迎。使用連結串列來根據需要新增資料要比精準地猜測陣列可能包含的最多數量的項要簡單得多。因此，連結串列在各種程式語言中也作為一種基礎的內建資料結構。
連結串列的設計
連結串列最重要的部分就是它的節點的資料結構。每一個節點都必須包含一個指向連結串列中下一個節點的指標和一些資料。如下為 JavaScript 中簡單的表示：
class LinkedListNode {
constructor (data) {
this.data = data;
this.next = null;
}
}
複製程式碼
在 LinkedListNode 類中， data 屬性包含了此節點應儲存的值， next 屬性為指向連結串列中下一個節點的指標。 next 的初始值應該為 null ，因為你暫時無法知道此節點在連結串列中的下一個節點是什麼。你可以像下面的例子一樣使用 LinkedListNode 來建立一個連結串列：
// 建立第一個節點 const head = new LinkedListNode(12); // 新增第二個節點 head.next = new LinkedListNode(99); // 新增第三個節點 head.next.next = new LinkedListNode(37); 複製程式碼
第一個節點我們一般稱為 頭 ，因此 head 識別符號在此例子中表示連結串列中的第一個節點。建立第二個節點並將 head.next 賦值於第二個節點，這樣連結串列中就有了兩個節點。通過給 head.next.next 賦值一個新節點來建立第三個節點，其中 head.next.next 為第二個節點中指向下一個節點的指標。第三個節點的 next 指標在連結串列中保持為 null 。下圖展示了最終的資料結構：
我們可以通過連結串列每個節點中的 next 指標來遍歷所有資料。如下就是一個簡單的遍歷連結串列資料並列印每個節點的值的例子：
let current = head;
while (current !== null) {
console.log(current.data);
current = current.next;
}
複製程式碼
上述程式碼使用 current 來作為連結串列中移動的指標，它的初始值為連結串列的 頭 即 head ， while 迴圈的條件為當 current 不為 null 。在迴圈內部， current 對應的節點所儲存的值將會被打印出來，接著 current 的 next 指標將往前移動，即 current 將被賦值為 current.next 所指向的節點。
大部分的連結串列操作都是使用這種遍歷演算法或其他類似的演算法，因此瞭解這種演算法對於理解連結串列一般來說非常重要。
LinkedList 類
如果你曾使用 C 寫過連結串列，你可能會在這一步就停下來，認為自己的任務已經完成了（儘管你將會用 struct 而不是類來表示每個節點）。然而，在面向物件的語言中，譬如 JavaScript，更多的是建立一個類來封裝這個功能。如下就是一個簡單的例子：
const head = Symbol("head");
class LinkedList {
constructor() {
this[head] = null;
}
}
複製程式碼
LinkedList 類表示為包含了連結串列中的節點之間互動的方法的連結串列類。其唯一的屬性 head 為使用 symbol 定義的變數，並指向連結串列中的第一個節點。使用 symbol 資料型別而不用 string 來定義此屬性就是為了明確地表明並不想要此屬性在此類外進行修改。
給連結串列新增新資料
在連結串列中新增新資料需要遍歷連結串列找到正確的位置，然後建立新的節點，最後插到正確的位置。這裡有個特殊的例子就是，當連結串列為空時，也就是你只需要新建一個節點然後賦予 head 即可：
const head = Symbol("head")
class LinkedList {
constructor() {
this[head] = null;
}
add(data) {
// 新建一個節點
const newNode = new LinkedListNode(data);
// 特殊情況：連結串列中無節點
if (this[head] === null) {
// 只需要將新建的節點賦予 `head`
this[head] = newNode;
} else {
// 從第一個節點開始尋找
let current = this[head];
// 跟隨 `next` 連結直到到連結串列的尾部
while (current.next !== null) {
current = current.next;
}
// 將新建的節點賦予 `next` 指標
current.next = newNode;
}
}
}
複製程式碼
add() 方法接收單個引數，可以為任何資料，然後將它新增到連結串列的尾部。如果連結串列為空（ this[head] 為 null ），你只需要將新建的節點 newNode 賦予給 this[head] 即可。如果連結串列不為空，那麼你需要遍歷連結串列中已有的節點，找打最後一個節點。這個遍歷的過程開始於 this[head] 並跟隨每個節點的 next 連結，直到找到最後一個節點。最後一個節點的 next 指標指向 null ，因此在這個節點停止遍歷非常重要，而不是當 current 為 null 時停止（如上一節所述）。然後你可以將新建的節點賦予其 next 屬性，以此來將資料新增到連結串列中。
注意
傳統的演算法使用了兩個指標 current 與 previous ， current 指向當前節點， previous 指向 current 的上一個節點。當 current 為 null 時，意味著 previous 指向了連結串列中的最後一項。我認為當你可以檢查 current.next 的值並在其為 null 時退出迴圈時還要使用這種方法並不合乎邏輯。
add() 方法的演算法時間複雜度為 O(n) ，因為你必須遍歷整個連結串列來找到正確的位置來插入新的節點。你可以通過從連結串列尾部開始遍歷（除去頭部之外）來將時間複雜度降低為 O(1) ，這樣你可以立即將新節點插入到正確的位置。
檢索連結串列中的資料
連結串列不允許隨機訪問其資料，但你仍然可以通過遍歷連結串列並返回資料來檢索任何給定位置的資料。為此，你需要新增一個 get() 方法，它接受一個從零開始的索引作為引數來檢索資料，如下所示：
class LinkedList {
// 為了簡潔，先隱藏之前新增的方法
get(index) {
// 確保 `index` 為非負整數
if (index > -1) {
// 用於遍歷的指標
let current = this[head];
// 用於跟蹤連結串列中的位置
let i = 0;
// 遍歷連結串列直到找到 `index` 索引或到達連結串列尾部
while ((current !== null) && (i < index)) {
current = current.next;
i++;
}
// 如果 `current` 不為 `null`，返回對應的資料
return current !== null ? current.data : undefined;
} else {
return undefined;
}
}
}
複製程式碼
get() 方法首先先確保 index 為非負數，否則返回 undefined 。變數 i 是用於跟蹤遍歷連結串列的深度；其中的迴圈就像你之前看到的基本遍歷一樣，只不過是多了一個條件：當 i 等於 index 時應該退出迴圈；這也就意味著要考慮如下兩種退出迴圈的情況：
-
current為null，意味著連結串列實際長度小於index -
i等於index，意味著current就是index索引所在的節點
如果 current 為 null ，那麼就返回 undefined ；反之返回 current.data 。這個檢查確保了 get() 將不會在連結串列中找不到索引時丟擲錯誤（儘管或許你會用丟擲錯誤而不是返回 undefined ）。
get() 方法的演算法時間複雜度範圍從刪除第一個節點的 O(1) （不需要遍歷）到刪除最後一個節點的 O(n) （需要遍歷整個連結串列）。我們很難再去減小其演算法時間複雜度，因為總需要檢索來檢查正確的返回值。
從連結串列中移除資料
從連結串列中移除資料會有點棘手，因為你要確保在移除節點後，所有節點的 next 指標都保持有效。譬如，如果你想要在一個有三個節點的連結串列中移除第二個節點，你需要確保第一個節點的 next 指標指向第三個節點，而不再是第二個節點。以這種方式來跳過第二個節點可以很有效地從連結串列中移除第二個節點。
移除的操作其實就兩個步驟：
get()
尋找這個特定的索引就和 get() 方法一樣，但在迴圈內部你還需要追蹤 current 的上一個節點，因為你需要修改上一個節點的 next 指標。
同時你還需要考慮以下四種特殊情況：
head
在前三個特殊情況中，是無法完成移除操作，因此丟擲錯誤也就很合理了。第四個特殊情況要求重新對 this[head] 進行賦值。如下是 remove() 方法的相關實現：
class LinkedList {
// 為了簡潔，先隱藏之前新增的方法
remove(index) {
// 特殊情況：空連結串列或非法 `index`
if ((this[head] === null) || (index < 0)) {
throw new RangeError(`index ${index} does not exist in the list.`)
}
// 特殊情況：移除第一個節點
if (index === 0) {
// 臨時儲存節點資料
const data = this[head].data;
// 用下一個節點（第二個節點）來替換連結串列的 head
this[head] = this[head].next
// 返回連結串列原來的 head 的資料
return data;
}
// 用於遍歷連結串列的指標
let current = this[head];
// 追蹤迴圈中 current 的上一個節點
let previous = null;
// 用於追蹤連結串列中的位置
let i = 0;
// 與 `get()` 相同的迴圈演算法
while ((current !== null) && (i < index)) {
// 儲存 current 的值
previous = current;
// 遍歷到下一個節點
current = current.next;
// 增加次數
i++;
}
// 如果找到要移除的節點則移除它
if (current !== null) {
// 通過跳過此節點（即不再連結此節點）來移除它
previous.next = current.next;
// 返回剛才被移除的節點的值
return current.data;
}
// 如果找不到要移除的節點則丟擲錯誤
throw new RangeError(`Index ${index} does not exist in the list.`);
}
}
複製程式碼
remove() 方法首先先檢查前兩個特殊情況，空連結串列 this[head] 為 null 和 index 小於零；兩種情況都將丟擲錯誤。
下一個特殊情況就是當 index 為 0 時，意味著你需要刪除連結串列的頭部。新的連結串列的頭部將會成為原來連結串列中的第二個節點，因此你可以將 this[head].next 賦值於 this[head] 。不用擔心如果連結串列中只有一個節點，因為 this[head] 最終會等於 null ，也就意味著移除節點後連結串列變成了空連結串列。唯一的問題就是，我們需要將連結串列原來的頭部的資料儲存在一個區域性變數 data 中，以便返回它。
在處理了四個特殊情況的前三個之後，現在你可以繼續進行類似於 get() 方法中的遍歷。就像之前提到的， remove() 方法中的迴圈有一點不一樣，那就是它使用了 previous 來跟蹤 current 的上一個節點，因為 previous 是能否正確移除節點的關鍵資訊。和 get() 方法類似，當退出迴圈時， current 可能為 null ，也就表示未找到 index 。如果發生了這種情況，那就丟擲錯誤；反之將 current.next 賦值於 previous.next ，這樣就很有效地將 current 從連結串列中移除了。最後一步就是將 current 中所儲存的值返回即可。
remove() 方法的演算法時間複雜度與 get() 方法一樣，當移除第一個節點時，時間複雜度為 O(1) ；當一處最後一個節點時，時間複雜度為 O(n) 。
使連結串列可迭代
為了能使用 JavaScript 中的 for-of 迴圈和陣列解構，資料的集合必須使可迭代的。在預設情況下，JavaScript 中的內建的集合（如 Array 和 Set）都是可迭代的，你可以通過在類上指定 Symbol.iterator 生成器（ genenrator ）方法來使你自己定義的類可迭代。我更傾向於先實現一個 values() 生成器方法（用來匹配內建集合類中找到的方法），然後直接使用 Symbol.iterator 來呼叫 values() 。
values() 方法只需要對連結串列進行基本的遍歷並 yield 每個節點的值即可：
class LinkedList {
// 為了簡潔，先隱藏之前新增的方法
*values() {
let current = this[head];
while (current !== null) {
yield current.data;
current = current.next;
}
}
[Symbol.iterator]() {
return this.values();
}
}
複製程式碼
values() 方法通過前置的 * 星號來標明它為一個生成器方法。該方法用於遍歷連結串列，並使用 yield 來返回其遇到的每個節點的值。（注意 Symbol.iterator 方法並不是生成器，因為它是從 values() 生成器方法中返回一個迭代器）
使用類
實現了上述的方法後，你就可以如下例子一樣使用這個連結串列類：
const list = new LinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
// 獲取連結串列的第二個節點
console.log(list.get(1));// orange
// 列印所有節點
for (const color of list) {
console.log(color);
}
// 移除連結串列中第二個節點
console.log(list.remove(1));// orange
// 獲取連結串列中新的第二個節點
console.log(list.get(1));// yellow
// 將連結串列轉換為陣列
const array1 = [...list.values()];
const array2 = [...list];
複製程式碼
這個連結串列的基本實現還可以新增 size 屬性來計算連結串列中的節點個數，或者其他類似 indexOf() 的方法。完整的程式碼在我的 GitHub 的 Computer Science in JavaScript 中。
總結
連結串列可能並不是你每天都會用到的東西，但它在計算機科學技術中式非常基礎的一種資料結構。其利用節點來指向彼此節點的概念在很多其他的資料結構中及其他的高階程式語言中都有所體現。能夠很好地理解連結串列的工作原理對於如何全面理解怎麼建立及使用其他資料結構非常重要。
而對於 JavaScript 來說，你應該儘量使用內建的集合類，譬如 Array ，而不是自己寫一個。因為內建的集合類已經針對生產使用進行了優化，並在不同的執行環境下有良好的支援。