演算法與資料結構(js) : 什麼是資料結構 ? 相關觀念、種類、實作與範例

 

如果把程式比成餐廳，資料結構就是廚房的收納：刀叉分門別類、常用的放手邊、笨重的放底層。收納對了，出菜就快；放錯了，再厲害的主廚也會忙亂。本文帶你用輕鬆的步調認識資料結構：它是什麼、為何重要、在程式設計裡扮演的角色。

接著用 JavaScript 實例把重點拆開：陣列怎麼高效處理、Map/Set 何時比物件安全、用 Heap 做排行榜、用 Trie 做自動完成、用 Graph 表達關係。你不需要背公式，只要記住選型邏輯與幾個小技巧，寫起來就會順很多。希望本篇文章能幫助到需要的您。

目錄

{tocify} $title={目錄} 

什麼是「資料結構」？

資料結構（Data Structure）是在電腦記憶體中「如何組織與儲存資料」的一套方法，讓我們能更有效地存取（讀取、搜尋）、更新（新增、刪除、修改）與傳輸資料。

同一批資料，用不同的結構表示，效能可能有天壤之別：有的適合快速查找，有的擅長維持順序，有的用來建模關係網路。

資料結構 vs. 演算法

資料結構：用來存放資料的「容器與形狀」。

演算法：在這些容器上「操作資料的步驟與流程」。

兩者互相依存：好的演算法需要合適的資料結構支撐；正確的資料結構也能讓演算法威力加倍。

為什麼需要資料結構？

1.    效能（Performance）

        隨著資料量成長，程式速度與記憶體成本會急速放大。合適的結構能把 O(n) 的操作降到 O(log n) 或 O(1)。

2.    可維護性（Maintainability）

        清楚的資料模型讓程式碼更容易閱讀、測試與擴充。

3.    對應真實世界問題（Modeling）

        圖（Graph）可以直觀表達社群關係、路網、依賴關係；堆（Heap）很適合做排程與優先佇列。

4.    可預測性（Predictability）

        知道查找、插入、刪除的時間複雜度，能預估在壓力下系統的行為，避免「上線才爆」。

資料結構在程式設計中的角色

1.    抽象化（Abstraction）：把資料與操作封裝成可重用模組（如 Map、Set、PriorityQueue）。

2.    API 設計：良好的資料結構往往伴隨直覺 API（push/pop、add/delete、get/set）。

3.    演算法基石：排序、搜尋、最短路徑、拓樸排序等都依賴特定結構達成最佳效率。

4.    系統與框架內核：瀏覽器渲染佇列、資料庫索引（B-Tree）、排程器、快取（Hash）都建築在資料結構上。

常見資料結構與應用情境（含 Big-O 概觀）

以下的「平均情況」複雜度以常見實作為準，實務仍依語言與實作細節而異。

結構	典型操作	時間複雜度（平均）	常見應用
Array/動態陣列	隨機存取、尾端插入	取值 O(1)、插尾 O(1)*、刪中 O(n)	順序資料、批次處理
Linked List	插刪已知節點	插刪 O(1)、查找 O(n)	需要頻繁插刪、記憶體分散
Stack	LIFO push/pop	O(1)	呼叫堆疊、撤銷/回上一步
Queue/Deque	FIFO/雙端操作	O(1)	工作佇列、滑動視窗
Hash Table (Map/Set)	插刪查	平均 O(1)	快取、去重、索引
Tree（BST/AVL/Red-Black）	有序查找、範圍查詢	平均 O(log n)	排序結構、資料庫索引基礎
Heap（Priority Queue）	取最小/最大	取堆頂 O(1)、插刪 O(log n)	排程、Dijkstra、Top-K
Trie（字典樹）	前綴查找	與字串長度 m 成正比 O(m)	自動完成、拼字檢查
Graph	鄰接與遍歷	依圖結構與演算法	路網、社群、依賴分析

* 動態陣列擴容均攤成本為 O(1)；最壞情況擴容為 O(n)。

