概念

Dynamic Array 的背後概念就是將原本 Array 再複製一個兩倍大小的新的 Array 出來
指向舊 Array 的指標變成指到新的 Array

在很多程式語言中都有支援動態陣列的型態

  • C++ (vector)
  • JAVA (ArrayList)
  • Python (list), 在 Python 中只有 list 這種型態的 Array 能使用

DynamicArray1

DynamicArray2

複製到新的 Array，dispose 舊的 Array
DynamicArray3

pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PushBack(val)
  // 如果原本的array滿了
  if size = capacity:
    allocate new_arr[2*capacity]  // 宣告一個比原本大一倍的array
    
    for i from 0 to size-1:
      new_arr[i] ← arr[i]
    
    free arr         
    arr ← new_arr;   // 指到新的array
    capacity ← 2 * capacity   // 更新capacity

  // 放入新的元素
  arr[size] ← val
  size ← size + 1

要從一個 Array 移除某個元素，如果此元素不是最後一個，要將此元素後面的全部元素都往前放，時間複雜度趨近 O(n)

1
2
3
4
5
6
7
Remove(index)
  if index < 0 or index >= size:
    ERROR: index out of range
  
  for j from index to size-2:
    arr[j] ← arr[j+1]
  size ← size - 1

延伸

新增資料到 Dynamic array 通常是 constant time O(1)，但在 worst case 下會是 O(n) [目前capacity滿的時候]，有時也會浪費空間，比如今天只是要多新增一個元素但剛好目前 Array 已經滿了，會複製一倍新的 Array 出來，如果原本已經有 1024bytes，複製完變 2048bytes，實際卻只使用 1028bytes

要解決上述問題需要用到 “Amortized Analysis (runtime analysis)”

這部份當初聽課時沒有很懂OTZ，這邊只陳列有記錄到的幾個名詞

  1. Aggregate Method
  2. Banker’s Method (tokens) : 每次都存一份複本，當capacity不夠時需要複製新的Array就不必跑迴圈一個一個複製
  3. Physicist’s Method (Potential Function)

這個國外的CS課程網頁對於Amortized Analysis有較詳細的解說