索引 (Index)

相較於列表 (List)分散儲存於各個記憶體區塊，陣列則是將所有數據排在連續區塊。 不透過指標存取數據，而是透過索引存取 (由 0 開始)，因此要存取 Red 則是透過 a[2]

陣列中，數據需要連續儲存於記憶體中

隨機存取 (random access)

因為數據被連續儲存，所以能透過索引來存取各數據，例如 a[2] 存取 Red

雖然數據讀取上較 List 方便，但是在增加數據或刪除數據上則須付出相當代價…

增加數據

例如要新增 Green 到 a[1]，則必須先確保陣列還要足夠空間新增，並且依序將 Red、Yellow 往後移動

p.s 記得，所有數據在記憶體區塊中必連續儲存

刪除數據

反之，要將 Green 從 a[1] 移除，則刪除 Green 後，依序將 Yellow、Red 往前移動最後刪除多餘的儲存空間

執行時間討論 (以 大O符號 表示)

1. 使用陣列內的數據的執行時間
   因為能隨機存取，不受陣列中的 n 個數據影響，所以為常數時間 O(1)
2. 新增數據
   需將指定位置的數據往後移動，當陣列最前端追加數據時，故為 O(n)
3. 刪除數據
   當刪除數據在陣列最前端時，同樣需耗費時間 O(n)

列表 vs 陣列

可以簡單整理出以下表格，列表適合新增/刪除數據；陣列則適合存取數據。因此需視情況選定使用列表或是陣列

Java 的實作

在 Java 有個類別叫做 ArrayList，實際上這個類別是透過陣列的方式實作 List
參考 OpenJDK 的 ArrayList source code 即可發現透過陣列儲存

存取數據 get 方法

elementData 方法實際上即是透過索引直接存取陣列中的元素

1
2
3
4
5
6
7
8

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

新增數據 add 方法

ensureCapacityInternal 即是用來確保內部陣列仍有足夠空間新增數據，當陣列長度不足時，會透過 Arrays.copyOf 方法產生新的陣列

1
2
3
4
5

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

刪除數據 remove 方法

透過 System.arraycopy 將刪去元素後面的元素逐一往前移動

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

ArrayList 內部採用陣列方式實作，因此是不利於新增或刪除數據的
(若有新增/刪除數據的需求應該使用 LinkedList，兩者實作方式完全不同，可參考 LinkedList source code)