讓我們一起聊聊什么是數組？
一、前言
數組是數據結構還是數據類型？
數組只是個名稱，它可以描述一組操作，也可以命名這組操作。數組的數據操作，是通過 idx->val 的方式來處理。它不是具體要求內存上要存儲著連續的數據才叫數據，而是說，通過連續的索引 idx，也可以線性訪問相鄰的數據。
那么當你定義了數據的存儲方式，也就定義了數據結構。所以它也是被歸類為數據結構。
二、數組數據結構
數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型數據的集合。
數組的特點：
- 數組是相同數據類型的元素集合（int 不能存放 double）
- 數組中各元素的存儲是有先后順序的，它們在內存中按照這個順序連續存放到一起。內存地址連續。
- 數組獲取元素的時間復雜度為O(1)
1. 一維數組
一維數組是最常用的數組，其他很多數據結構的變種也都是從一維數組來的。例如 HashMap 的拉鏈尋址結構，ThreadLocal 的開放尋址結構，都是從一維數組上實現的。
2. 二維數組
二維以及多維數組，在開發場景中使用到的到不是不多，不過在一些算法邏輯，數學計算中到是可以使用。
三、實現數組列表
在 Java 的源碼中，數組是一個非常常用的數據結構，很多其他數據結構也都有數組的影子。在一些數據存放和使用的場景中，基本也都是使用 ArrayList 而不是 LinkedList，具體性能分析參考：LinkedList插入速度比ArrayList快？你確定嗎？
那么本章節我們就借著數組結構的學習，實現一個簡單的 ArrayList，讓使用 Java 的讀者既能了解學習數據結構，也能了解到 Java 源碼實現。
- 源碼地址：https://github.com/fuzhengwei/java-algorithms -Java 算法與數據結構
- 本章源碼：https://github.com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/array/ArrayList.java
1. 基本設計
數組是一個固定的、連續的、線性的數據結構，那么想把它作為一個自動擴展容量的數組列表，則需要做一些擴展。
/**
* 默認初始化空間
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空元素
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList 元素數組緩存區
*/
transient Object[] elementData;
初始化 ArrayList 階段，如果不指定大小，默認會初始化一個空的元素。這個時候是沒有默認長度的。
那么什么時候給初始化的長度呢？是在首次添加元素的時候，因為所有的添加元素操作，也都是需要判斷容量，以及是否擴容的。那么在 add 添加元素時統一完成這個事情，還是比較好處理的。
之后就是隨著元素的添加，容量是會不足的。當容量不足的是，需要進行擴容操作。同時還得需要把舊數據遷移到新的數組上。所以數據的遷移算是一個比較耗時的操作
2. 添加元素
public boolean add(E e) {
// 確保內部容量
int minCapacity = size + 1;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 判斷擴容操作
if (minCapacity - elementData.length > 0) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 添加元素
elementData[size++] = e;
return true;
}
這是一份簡化后的 ArrayList#add 操作
判斷當前容量與初始化容量，使用 Math.max 函數取最大值最為最小初始化空間。
接下來是判斷 minCapacity 和元素的數量，是否達到了擴容。首次創建 ArrayList 是一定會擴容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。
Arrays.copyOf 實際上是創建一個新的空間數組，之后調用的 System.arraycopy 遷移到新創建的數組上。這樣后續所有的擴容操作，也就都保持統一了。
ArrayList 擴容完成后，就是使用 elementData[size++] = e; 添加元素操作了。
3. 移除元素
ArrayList 的重點離不開對 System.arraycopy 的使用，它是一個本地方法，可以讓你從原數組的特定位置，遷移到新數組的指定位置和遷移數量。如圖 2-5 所示，數據遷移 測試代碼在 java-algorithms
刪除元素
public E remove(int index) {
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
// 從原始數組的某個位置，拷貝到目標對象的某個位置開始后n個元素
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
ArrayList 的元素刪除，就是在確定出元素位置后，使用 System.arraycopy 拷貝數據方式移動數據，把需要刪除的元素位置覆蓋掉。
此外它還會把已經刪除的元素設置為 null 一方面讓我們不會在讀取到這個元素，另外一方面也是為了 GC
4. 獲取元素
public E get(int index) {
return (E) elementData[index];
}
@Override
public String toString() {
return "ArrayList{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}獲取元素就比較簡單了，直接從 elementData 使用索引直接獲取即可。這個是一個 O(1) 操作。也正因為搜索元素的便捷性，才讓 ArrayList 使用的那么廣泛。同時為了兼容可以通過元素來獲取數據，而不是直接通過下標，引出了 HashMap 使用哈希值計算下標的計算方式，也引出了斐波那契散列。它們的設計都是在盡可能減少元素碰撞的情況下，盡可能使用貼近 O(1) 的時間復雜度獲取數據。這些內容的學習可以閱讀小傅哥的《Java面經手冊》也可以隨著本系列章節內容的鋪設逐步覆蓋到算法后進行學習
四、數組列表測試
@Test
public void test_array_list() {
cn.bugstack.algorithms.data.array.List<String> list = new ArrayList<>();
list.add("01");
list.add("02");
list.add("03");
list.add("04");
list.add("05");
list.add("06");
list.add("07");
list.add("08");
list.add("09");
list.add("10");
list.add("11");
list.add("12");
System.out.println(list);
list.remove(9);
System.out.println(list);
}
測試結果
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size=12}
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size=11}
Process finished with exit code 0
測試案例中包括了在我們自己實現的 ArrayList 中順序添加元素，逐步測試擴容遷移元素，以及刪除元素后數據的遷移。
最終的測試結果可以看到，一共有12個元素，其中idx=9的元素被刪除前后，元素的遷移變化。