在 JavaScript 中如何使用資料結構？

JavaScript 雖然不是「強型別 + 標準庫齊全」的資料結構語言，但 ES6 之後已具備實用容器：Array、Map、Set、WeakMap、WeakSet，搭配物件、類別與閉包，可完成多數常見結構。以下分主題示範。

1. 陣列 Array：基礎但萬能

// 常見操作
const arr = [10, 20, 30];
arr.push(40);      // 尾插 O(1) 均攤
arr.pop();         // 尾刪 O(1)
arr.unshift(5);    // 頭插 O(n) 需整體位移
arr.splice(1, 1);  // 中間刪除 O(n)
console.log(arr[2]); // 隨機存取 O(1)

 

技巧

需要大量頭部操作時，考慮 Deque（見下）。

需要去重：[...new Set(arr)]。

批次處理用 map/filter/reduce，可讀性高。

2. 佇列 Queue / 雙端佇列 Deque

JS 原生陣列的 shift/unshift 是 O(n)。要 O(1) 雙端操作，可用環形緩衝或鏈結串列；下例給出簡潔 Deque。

class Deque {
  constructor() { this._data = {}; this._head = 0; this._tail = 0; }
  pushBack(x) { this._data[this._tail++] = x; }      // O(1)
  pushFront(x) { this._data[--this._head] = x; }     // O(1)
  popBack() { if (this.isEmpty()) return undefined;
    const v = this._data[--this._tail]; delete this._data[this._tail]; return v; }
  popFront() { if (this.isEmpty()) return undefined;
    const v = this._data[this._head]; delete this._data[this._head++]; return v; }
  front() { return this._data[this._head]; }
  back() { return this._data[this._tail - 1]; }
  size() { return this._tail - this._head; }
  isEmpty() { return this.size() === 0; }
}

 

應用：滑動視窗最大值、BFS、任務排程、瀏覽器前進後退。

3. 堆 Heap（Priority Queue）

JS 沒有內建 PriorityQueue，常用二元堆實作。以下為最小堆：

