跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · 動態陣列

動態陣列

一排連續的格子：用索引讀任何一格都只要一步，但在中間插入就得把後面全部往後搬。

目前的區塊：容量 8，用了 5 格
  1. 3
    0
  2. 1
    1
  3. 4
    2
  4. 1
    3
  5. 5
    4
  6. 5
  7. 6
  8. 7
這次寫入的值被搬動的格子擴容時複製過來已配置但沒用到

一塊容量固定的連續記憶體，前面幾格有資料。試試在尾端加入，直到它塞滿。

長度／容量
5 / 8
這次寫入幾格
–
尾端加入次數
0
平均每次加入寫幾格
–
亮起來的是這一步執行的程式碼
class DynamicArray {
  private data: number[] = new Array(1);
  private length = 0;
 
  get(i: number): number {
    return this.data[i];
  }
 
  push(value: number): void {
    if (this.length === this.data.length) this.grow();
    this.data[this.length] = value;
    this.length++;
  }
 
  insert(index: number, value: number): void {
    if (this.length === this.data.length) this.grow();
    for (let i = this.length; i > index; i--) {
      this.data[i] = this.data[i - 1];
    }
    this.data[index] = value;
    this.length++;
  }
 
  removeAt(index: number): number {
    const value = this.data[index];
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    this.length--;
    return value;
  }
 
  private grow(): void {
    const bigger = new Array(this.data.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.data[i];
    }
    this.data = bigger;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 需要用索引直接讀第幾個，或要依序掃過全部資料。記憶體是連續的，對 CPU 快取最友善。
  • 大部分加入都在尾端。容量滿了就加倍，平均下來每次加入的成本是常數。
  • 資料量小（幾十、幾百個）時，就算要在中間插入，搬一小段連續記憶體通常也比其他結構快。

和其他主題的關係

語言內建的版本

Array<T> · T[]
操作寫法成本
讀第 i 個a[1]O(1)
尾端加入a.push(4)O(1) amortised
尾端移除a.pop()O(1)
插入到 ia.splice(1, 0, 9)O(n)
移除第 i 個a.splice(1, 1)O(n)
找值a.indexOf(3)O(n)
有沒有a.includes(3)O(n)
複製一段a.slice(1, 3)O(k)
排序（數字）nums.sort((x, y) => x - y)O(n log n)
const a = [1, 2, 3];
a[1];                          // → 2
a.push(4);                     // → 4
a.pop();                       // → 4
a.splice(1, 0, 9);             // → []
a;                             // → [1, 9, 2, 3]
a.splice(1, 1);                // → [9]
a.indexOf(3);                  // → 2
a.includes(3);                 // → true
a.slice(1, 3);                 // → [2, 3]
a.at(-1);                      // → 3
 
const b = a;                   // the same array, not a copy
const c = [...a];              // a shallow copy
b.push(5);
a.length;                      // → 4
c.length;                      // → 3
 
const nums = [10, 9, 1];
[...nums].sort();              // → [1, 10, 9]
nums.sort((x, y) => x - y);    // → [1, 9, 10]
 
new Array(3).fill(0);          // → [0, 0, 0]
Array.from("abc");             // → ["a", "b", "c"]
Array.from({ length: 2 }, () => [0, 0]);  // → [[0, 0], [0, 0]]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • sort() 不給比較函式時會把元素轉成字串再比，所以 [10, 9, 1] 會排成 [1, 10, 9]。數字一定要寫 (x, y) => x - y。
  • shift()／unshift()（從頭拿、從頭放）要把後面全部挪一格，是 O(n)。要當佇列用，請看佇列主題。
  • 二維陣列別寫 new Array(3).fill([])：三格會指向同一個陣列。用 Array.from({ length: 3 }, () => [])。

時間與空間複雜度（Big O）

操作平均最差
讀第 i 個O(1)O(1)
尾端加入
均攤 O(1)：只有擴容的那一次要複製全部
O(1)O(n)
在開頭或中間插入O(n)O(n)
刪除開頭或中間O(n)O(n)
刪除尾端O(1)O(1)
找某個值O(n)O(n)

空間：O(n)，容量最多是元素數的兩倍

Big O 實測：n 變大時步數怎麼長

數的是：讀或寫的格子數

Big On = 1,000n = 10,000n = 100,000n = 1,000,000成長倍數：實測（理論）
讀第 i 個O(1)1111×1.0 (×1.0)
尾端加入（平均，含擴容）O(1)2.02.62.32.0×1.0 (×1.0)
在開頭插入O(n)1,00010,000100,0001,000,000×1,000 (×1,000)
找某個值（平均）O(n)4814,80948,084480,836×999 (×1,000)

尾端加入的平均值在 2 到 3 之間跳動，因為取決於 n 離下一次擴容多近；但不管 n 多大，都不會往上長。

和其他做法比

平均最差的一次
讀第 i 格11
尾端加入（寫入格數）2.02513
開頭插入（搬動格數）499.5999
找某個值（看幾格）500.51,000

從空陣列開始做 1,000 次操作實際數出來的。尾端加入最差的那一次要複製 512 個元素，但每次擴容都加倍，平均下來每次加入只寫 2.02 格：這就是「均攤 O(1)」。

真實世界裡的它

  • JavaScript 的 Array、Python 的 list、C++ 的 std::vector、Java 的 ArrayList。
  • 影像的像素、音訊的取樣、GPU 上的張量：都是一大塊連續的陣列。
  • 堆積和雜湊表的底層也是陣列（見上方的關聯）。

取捨與陷阱

  • 在開頭插入或刪除要搬動整排：在迴圈裡反覆 shift() 或 insert(0, …)，整段就從 O(n) 變成 O(n²)。
  • 擴容的那一次很慢（要複製全部）。對延遲敏感的程式可以事先保留容量（例如 C++ 的 reserve）。
  • 擴容後舊的記憶體就被釋放了：C++ 裡指向元素的指標或迭代器，在 push 之後可能變成懸空指標。

LeetCode 練習