[algorithms] Array 陣列

視覺化概覽

graph LR
    subgraph 連續記憶體空間
        A0["[0] 10"] --- A1["[1] 20"] --- A2["[2] 30"] --- A3["[3] 40"] --- A4["[4] 50"]
    end
    IDX["index 2"] -.->|"O(1) 隨機存取"| A2
    style A2 fill:#f9f,stroke:#333,stroke-width:2px
    style IDX fill:#fff,stroke:#333,stroke-dasharray: 5 5

💡 白話版：Array 就像一排有編號的儲物櫃。你知道第幾號就能直接開，不用一個一個找。

什麼是陣列？

陣列就是一排連續的格子，每個格子都有編號（index），可以直接跳到任何一格。

Index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
Data:   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+

核心特性

特性	說明
連續記憶體	所有元素在記憶體中是連在一起的
固定大小	建立時就決定大小，之後不能改
隨機存取	知道 index 就能立刻找到，不用從頭找

操作與時間複雜度

操作	時間複雜度	為什麼？
讀取 get(i)	O(1)	直接跳到第 i 格
修改 set(i, val)	O(1)	直接改第 i 格
尾端新增	O(1)*	直接放最後面
中間插入	O(n)	後面的元素都要往後移
中間刪除	O(n)	後面的元素都要往前移
搜尋	O(n)	最差要從頭找到尾

*平均 O(1)，擴容時 O(n)

插入操作圖解

在 index 1 插入 15：

原本:  [10, 20, 30, 40]
        0   1   2   3

Step 1: 把 index 1 之後的元素往後移
       [10, __, 20, 30, 40]
        0   1   2   3   4

Step 2: 把 15 放進 index 1
       [10, 15, 20, 30, 40]
        0   1   2   3   4

刪除操作圖解

刪除 index 1 的元素：

原本:  [10, 15, 20, 30, 40]
        0   1   2   3   4

Step 1: 把 index 1 之後的元素往前移
       [10, 20, 30, 40, __]
        0   1   2   3   4

Step 2: 縮小 size
       [10, 20, 30, 40]
        0   1   2   3

動態陣列 (Dynamic Array)

普通陣列的問題：大小固定，不能變

解決方案：當空間不夠時，建立一個更大的陣列（通常是 2 倍），把資料搬過去。

原本容量 4，已滿:
[10, 20, 30, 40]

新增一個元素，觸發擴容:
1. 建立容量 8 的新陣列
2. 複製舊資料過去
3. 新增新元素

[10, 20, 30, 40, 50, __, __, __]

這就是 Java ArrayList 的原理！

什麼時候用陣列？

適合用：

• 需要頻繁用 index 存取資料
• 資料量固定或變動不大
• 需要快速讀取、修改

不適合用：

• 頻繁在中間插入、刪除
• 資料量變動很大
• 不知道會有多少資料

相關檔案

• Java 實作：DynamicArray.java
• 視覺化：array.html