一、前言

數(shù)組是數(shù)據(jù)結(jié)構(gòu)還是數(shù)據(jù)類型？

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

那么當(dāng)你定義了數(shù)據(jù)的存儲方式，也就定義了數(shù)據(jù)結(jié)構(gòu)。所以它也是被歸類為數(shù)據(jù)結(jié)構(gòu)。

二、數(shù)組數(shù)據(jù)結(jié)構(gòu)

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型數(shù)據(jù)的集合。

數(shù)組的特點(diǎn)：

• 數(shù)組是相同數(shù)據(jù)類型的元素集合（int 不能存放 double）
• 數(shù)組中各元素的存儲是有先后順序的，它們在內(nèi)存中按照這個順序連續(xù)存放到一起。內(nèi)存地址連續(xù)。
• 數(shù)組獲取元素的時間復(fù)雜度為O(1)

1. 一維數(shù)組

一維數(shù)組是最常用的數(shù)組，其他很多數(shù)據(jù)結(jié)構(gòu)的變種也都是從一維數(shù)組來的。例如 HashMap 的拉鏈尋址結(jié)構(gòu)，ThreadLocal 的開放尋址結(jié)構(gòu)，都是從一維數(shù)組上實(shí)現(xiàn)的。

2. 二維數(shù)組

二維以及多維數(shù)組，在開發(fā)場景中使用到的到不是不多，不過在一些算法邏輯，數(shù)學(xué)計算中到是可以使用。

三、實(shí)現(xiàn)數(shù)組列表

在 Java 的源碼中，數(shù)組是一個非常常用的數(shù)據(jù)結(jié)構(gòu)，很多其他數(shù)據(jù)結(jié)構(gòu)也都有數(shù)組的影子。在一些數(shù)據(jù)存放和使用的場景中，基本也都是使用 ArrayList 而不是 LinkedList，具體性能分析參考：LinkedList插入速度比ArrayList快？你確定嗎？

那么本章節(jié)我們就借著數(shù)組結(jié)構(gòu)的學(xué)習(xí)，實(shí)現(xiàn)一個簡單的 ArrayList，讓使用 Java 的讀者既能了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，也能了解到 Java 源碼實(shí)現(xiàn)。

• 源碼地址：https://github.com/fuzhengwei/java-algorithms -Java 算法與數(shù)據(jù)結(jié)構(gòu)
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/array/ArrayList.java

1. 基本設(shè)計

數(shù)組是一個固定的、連續(xù)的、線性的數(shù)據(jù)結(jié)構(gòu)，那么想把它作為一個自動擴(kuò)展容量的數(shù)組列表，則需要做一些擴(kuò)展。

/**
 * 默認(rèn)初始化空間
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 空元素
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * ArrayList 元素數(shù)組緩存區(qū)
 */
transient Object[] elementData;

初始化 ArrayList 階段，如果不指定大小，默認(rèn)會初始化一個空的元素。這個時候是沒有默認(rèn)長度的。

那么什么時候給初始化的長度呢？是在首次添加元素的時候，因?yàn)樗械奶砑釉夭僮鳎捕际切枰袛嗳萘浚约笆欠駭U(kuò)容的。那么在 add 添加元素時統(tǒng)一完成這個事情，還是比較好處理的。

之后就是隨著元素的添加，容量是會不足的。當(dāng)容量不足的是，需要進(jìn)行擴(kuò)容操作。同時還得需要把舊數(shù)據(jù)遷移到新的數(shù)組上。所以數(shù)據(jù)的遷移算是一個比較耗時的操作

2. 添加元素

public boolean add(E e) {
    // 確保內(nèi)部容量
    int minCapacity = size + 1;
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 判斷擴(kuò)容操作
    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 操作

判斷當(dāng)前容量與初始化容量，使用 Math.max 函數(shù)取最大值最為最小初始化空間。

接下來是判斷 minCapacity 和元素的數(shù)量，是否達(dá)到了擴(kuò)容。首次創(chuàng)建 ArrayList 是一定會擴(kuò)容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。

Arrays.copyOf 實(shí)際上是創(chuàng)建一個新的空間數(shù)組，之后調(diào)用的 System.arraycopy 遷移到新創(chuàng)建的數(shù)組上。這樣后續(xù)所有的擴(kuò)容操作，也就都保持統(tǒng)一了。

ArrayList 擴(kuò)容完成后，就是使用 elementData[size++] = e; 添加元素操作了。

3. 移除元素

ArrayList 的重點(diǎn)離不開對 System.arraycopy 的使用，它是一個本地方法，可以讓你從原數(shù)組的特定位置，遷移到新數(shù)組的指定位置和遷移數(shù)量。如圖 2-5 所示，數(shù)據(jù)遷移 測試代碼在 java-algorithms

刪除元素

public E remove(int index) {
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 從原始數(shù)組的某個位置，拷貝到目標(biāo)對象的某個位置開始后n個元素
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

ArrayList 的元素刪除，就是在確定出元素位置后，使用 System.arraycopy 拷貝數(shù)據(jù)方式移動數(shù)據(jù)，把需要刪除的元素位置覆蓋掉。

此外它還會把已經(jīng)刪除的元素設(shè)置為 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) 操作。也正因?yàn)樗阉髟氐谋憬菪裕抛?ArrayList 使用的那么廣泛。同時為了兼容可以通過元素來獲取數(shù)據(jù)，而不是直接通過下標(biāo)，引出了 HashMap 使用哈希值計算下標(biāo)的計算方式，也引出了斐波那契散列。它們的設(shè)計都是在盡可能減少元素碰撞的情況下，盡可能使用貼近 O(1) 的時間復(fù)雜度獲取數(shù)據(jù)。這些內(nèi)容的學(xué)習(xí)可以閱讀小傅哥的《Java面經(jīng)手冊》也可以隨著本系列章節(jié)內(nèi)容的鋪設(shè)逐步覆蓋到算法后進(jìn)行學(xué)習(xí)

四、數(shù)組列表測試

@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);
}

測試結(jié)果

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

測試案例中包括了在我們自己實(shí)現(xiàn)的 ArrayList 中順序添加元素，逐步測試擴(kuò)容遷移元素，以及刪除元素后數(shù)據(jù)的遷移。

最終的測試結(jié)果可以看到，一共有12個元素，其中idx=9的元素被刪除前后，元素的遷移變化。