class MinHeap {
  constructor(comp = (a,b) => a - b) { this.a = []; this.comp = comp; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) { this.a.push(x); this._up(this.size()-1); }
  pop() {
    if (!this.size()) return undefined;
    const top = this.a[0], last = this.a.pop();
    if (this.size()) { this.a[0] = last; this._down(0); }
    return top;
  }
  _up(i){
    const {a, comp} = this;
    while(i>0){
      const p = (i-1>>1);
      if (comp(a[i], a[p]) >= 0) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  _down(i){
    const {a, comp} = this;
    for(;;){
      let l = i*2+1, r = l+1, s = i;
      if (l < a.length && comp(a[l], a[s]) < 0) s = l;
      if (r < a.length && comp(a[r], a[s]) < 0) s = r;
      if (s === i) break;
      [a[i], a[s]] = [a[s], a[i]]; i = s;
    }
  }
}
// 使用：取前 K 小（或大）元素
const heap = new MinHeap();
[5,3,8,1,2].forEach(x => heap.push(x));
while (heap.size()) console.log(heap.pop()); // 1,2,3,5,8

 

應用：Top-K、即時排行、事件排程、Dijkstra 最短路徑。

4. 雜湊 Hash：Map 與 Set

ES6 Map/Set 以雜湊為核心（具備插刪查平均 O(1) 的特性）。

// Map：鍵值對
const m = new Map();
m.set('id', 123);
m.set({ u: 1 }, 'obj'); // 物件也能當 key（比 Object 更健壯）
console.log(m.get('id'));  // 123
console.log(m.has('id'));  // true
m.delete('id');

// Set：去重與集合運算
const s = new Set([1,2,2,3]); // {1,2,3}
const t = new Set([2,3,4]);
const inter = new Set([...s].filter(x => t.has(x)));   // 交集 {2,3}
const diff  = new Set([...s].filter(x => !t.has(x)));  // 差集 {1}

 

應用：快取、計數（Map 做頻率表）、去重、圖的鄰接表、LRU Cache。

延伸：LRU Cache（Least Recently Used）

// 簡化版：Map + 雙端特性（Map 迭代維持插入順序）
class LRU {
  constructor(cap = 100){ this.cap = cap; this.map = new Map(); }
  get(k){
    if (!this.map.has(k)) return undefined;
    const v = this.map.get(k);
    this.map.delete(k); this.map.set(k, v); // 移到尾端（最新）
    return v;
  }
  set(k,v){
    if (this.map.has(k)) this.map.delete(k);
    this.map.set(k, v);
    if (this.map.size > this.cap) {
      const oldestKey = this.map.keys().next().value; // 最舊在頭部
      this.map.delete(oldestKey);
    }
  }
}

 

5.     鏈結串列 Linked List

JS 沒有內建 LinkedList，但可用物件節點實作。適合頻繁插刪但不常隨機存取的情境。

class ListNode { constructor(val){ this.val = val; this.next = null; } }
class SinglyList {
  constructor(){ this.head = null; }
  insertHead(val){ const n = new ListNode(val); n.next = this.head; this.head = n; }
  delete(val){
    const dummy = new ListNode(0); dummy.next = this.head;
    let cur = dummy;
    while (cur.next && cur.next.val !== val) cur = cur.next;
    if (cur.next) cur.next = cur.next.next;
    this.head = dummy.next;
  }
}

 

應用：LRU 的雙向串列、實作佇列、合併有序串列等。

6.     樹（Binary Search Tree, 平衡樹概念）

JS 可以類別手寫 BST。注意：未平衡的 BST 可能退化為鏈；生產環境常以庫或以 Map 取代。

class BSTNode { constructor(key){ this.key=key; this.left=this.right=null; } }
class BST {
  constructor(){ this.root=null; }
  insert(key){ this.root = this._ins(this.root, key); }
  _ins(node,key){
    if(!node) return new BSTNode(key);
    if(key < node.key) node.left = this._ins(node.left,key);
    else if(key > node.key) node.right = this._ins(node.right,key);
    return node;
  }
  search(key){
    let cur=this.root;
    while(cur){ if(key===cur.key) return true; cur= key<cur.key?cur.left:cur.right; }
    return false;
  }
}

 

應用：有序集合、範圍查詢、排名統計（平衡樹更佳）。

7.     Trie（字典樹）

class TrieNode { constructor(){ this.children = new Map(); this.end = false; } }
class Trie {
  constructor(){ this.root = new TrieNode(); }
  insert(word){
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) cur.children.set(ch, new TrieNode());
      cur = cur.children.get(ch);
    }
    cur.end = true;
  }
  startsWith(prefix){
    let cur = this.root;
    for (const ch of prefix) {
      if (!cur.children.has(ch)) return false;
      cur = cur.children.get(ch);
    }
    return true;
  }
}

應用：關鍵字提示、敏感詞過濾、URL 路由匹配。

 8.    圖 Graph（鄰接表）

以 Map<節點, Set<鄰居>> 表示最直覺。

class Graph {
  constructor(directed=false){ this.adj = new Map(); this.directed = directed; }
  addVertex(v){ if(!this.adj.has(v)) this.adj.set(v, new Set()); }
  addEdge(u,v){ this.addVertex(u); this.addVertex(v);
    this.adj.get(u).add(v); if(!this.directed) this.adj.get(v).add(u); }
  bfs(start){
    const vis=new Set([start]), q=[start], order=[];
    while(q.length){
      const u=q.shift(); order.push(u);
      for(const v of this.adj.get(u)||[]) if(!vis.has(v)){ vis.add(v); q.push(v); }
    } return order;
  }
}

應用：社群關係、路徑尋找、依賴與影響分析（拓樸排序）。

選擇資料結構的實戰思路

1.    找出瓶頸操作

你最常做的是查找？插入？刪除？取最小/最大？

        常查找：Map/Set

        維持順序且需範圍查詢：平衡樹（或以排序 + 二分近似）

        取最小/最大：Heap

        頻繁頭尾：Deque

