一、前言

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

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

那么當(dāng)你定義了數(shù)據(jù)的存儲(chǔ)方式，也就定義了數(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)存空間，來存儲(chǔ)一組具有相同類型數(shù)據(jù)的集合。

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

• 數(shù)組是相同數(shù)據(jù)類型的元素集合（int 不能存放 double）
• 數(shù)組中各元素的存儲(chǔ)是有先后順序的，它們?cè)趦?nèi)存中按照這個(gè)順序連續(xù)存放到一起。內(nèi)存地址連續(xù)。
• 數(shù)組獲取元素的時(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ā)場(chǎng)景中使用到的到不是不多，不過在一些算法邏輯，數(shù)學(xué)計(jì)算中到是可以使用。

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

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

那么本章節(jié)我們就借著數(shù)組結(jié)構(gòu)的學(xué)習(xí)，實(shí)現(xiàn)一個(gè)簡(jiǎ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è)計(jì)

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

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

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

那么什么時(shí)候給初始化的長(zhǎng)度呢？是在首次添加元素的時(shí)候，因?yàn)樗械奶砑釉夭僮?，也都是需要判斷容量，以及是否擴(kuò)容的。那么在 add 添加元素時(shí)統(tǒng)一完成這個(gè)事情，還是比較好處理的。

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

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

這是一份簡(jiǎn)化后的 ArrayList#add 操作

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

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

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

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

3. 移除元素

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

刪除元素

public E remove(int index) {
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 從原始數(shù)組的某個(gè)位置，拷貝到目標(biāo)對(duì)象的某個(gè)位置開始后n個(gè)元素
        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ù)方式移動(dòng)數(shù)據(jù)，把需要?jiǎng)h除的元素位置覆蓋掉。

此外它還會(huì)把已經(jīng)刪除的元素設(shè)置為 null 一方面讓我們不會(huì)在讀取到這個(gè)元素，另外一方面也是為了 GC

4. 獲取元素

public E get(int index) {
    return (E) elementData[index];
}
@Override
public String toString() {
    return "ArrayList{" +
            "elementData=" + Arrays.toString(elementData) +
            ", size=" + size +
            '}';
}

獲取元素就比較簡(jiǎn)單了，直接從 elementData 使用索引直接獲取即可。這個(gè)是一個(gè) O(1) 操作。也正因?yàn)樗阉髟氐谋憬菪?，才?ArrayList 使用的那么廣泛。同時(shí)為了兼容可以通過元素來獲取數(shù)據(jù)，而不是直接通過下標(biāo)，引出了 HashMap 使用哈希值計(jì)算下標(biāo)的計(jì)算方式，也引出了斐波那契散列。它們的設(shè)計(jì)都是在盡可能減少元素碰撞的情況下，盡可能使用貼近 O(1) 的時(shí)間復(fù)雜度獲取數(shù)據(jù)。這些內(nèi)容的學(xué)習(xí)可以閱讀小傅哥的《Java面經(jīng)手冊(cè)》也可以隨著本系列章節(jié)內(nèi)容的鋪設(shè)逐步覆蓋到算法后進(jìn)行學(xué)習(xí)

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

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

測(cè)試結(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

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

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