深入理解鏈表（Linked List）與資料結構 - 以 JavaScript 實作

Unsplash

會開始寫有關演算法的文章，一部分是知道自己在演算法沒有這麼熟悉，另一個部分，則是發現現在面試考演算法的比例變高了。因此也下定決心，在這個過程慢慢地把演算法補齊。今天要介紹的資料結構便是——鏈表（Linked List）。

如何理解 Linked List 與 Array 的差異？

與常見的數組（Array）不同，我們可以用書櫃和貨櫃車的貨櫃來比喻。想像數組就像是一個書櫃，其中的書籍排列整齊，每本書都在自己的位置上。當你需要找一本書時，只要知道它的位置，就可以直接拿到它。這就像是在 Array 中，可以直接透過 index訪問元素。

但當你需要在書櫃中放入或拿出一本書時，可能需要移動其他書籍來為新書騰出空間，或移動被拿出的書籍所留下的空白，這就像 Array 在插入或刪除元素時，需要移動其他元素一樣。

鏈表更像是一列貨櫃車上的貨櫃。每個貨櫃都連接到下一個，但它們不一定需要排列在一條直線上。當你想增加或移除一個貨櫃時，只需要解開它與前後貨櫃的連接，然後將它移出或加入即可。這就像在鏈表中添加或刪除節點那樣，不需要移動其他節點，只需要更改一些鏈接即可。

不過，如果你需要找到特定順位的貨櫃，你就會需要從頭開始計算，直到找到目標為止，這也說明了 Linked List 在搜尋上的特性。

這一篇文章有什麼？

本文將深入探討鏈表的核心概念，並使用 JavaScript 來說明如何實現和操作鏈表。我們將一步一步說明鏈表的六大方法：

1. append（添加到末尾）
2. prepend（添加到開頭）
3. insert（插入元素至特定位置）
4. remove（刪除元素）
5. find（查找元素）
6. 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）。

1. 單鏈表：在這種類型的鏈表中，每個節點只含有指向下一節點的鏈接。這意味著它們只能單向遍歷。單鏈表結構簡單，使用的記憶體較少，但在某些操作中，如反向遍歷或查找前節點時效率會很差。
2. 雙鏈表：與單鏈表不同，雙鏈表的節點不僅有指向下一節點的鏈接，還有指向前一節點的鏈接。這種結構使得雙向遍歷成為可能，提高了某些操作的效率，例如反向遍歷和在特定位置插入或刪除節點。然而，這種靈活性是以增加額外內存為代價，因為每個節點需要額外的記憶體空間，來存儲前驅節點的引用。

因此，在選擇使用哪種類型的鏈表時，就會需要思考何種限制與需求需要被優先滿足。

實現鏈表的基礎結構

在 JavaScript 中實現一個鏈表，最重要的有兩個核心元素：

1. 節點類（Node class）
2. 鏈表類（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）作為一種靈活且強大的數據結構，目前搜尋到的有以下是幾個經典應用場景：

1. 動態數據存儲：由於鏈表可以在運行時動態地增加或減少節點，它們非常適合用於不確定大小的數據集合，例如用戶生成的內容列表或實時消息體系。
2. 實現隊列和堆棧：鏈表非常適合實現如 Queue 和 Stack 這樣的抽象數據類型。尤其是在需要頻繁進行插入和刪除操作的場景中，Linked List 的效能會優於 Array。
3. 圖的表示：在圖形算法中，鏈表可用來有效地表示圖的邊和節點，尤其是在實現鄰接表時。
4. 記憶體管理：操作系統中的記憶體管理，也常使用鏈表來追蹤空閒的記憶體塊。

結語

第一次在了解與實作 Linked List 時，花了非常多時間在了解其核心的觀念，以及如何對 Linked List 的資料結構進行操作，這些都讓一開始學習 Linked List 有著一定的門檻。筆者自己也是在一點一滴的實作中，才慢慢知道如何操作 Linked List，甚至慢慢能夠寫出常見的方法。

因此這一篇文章，希望能夠給剛接觸 Linked List 的人一些切入方向，並透過文章中的逐步說明，了解 Linked List 這一個資料結構的美妙！

如果以上內容有任何錯誤或建議，都歡迎直接留言或來信交流！

Reference 參考資料

• 基礎演算法系列 — 基礎資料結構 Linked-list 與 Array
• Implementation of LinkedList in Javascript
• Linked list Javascript實作及Leet code題目解析