2.    資料量級與可擴展性

        幾百 vs 幾百萬筆，選型結果可能完全不同。

3.    記憶體 vs. 速度取捨

        Hash 快但浪費空間；Trie 快但可能很肥。

4.    JS 生態現實

        沒有內建平衡樹與 PriorityQueue？用輕量實作或現成套件（如 heap-js）

在前端，壓力在 UI/網路多於 DS；但在資料處理與即時功能（搜尋、去重、排行）時，選對結構差很多。

常見實作陷阱與最佳實務

1.    用 Object 當字典的坑：

        原型鏈與非字串鍵的問題多；優先使用 Map。若必須用物件做字典，請搭配 Object.create(null) 產生無原型物件。

2.    陣列頭部操作：

        unshift/shift 是 O(n)。需要高頻率就改用 Deque。

3.    深拷貝與不可變資料：

        React 狀態或多人協作程式碼常需要**不可變（Immutable）**策略，搭配結構共享（Persistent DS）或以 structuredClone/immer 等工具降低成本。

4.    演算法複雜度估算：

        寫前先估 O()，寫後用基準測試（performance.now()）驗證是否符合預期。

5.    邊界條件：

        空集合、單節點、重複鍵、溢位、極端輸入。單元測試要刻意覆蓋。

整合案例：Top-K 熱門關鍵字（前端即時榜單）

需求：即時流式資料中，維持「出現次數最多的前 K 個字」。

選型：Map 做頻率表 + 大小為 K 的最小堆維持候選。

const freq = new Map();
const topK = new MinHeap((a,b) => a.count - b.count); // a={word,count}
const K = 5;

function onWord(word){
  const c = (freq.get(word) || 0) + 1;
  freq.set(word, c);

  // 嘗試更新堆：如果堆內已有該詞，簡化做法是重建堆（或額外索引定位）
  // 示範：每 N 次批量重建（降低常數因子）
}

function rebuildTopK(){
  topK.a = []; // 清空
  for (const [word, count] of freq.entries()) {
    if (topK.size() < K) topK.push({word, count});
    else if (count > topK.peek().count) { topK.pop(); topK.push({word, count}); }
  }
}

// 假設每 1000 筆重建一次
let cnt = 0;
function onStream(word){
  onWord(word);
  if ((++cnt) % 1000 === 0) rebuildTopK();
}

 

說明：

1.    Map 保持 O(1) 更新頻率。

2.    MinHeap 保持前 K 大：堆頂永遠是當前第 K 名，若新數值更大就替換。

3.    若需要每次都即時更新堆，可為堆內元素建立索引（Map<word, index>）實作「減關鍵值」或「提升權重」，但程式碼複雜度上升。

結語

        資料結構是程式設計的肌理：當資料改變形狀，問題就改變難度。在 JavaScript 的世界裡，雖然原生結構不如某些語言齊全，但憑藉 Array/Map/Set 與少量自訂類別，就能穩健地打造高效、可維護的功能。真正重要的是分析需求、辨識高頻操作、選擇合適結構，再用測試與基準驗證，讓你的程式在真實流量之下依然順暢。

延伸閱讀推薦：

javaScript : 什麼是javaScript ? 相關觀念、種類、實作與範例

javaScript : 從 ES5、ES6 到 2025 年的現在

javaScript : 變數、作用域、函數、分號與註釋

javaScript : 資料型別整理、測型方法、轉型技巧

javaScript : 傳值、傳參考、型別轉換與強弱型別

javaScript : 運算式與運算子

javaScript : 陣列宣告、種類、操作方法

javaScript : 物件導向從原型到 class、從封裝到組合

javaScript : 條件分歧處理

javaScript : 迴圈處理

javaScript : 錯誤處理與例外處理

javaScript : 函數種類、宣告、參數 vs. 引數、返回值

javaScript : class從原型到 ES6， 搞懂 constructor / new / this / prototype / static