數組 Array

一、前言

數組是數據結構還是數據類型？

數組只是個名稱，它可以描述一組操作，也可以命名這組操作。數組的數據操作，是通過 idx->val 的方式來處理。它不是具體要求內存上要存儲著連續的數據才叫數據，而是說，通過連續的索引 idx，也可以線性訪問相鄰的數據。

那么當你定義了數據的存儲方式，也就定義了數據結構。所以它也是被歸類為數據結構。

二、數組數據結構

數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型數據的集合。

數組的特點：

1. 數組是相同數據類型的元素集合（int 不能存放 double）
2. 數組中各元素的存儲是有先后順序的，它們在內存中按照這個順序連續存放到一起。內存地址連續。
3. 數組獲取元素的時間復雜度為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/tree/main/data-structures/src/main/java/array_list

1. 基本設計

數組是一個固定的、連續的、線性的數據結構，那么想把它作為一個自動擴展容量的數組列表，則需要做一些擴展。

/*** 默認初始化空間*/
private static final int DEFAULT_CAPACITY = 10;
/*** 空元素*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/*** ArrayList 元素數組緩存區*/
transient Object[] elementData;

1. 初始化 ArrayList 階段，如果不指定大小，默認會初始化一個空的元素。這個時候是沒有默認長度的。
2. 那么什么時候給初始化的長度呢？是在首次添加元素的時候，因為所有的添加元素操作，也都是需要判斷容量，以及是否擴容的。那么在 add 添加元素時統一完成這個事情，還是比較好處理的。
3. 之后就是隨著元素的添加，容量是會不足的。當容量不足的是，需要進行擴容操作。同時還得需要把舊數據遷移到新的數組上。所以數據的遷移算是一個比較耗時的操作

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 操作

1. 判斷當前容量與初始化容量，使用 Math.max 函數取最大值最為最小初始化空間。
2. 接下來是判斷 minCapacity 和元素的數量，是否達到了擴容。首次創建 ArrayList 是一定會擴容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。
3. Arrays.copyOf 實際上是創建一個新的空間數組，之后調用的 System.arraycopy 遷移到新創建的數組上。這樣后續所有的擴容操作，也就都保持統一了。
4. 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 workreturn 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的元素被刪除前后，元素的遷移變化。

六、常見面試問題

1. 數據結構中有哪些是線性表數據結構？
2. 數組的元素刪除和獲取，時間復雜度是多少？
3. ArrayList 中默認的初始化長度是多少？
4. ArrayList 中擴容的范圍是多大一次？
5. ArrayList 是如何完成擴容的，System.arraycopy 各個入參的作用是什么？