Array 和 String

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

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

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

白話理解

想像一整排有編號的置物櫃，每一格都有固定的號碼牌（Index）。只要知道號碼，不用一格一格找過去，直接走過去開櫃子就能拿到東西。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 把所有資料從頭到尾洗一遍、轉成別的格式時。

在陣列與字串上解題時，還有三個非常常見的技巧，建議一併認識：

• Two Pointers：用兩個指標同時掃描，取代雙層迴圈。
• Sliding Window：處理「連續」子陣列或子字串的最大/最小值問題。
• Prefix Sum：需要多次查詢區間總和時，先預先計算好前綴和。

複雜度

操作種類	陣列 (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 這個資料結構。

這邊提供簡化過的實作，為了方便大家理解陣列底層的運作原理。

Python

class MyArray:
    def __init__(self):
        self.length = 0  # 記錄目前陣列的長度
        self.data = {}   # 用字典的 key (0, 1, 2...) 來模擬記憶體索引

    # 1. 讀取資料：O(1)
    def get(self, index):
        return self.data.get(index)

    # 2. 尾端新增：O(1)
    def push(self, item):
        self.data[self.length] = item
        self.length += 1
        return self.length

    # 3. 尾端刪除：O(1)
    def pop(self):
        if self.length == 0:
            return None

        last_item = self.data[self.length - 1]
        del self.data[self.length - 1]
        self.length -= 1
        return last_item

    # 4. 開頭新增：O(n) - 所有元素都要往後挪一格，空出索引 0
    def unshift(self, item):
        # 從最後一個元素開始，全部往後複製一格
        for i in range(self.length, 0, -1):
            self.data[i] = self.data[i - 1]
        # 把新資料放到開頭
        self.data[0] = item
        self.length += 1
        return self.length

    # 5. 開頭刪除：O(n) - 所有元素都要往前挪一格，補上索引 0 的空缺
    def shift(self):
        if self.length == 0:
            return None

        first_item = self.data[0]

        # 從索引 1 開始，全部往前覆蓋一格
        for i in range(self.length - 1):
            self.data[i] = self.data[i + 1]

        # 刪除原本最後一個重複的格子
        del self.data[self.length - 1]
        self.length -= 1
        return first_item

JavaScript

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;
  }
}

Java

import java.util.HashMap;
import java.util.Map;

class MyArray {
    private int length;           // 記錄目前陣列的長度
    private Map<Integer, Object> data; // 用 Map 的 key (0, 1, 2...) 來模擬記憶體索引

    public MyArray() {
        this.length = 0;
        this.data = new HashMap<>();
    }

    // 1. 讀取資料：O(1)
    public Object get(int index) {
        return this.data.get(index);
    }

    // 2. 尾端新增：O(1)
    public int push(Object item) {
        this.data.put(this.length, item);
        this.length++;
        return this.length;
    }

    // 3. 尾端刪除：O(1)
    public Object pop() {
        if (this.length == 0) return null;

        Object lastItem = this.data.get(this.length - 1);
        this.data.remove(this.length - 1);
        this.length--;
        return lastItem;
    }

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

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

        Object firstItem = this.data.get(0);

        // 從索引 1 開始，全部往前覆蓋一格
        for (int i = 0; i < this.length - 1; i++) {
            this.data.put(i, this.data.get(i + 1));
        }

        // 刪除原本最後一個重複的格子
        this.data.remove(this.length - 1);
        this.length--;
        return firstItem;
    }
}

常見誤區

• 以為 String 也能像 Array 一樣直接修改：在 JavaScript 與 Python 中，String 都是不可變（Immutable） 的，str[0] = 'x' 這種寫法不會生效，甚至會直接報錯。想修改字串內容，必須用切割、拼接的方式產生一個全新的字串。
• 忽略字串拼接的成本：如果在迴圈裡不斷用 += 拼接字串，每次都會建立一個新的字串物件並複製舊內容，長期下來效能會變差；資料量大時可考慮用陣列先收集片段，最後再用 join('') 一次組合。
• 搞混 index 的起訖範圍：slice(start, end) 這類方法通常是「包含 start、不包含 end」，新手很容易因為差一位（off-by-one）而漏抓或多抓一個元素，動手前建議先用小範例驗證邊界。