前面的佇列與堆疊都是特殊的線性表,也都屬於比較簡單的、基於陣列的順序儲存結構。由於 JavaScript 解釋器針對陣列做了大量優化,我們不會遇到許多語言中「陣列填滿後難以擴充」的問題(push、pop、shift、unshift、splice 等方法都已經包裝好了)。但順序儲存有一個根本上的限制,而鏈式儲存正是為了解它而出現的。
線性表的順序儲存結構,最大的缺點是:改動其中一個元素的位置,往往會牽動整個集合。原因在於記憶體中的配置是連續而沒有間隙的,刪掉一個自然就得補位。
鏈式儲存換了個思路:我們完全不關心資料在記憶體中的排列,只需要在每個元素裡記錄「下一個資料在哪裡」即可。用鏈接方式儲存的線性表就稱為鏈表,其中每筆資料 = 資訊 + 位址。
我們把位址稱為「鏈」,一個資料單元就是一個節點,鏈表就是一串節點組成的集合,每個節點都有一個指標指向它的下一個節點。

對比就很清楚:陣列元素靠位置關係做邏輯引用,鏈表則靠每個節點保存的指標來引用。這種結構的優勢在插入與刪除時特別明顯——完全不必理會排列,只要把鏈的指向接上即可。
這樣一來,思路就不必局限在陣列上,用物件也行,只要物件之間存在引用關係即可。
單鏈表:單純地往下一個傳遞,每個節點只記錄下一個節點的資訊。
靜態鏈表:用陣列描述的鏈表,陣列中每個索引都是一個「節」,包含資料與指向。
循環鏈表:單鏈表只能往後傳遞,到達尾部後要回溯到頭部很麻煩,因此把尾節的鏈接回頭節形成循環。
雙向鏈表:針對單鏈表的優化,讓每個節都知道前後是誰,除了後指標還有一個前指標,提高查找效率,代價是設計上的複雜度提升——本質上是空間換時間。
綜合來看,鏈表就是線性表中針對順序儲存的一種優化手段。而在 JavaScript 中,由於陣列會自動更新索引,我們可以用物件來做鏈式結構。
function createLinkList() {
var prev = null;
return {
add: function(val) {
// 保存目前的引用
prev = { data: val, next: prev || null };
}
};
}
var linksList = createLinkList();
linksList.add("arron1");
linksList.add("arron2");
linksList.add("arron3");
// node 的 next 鏈:-arron3- → -arron2- → -arron1
透過 node 物件的 next 直接引用下一個 node,初步實現了鏈式引用。但還有一個關鍵問題沒解決:如何動態插入資料到某個節點之後?為此必須設計一個遍歷方法,沿著鏈搜尋目標節點,找到後把新節插入並改寫指標。
// 在鏈表中找到對應的節(用 curry 手法固定起點)
var findNode = function createFindNode(currNode) {
return function(key){
while (currNode.data != key) {
currNode = currNode.next;
}
return currNode;
};
}(headNode);
指標的換算關係很簡單:在 a-b-c-d 中,若要在 c(此時 c.next 指向 d)之後插入 f,結果是 a-b-c-f-d,做法是讓 c.next 指向 f,再讓 f.next 指向 d。
// 建立節
function createNode(data) {
this.data = data;
this.next = null;
}
// 初始化頭部節,從 headNode 開始形成一條鏈
var headNode = new createNode("head");
this.insert = function(data, key) {
var newNode = new createNode(data);
var current = findNode(key);
newNode.next = current.next; // 先接上後繼
current.next = newNode; // 再改寫前驅
};
這兩行的順序至關重要:必須先把新節的 next 指向原本的後繼,才不會在改寫 current.next 時把後半條鏈丟掉。
鏈表的特性決定了刪除方式:a→b→c→d 中要刪掉 c,就必須把 b.next 從指向 c 改成指向 d。也就是要先找到前一個節點——這有點像 DOM 操作中必須先取得父節點才能呼叫 removeChild。
// 找到前一個節
var findPrevious = function(currNode) {
return function(key){
while (!(currNode.next == null) && (currNode.next.data != key)) {
currNode = currNode.next;
}
return currNode;
};
}(headNode);
this.remove = function(key) {
var prevNode = findPrevious(key);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next; // 跳過目標節
}
};
function createLinkList() {
function createNode(data) {
this.data = data;
this.next = null;
}
var headNode = new createNode("head");
var findNode = function(currNode) {
return function(key) {
while (currNode.data != key) { currNode = currNode.next; }
return currNode;
};
}(headNode);
var findPrevious = function(currNode) {
return function(key) {
while (!(currNode.next == null) && (currNode.next.data != key)) {
currNode = currNode.next;
}
return currNode;
};
}(headNode);
this.insert = function(data, key) {
var newNode = new createNode(data);
var current = findNode(key);
newNode.next = current.next;
current.next = newNode;
};
this.remove = function(key) {
var prevNode = findPrevious(key);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
};
this.display = function(fn) {
var currNode = headNode;
while (!(currNode.next == null)) {
currNode = currNode.next;
fn(currNode.data);
}
};
}
var cities = new createLinkList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display(function(data){ console.log(data); });
cities.remove("Russellville");
要留意的是 findNode 找不到 key 時會沿著 next 走到 null,下一輪比對就會拋出錯誤。實務上應在迴圈條件中加上 currNode != null 的檢查並回傳 null,由呼叫端決定如何處理。
原理與單鏈表相同,只是每個節多了一個指向前驅的指標。

插入:
this.insert = function(data, key) {
var newNode = new createNode(data);
var current = findNode(headNode, key);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
};
刪除:
this.remove = function(key) {
var currNode = findNode(headNode, key);
if (!(currNode.next == null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
};
刪除時有一個明顯的優化:不需要再去找父節點,因為雙向引用讓前驅可以直接取得,效率比單鏈表高。
陣列與鏈表的取捨是經典題目:陣列的隨機存取是 O(1),但插入刪除是 O(n);鏈表插入刪除是 O(1)(前提是已經找到位置),但只能循序存取,而且每個節點都多一份指標的空間成本,快取局部性也較差。
在 JavaScript 中,由於陣列底層已經足夠優秀,實務上大多不需要自己實作鏈表。真正理解它的價值在於看懂那些「指標思維」的應用:jQuery 的 deferred 鏈、React Fiber 的鏈式結構、瀏覽器 DOM 的節點樹、以及 LRU 快取常用「雜湊表 + 雙向鏈表」的組合——背後都是同一套想法。