跳至主要内容

Array 和 String

這兩個資料結構比較類似，所以放在一起討論。

陣列（Array）與字串（String）都是用來按順序儲存多個資料的基礎資料結構。

Array 可以放各種資料，String 則專門放文字字元，兩者都能用數字索引來快速抓取資料，且在記憶體中通常是排成直線的連續空間。

簡單介紹​

  • 陣列（Array）
    • 可以裝數字、物件、布林值或甚至是另一個陣列等等。
    • 常見於各種清單與資料列表。
    • 也可稱作 list，在 JavaScript 稱為 Array，而在 Python 中則稱作 List。
  • 字串（String）
    • 本質上很像一個「唯讀的字元陣列」。
    • 專門用來處理文字、句子與字母。
  • 相似之處
    • 使用索引：兩者都用數字編號（通常從 0 開始）來代表每個位置，能直接找到特定資料。
    • 順序排列：裡面的資料都有固定前後順序，不是亂跳的。
    • 連續記憶體：在電腦記憶體裡，它們的資料通常排得很靠近，找資料速度快。
    • 可疊代性：都能用迴圈（Loop）一個一個讀出裡面的內容。

適用情況​

適合使用 Array 的情境是當資料具有順序性，且你不在乎或不需要透過特定的鍵（Key）來查找時，Array 是最佳選擇。

  • 商品列表、代辦事項（Todo List）：需要排序、過濾（filter）、分頁顯示的資料。
  • 歷史紀錄、時間軸（Timeline）：需要維持資料進來的先後順序（例如：瀏覽紀錄、聊天訊息列表）。
  • 堆疊與佇列（Stack & Queue）：需要頻繁在「尾端」新增或刪除資料（例如：Undo/Redo 復原功能）。
  • 集體操作（Bulk Operations）：當你常常需要用 map、forEach 或 reduce 把所有資料從頭到尾洗一遍、轉成別的格式時。

複雜度​

操作種類陣列 (Array)字串 (String)備註說明
讀取資料 (Access)O(1)O(1)知道 index 就能瞬間找到。
尋找資料 (Search)O(n)O(n)必須從頭到尾一個一個檢查（線性搜尋）。
尾端新增/刪除 (Push/Pop)O(1)O(n)array 的尾端操作極快；string 因不可變性通常需要重新複製整串。
其他位置新增/刪除 (Insert)O(n)O(n)除了尾端之外，插入內容後 array 必須把後面所有元素往後/往前挪移；字串同樣需要重寫。

實作​

JavaScript 和 Python 都有內建 array/list 這個資料結構。

這邊提供利用 js 實作的寫法，為了方便大家理解。

class MyArray {
  constructor() {
    this.length = 0; // 記錄目前陣列的長度
    this.data = {};  // 用物件的 key (0, 1, 2...) 來模擬記憶體索引
  }

  // 1. 讀取資料：O(1)
  get(index) {
    return this.data[index];
  }

  // 2. 尾端新增：O(1)
  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  // 3. 尾端刪除：O(1)
  pop() {
    if (this.length === 0) return undefined;
    
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }

  // 4. 開頭新增：O(n) - 所有元素都要往後挪一格，空出索引 0
  unshift(item) {
    // 從最後一個元素開始，全部往後複製一格
    for (let i = this.length; i > 0; i--) {
      this.data[i] = this.data[i - 1];
    }
    // 把新資料放到開頭
    this.data[0] = item;
    this.length++;
    return this.length;
  }

  // 5. 開頭刪除：O(n) - 所有元素都要往前挪一格，補上索引 0 的空缺
  shift() {
    if (this.length === 0) return undefined;

    const firstItem = this.data[0];
    
    // 從索引 1 開始，全部往前覆蓋一格
    for (let i = 0; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    
    // 刪除原本最後一個重複的格子
    delete this.data[this.length - 1];
    this.length--;
    return firstItem;
  }
}
最後於 更新