深入理解鏈表（Linked List）與資料結構 - 以 JavaScript 實作
會開始寫有關演算法的文章，一部分是知道自己在演算法沒有這麼熟悉，另一個部分，則是發現現在面試考演算法的比例變高了。因此也下定決心，在這個過程慢慢地把演算法補齊。今天要介紹的資料結構便是——鏈表（Linked List）。
如何理解 Linked List 與 Array 的差異？
與常見的數組（Array）不同，我們可以用書櫃和貨櫃車的貨櫃來比喻。想像數組就像是一個書櫃，其中的書籍排列整齊，每本書都在自己的位置上。當你需要找一本書時，只要知道它的位置，就可以直接拿到它。這就像是在 Array 中，可以直接透過 index訪問元素。
但當你需要在書櫃中放入或拿出一本書時，可能需要移動其他書籍來為新書騰出空間，或移動被拿出的書籍所留下的空白，這就像 Array 在插入或刪除元素時，需要移動其他元素一樣。
鏈表更像是一列貨櫃車上的貨櫃。每個貨櫃都連接到下一個，但它們不一定需要排列在一條直線上。當你想增加或移除一個貨櫃時，只需要解開它與前後貨櫃的連接，然後將它移出或加入即可。這就像在鏈表中添加或刪除節點那樣，不需要移動其他節點，只需要更改一些鏈接即可。
不過，如果你需要找到特定順位的貨櫃，你就會需要從頭開始計算，直到找到目標為止，這也說明了 Linked List 在搜尋上的特性。
這一篇文章有什麼？
本文將深入探討鏈表的核心概念，並使用 JavaScript 來說明如何實現和操作鏈表。我們將一步一步說明鏈表的六大方法：
- append（添加到末尾）
- prepend（添加到開頭）
- insert（插入元素至特定位置）
- remove（刪除元素）
- find（查找元素）
- reverse（反轉鏈表）
每個方法都將通過詳細的程式碼和解釋，讓您不僅學會如何使用這些方法，還能深入理解其背後的原理。接著，就讓我們開始吧！
鏈表（Linked List）的核心概念
鏈表（Linked List）是一種數據結構，它由一系列節點（Node）組成，每個節點包含數據和指向下一節點（next）的連接。也是因為結構的特性，使得元素的插入和刪除等操作，可以在任何位置有效率地進行，不同於需要連續記憶體空間的數組（Array）。
例如 React 的 hooks 儲存，就是使用 Linked List 的結構進行儲存，這也是為什麼 hook 不能被放在條件式之中的主因。但礙於本篇的主題，之後有機會再開一篇。
為何 Linked List 插入與刪除優於 Array？
鏈表與數組的主要區別在於數據存儲和訪問方式。數組是連續存儲的，這意味著它們可以快速訪問任何位置的元素（時間複雜度 O(1) ），但在中間插入或刪除元素時可能效率較低。相反，鏈表在插入和刪除操作上更有優勢，但對於隨機訪問與搜尋來說效率較低。
常見的單鏈表與雙鏈表
鏈表可以分為兩類：單鏈表（Singly Linked List）和雙鏈表（Doubly Linked List）。單鏈表的節點僅包含指向下一節點（next）的鏈接，而雙鏈表的節點則包含兩個鏈接，分別指向前一個（prev）和下一個節點（next）。
- 單鏈表：在這種類型的鏈表中，每個節點只含有指向下一節點的鏈接。這意味著它們只能單向遍歷。單鏈表結構簡單，使用的記憶體較少，但在某些操作中，如反向遍歷或查找前節點時效率會很差。
- 雙鏈表：與單鏈表不同，雙鏈表的節點不僅有指向下一節點的鏈接，還有指向前一節點的鏈接。這種結構使得雙向遍歷成為可能，提高了某些操作的效率，例如反向遍歷和在特定位置插入或刪除節點。然而，這種靈活性是以增加額外內存為代價，因為每個節點需要額外的記憶體空間，來存儲前驅節點的引用。
因此，在選擇使用哪種類型的鏈表時，就會需要思考何種限制與需求需要被優先滿足。
實現鏈表的基礎結構
在 JavaScript 中實現一個鏈表，最重要的有兩個核心元素：
- 節點類（Node class）
- 鏈表類（LinkedList class）
首先需要創建一個節點類（Node class），用於表示鏈表中的每個節點。隨後，我們將建立一個鏈表類（LinkedList class），用於管理這些節點並提供鏈表操作的方法。
節點類（Node class）的實現
節點類通常包含兩個屬性：value（用於存儲數據）和 next（用於指向鏈表中的下一個節點）。以下會各自實現單向列表（Singly Linked List）與雙向列表（Doubly Linked List）。兩者唯一的差異，就在於每一個節點，需要多一個 prev 來記錄前一個 Node 的指向。
// Singly Node
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Doubly Node
class DoublyNode {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
鏈表類（Linked List class）的初始結構
鏈表類則負責組織節點（Node），並提供各種操作鏈表的方法。在這個基本結構中，head 屬性指向鏈表的第一個節點，且因為尚未有任何節點，因此 tail 也指向 head 的 null。而 size 屬性則用於追蹤鏈表中的節點總數。
class LinkedList {
constructor() {
this.head = null;
this.tail = this.head;
this.size = 0;
}
}
如何實作 Linked List 常見的方法
接下來，筆者將六個常見的方法「append」、「prepend」、「insert」、「remove」、「find」和「reverse」等鏈表操作，以實際的程式碼逐行說明。但也要提醒大家，實際上不只有一種實現方式，這篇文章的只是其中一種實現方式，提供給大家參考與對照。
append - 在鏈表尾部添加元素
append 這個方法，主要用於在鏈表的末尾添加一個新節點。這個操作首先檢查是否存在頭節點（head）。如果沒有，新節點將成為頭節點。
接著，因為我們有設定 tail 來直接找到最後一個節點，不然就需要從頭遍歷鏈表，找到最後一個節點，並將其 next 指針指向新節點。
而雙向鏈表需要額外做的步驟，在於將新節點的 prev 與原先 tail 的節點相連，讓我們可以從新的節點找到前一個的節點。
// Singly Linked List
class LinkedList {
append(item) {
const newNode = new Node(item);
if (this.head === null) { // 如果為空鏈表
this.head = newNode; // 將 newNode 新增至 head
this.tail = this.head; // 將 newNode 新增至 tail
} else {
this.tail.next = newNode; // 將 newNode 接在 tail 的後方
this.tail = newNode; // 將 tail 換成 newNode
}
this.size++;
return this; // 方便鏈式調用
}
}
// Doubly Linked List
class DoublyLinkedList {
append(item) {
const newNode = new Node(item);
if (this.head === null) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.prev = this.tail; // 將 newNode 的前節點設定為原先的 tail 節點
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}
}
prepend - 在鏈表頭部添加元素
prepend 方法將新節點添加到鏈表的開頭。對於單向鏈表，這涉及將新節點的 next 指向當前的頭節點，然後更新頭節點為新節點。對於雙向鏈表，還需要設置新節點的前驅節點為 null 並更新原頭節點的 prev 為新節點。
// Singly Linked List
class LinkedList {
prepend(item) {
const newNode = new Node(item);
newNode.next = this.head; // 將 newNode 的 next 指向當前的頭節點 head。
this.head = newNode; // 更新 head 為 newNode。
return this;
}
}
// Doubly Linked List
class DoublyLinkedList {
prepend(item) {
const newNode = new DoublyNode(item);
if (!this.head) { // 如果鏈表為空，則將 newNode 設為頭節點和尾節點。
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head; // 將 newNode.next 指向當前的頭節點
this.head.prev = newNode; //將原頭節點的 prev 指向 newNode
this.head = newNode; // 更新 head 為 newNode
}
return this;
}
}
insert - 從鏈表的特定位置插入元素
在單向鏈表中，這需要遍歷鏈表到特定的 index 元素後，再更新前一節點的 next 指針以指向插入的新節點。並將新節點的 next 與原先的下一個節點連結在一起。而在雙向鏈表中，除了要更新前一個節點的 next 指針，也要更新插入節點的 prev ，以及下一個的 prev 指針。
// Singly Linked List
class LinkedList {
insert(item, index) {
if (index < 0 || index >= this.size) return null;
if (index === 0) return this.prepend(item);
if (index === this.size - 1) this.append(item);
const newNode = new Node(item);
let current = this.head;
for (let i = 0; i < index; i++) { // 找到要插入的前一個節點
current = current.next;
}
newNode.next = current.next; // 將 newNode 的 next 指向當前的頭節點 head。
current.next = newNode; // 更新 head 為 newNode。
this.size++; // 更新長度
return this;
}
}
// Doubly Linked List
class DoublyLinkedList {
insert(item, index) {
if (index < 0 || index >= this.size) return null;
if (index === 0) return this.prepend(item);
if (index === this.size - 1) this.append(item);
const newNode = new Node(item);
let current = this.head;
let previous = null;
for (let i = 0; i < index; i++) { // 找到插入的當前節點
previous = current;
current = current.next;
}
newNode.next = current; // 將 newNode 的 next 指向當前節點。
newNode.prev = previous; // 將新節點的 prev 接上上一個節點
current.prev = newNode; // 將當前節點的 prev 接上 newNode
previous.next = newNode;
this.size++; // 更新長度
return this;
}
}
remove - 從鏈表中刪除給定 index 元素
remove 方法用於從鏈表中刪除元素。在單向鏈表中，需要遍歷整個鏈表，以找到要刪除的元素 index，並更新前一節點的 next 指針以刪除目標節點。而在雙向鏈表中，除了更新前一節點的 next 指針，還需要更新後一節點的 prev 指針。
// Singly Linked List
class LinkedList {
remove(index) {
if (!this.head) return null; // 如果鏈表為空，直接返回
if (index < 0 || index >= this.size) return null; // index 為負數或超出範圍
// 如果頭節點是要刪除的節點
if (index === 0) {
const removedNode = this.head;
this.head = this.head.next; // 更新 head 節點
this.size--;
return removedNode;
}
let current = this.head; // 記錄當前的 Node
let previous = null; // 記錄上一個節點
let counter = 0; // 記錄遍歷到第幾次
// 找到 index 的當前 Node，且確認該節點不為空（超出範圍）
while (counter < index && current !== null) {
[previous, current] = [current, current.next];
counter++;
}
// 如果確定當前節點不為空，則將上一個節點的 next 接在 current 的下一個節點
if (current !== null) previous.next = current.next;
this.size--;
return this;
}
}
// Doubly Linked List
class DoublyLinkedList {
remove(index) {
if (!this.head) return null; // 如果鏈表為空，直接返回
if (index < 0 || index >= this.size) return null; // index 為負數
// 如果頭節點是要刪除的節點
if (index === 0) {
const removedNode = this.head;
this.head = this.head.next; // 更新頭節點
if (this.head) this.head.prev = null; // 如果新的頭節點存在，更新其 prev 指針
else this.tail = null; // 如果移除後沒有 Node，則將 tail 一併設為 null
this.size--;
return removedNode;
}
let current = this.head; // 從頭開始計算
let counter = 0; // 用以計數
while (counter < index && current !== null) {
current = current.next;
counter++;
}
const removedNode = current; // 保存被移除的節點
// 處理目標不為最後一個節點時，將下一個節點的 prev 接上上一個節點
if (current.next) current.next.prev = current.prev;
// 如果不為第一個節點，則將前一個節點的 next 接上下一個節點
if (current.prev !== null) current.prev.next = current.next;
// current 為最後一個節點的情況，將前一個節點更新為 tail
if (current === this.tail) this.tail = current.prev;
this.size--;
return removedNode; // 如果沒有找到，返回鏈表本身
}
}
find - 在鏈表中查找元素
find 方法用於在鏈表中查找特定元素。無論是單向鏈表還是雙向鏈表，此方法的基本操作相同：從頭節點開始遍歷，直到找到匹配的元素或達到鏈表末尾。
// Singly Linked List
class LinkedList {
find(value) {
let current = this.head;
while (current) {
if (current.value === value) return current; // 找到匹配的元素，返回該節點
current = current.next;
}
return null; // 沒有找到，返回 null
}
}
// Doubly Linked List
class DoublyLinkedList {
find(value) {
let current = this.head;
while (current) {
if (current.value === value) return current; // 找到匹配的元素，返回該節點
current = current.next;
}
return null; // 沒有找到，返回 null
}
}
reverse - 反轉鏈表
reverse 方法將鏈表的元素順序反轉。在單向鏈表中，此操作需要更改每個節點的 next 指針。在雙向鏈表中，還需要更改每個節點的 prev 指針。
// Singly Linked List with iteration
class LinkedList {
reverse() {
let current = this.head;
let prev = null;
let next = null;
while (current) {
next = current.next; // 保存下一個節點
current.next = prev; // 反轉當前節點的 next 指針
prev = current; // 移動 prev 節點
current = next; // 移動到下一個節點
}
this.head = prev; // 更新頭節點
return this;
}
}
// Singly Linked List with Recursion
class LinkedList {
reverse() {
// 定義 recursion 的函式
function reverseList(head) {
// 確定當前節點或下一個節點為空，則直接返回傳入的當前節點
if (head === null || head.next === null) return head;
const reversedList = reverseList(head.next);
head.next.next = head; // 將下個節點的 next 接上當前節點
head.next = null; // 將當前節點的 next 暫時移除連接（因為往後執行時會再接上）
return reversedList;
}
// 處理無節點，或僅有一個節點的情況
if (this.head === null || this.head.next === null) return this;
const originHead = this.head; // 記得原先的 head
this.head = reverseList(this.head);
this.tail = originHead; // 將原本的 head 換成 tail
return this;
}
}
// Doubly Linked List
class DoublyLinkedList {
reverse() {
let current = this.head;
let temp = null;
while (current) {
// 交換 prev 和 next 指針
[current.next, current.prev] = [current.prev, current.next];
current = current.prev; // 移動到原本的下一個節點
}
if (temp) this.head = temp.prev; // 更新頭節點
return this;
}
}
其中，要注意的是遞迴（Recursion）會將欲執行的函式疊在 Stack 中，因此最後執行的函式會被優先處理。換句話說，最後執行的結果就會是終止函式，接著才從終止函式中往回執行，直到處理第一個函式。
Linked List 的應用場景
鏈表（Linked List）作為一種靈活且強大的數據結構，目前搜尋到的有以下是幾個經典應用場景：
- 動態數據存儲：由於鏈表可以在運行時動態地增加或減少節點，它們非常適合用於不確定大小的數據集合，例如用戶生成的內容列表或實時消息體系。
- 實現隊列和堆棧：鏈表非常適合實現如 Queue 和 Stack 這樣的抽象數據類型。尤其是在需要頻繁進行插入和刪除操作的場景中，Linked List 的效能會優於 Array。
- 圖的表示：在圖形算法中，鏈表可用來有效地表示圖的邊和節點，尤其是在實現鄰接表時。
- 記憶體管理：操作系統中的記憶體管理，也常使用鏈表來追蹤空閒的記憶體塊。
結語
第一次在了解與實作 Linked List 時，花了非常多時間在了解其核心的觀念，以及如何對 Linked List 的資料結構進行操作，這些都讓一開始學習 Linked List 有著一定的門檻。筆者自己也是在一點一滴的實作中，才慢慢知道如何操作 Linked List，甚至慢慢能夠寫出常見的方法。
因此這一篇文章，希望能夠給剛接觸 Linked List 的人一些切入方向，並透過文章中的逐步說明，了解 Linked List 這一個資料結構的美妙！
如果以上內容有任何錯誤或建議，都歡迎直接留言或來信交流！
Reference 參考資料
- 如何理解 Linked List 與 Array 的差異？
- 這一篇文章有什麼？
- 鏈表（Linked List）的核心概念
- 為何 Linked List 插入與刪除優於 Array？
- 常見的單鏈表與雙鏈表
- 實現鏈表的基礎結構
- 節點類（Node class）的實現
- 鏈表類（Linked List class）的初始結構
- 如何實作 Linked List 常見的方法
- append - 在鏈表尾部添加元素
- prepend - 在鏈表頭部添加元素
- insert - 從鏈表的特定位置插入元素
- remove - 從鏈表中刪除給定 index 元素
- find - 在鏈表中查找元素
- reverse - 反轉鏈表
- Linked List 的應用場景
- 結語
- Reference 參考資料
