目錄

• 動態陣列的資料結構的實作程序（Java 實作）
  • 陣列基礎簡單回顧
  • 二次封裝陣列類設計
    • 基本設計
    • 向陣列中添加元素
      • 向陣列末尾添加元素
      • 向陣列指定索引位置添加元素
    • 在陣列中查詢元素和修改元素
    • 陣列中的包含、搜索和洗掉元素
    • 使用泛型使該類更加通用（能夠存放 “任意” 資料型別的資料）
    • 升級為動態陣列
      • 當陣列空間滿的時候進行擴容
      • 當陣列空間少到一定程度時進行減容
    • 簡單的時間復雜度分析與一些改進
      • 對于添加操作的時間復雜度分析
      • 對于洗掉操作的時間復雜度分析
      • 對于修改操作的時間復雜度分析
      • 對于查找操作的時間復雜度分析

動態陣列的資料結構的實作程序（Java 實作）

陣列基礎簡單回顧

1. 陣列是一種資料結構，用來存盤同一型別值的集合，

2. 陣列就是存盤資料長度固定的容器，保證多個資料的資料型別要一致，

3. 陣列是一種參考資料型別，

4. 簡單來說，陣列就是把需要存盤的資料排成一排進行存放，

5. 陣列的索引從 0 開始計數，最后一個位置的索引是陣列的長度(n) - 1（即 n - 1），

6. 可以借助陣列的索引來存取資料，

7. 陣列的索引可以有語意，也可以沒有語意，

   例如，一個存盤學生成績的陣列如果索引有語意，那么索引可以看成學生的學號，此時對于使用索引操作陣列就可以看成對學號是 xxx 的學生進行存取成績的操作，那么如果沒有語意，就是隨意存取學生的成績到該陣列中，

8. 陣列最大的優點：快速查詢，例如：array[index]，

   根據此優點，可以知道陣列最好應用于 “索引有語意” 的情況，因為索引有了語意，那么我們就可以知道要取的資料是什么、是在哪個位置，可以很方便地查詢到資料，
   
   但也并非是所有有語意的索引都適用于陣列，例如身份證號，我們知道，一個身份證號的號碼有 18 位的長度，如果索引為一個身份證號，其對應著一個人，那么陣列就要開啟很大的空間，簡單說就是要開啟空間到一個索引能有 18 位長度的數字這么大，那么此時如果只存取幾個人，空間就會很浪費，而且這么多空間里并不是每一個索引都能是一個身份證號，有些是和身份證號的格式對應不上的，這些空間就會被浪費，所以并非是所有有語意的索引都適用于陣列，要根據情況來決定使用，

9. 陣列也可以處理“索引沒有語意”的情況，比如一個陣列有 10 個空間，其中前 4 個空間有資料，此時索引沒有語意，對于用戶而言，后面的空間是沒有元素的，那么此時如何處理我們需要進行考慮，所以我們可以根據 Java 的靜態陣列來二次封裝一個陣列類來進行處理 ”索引沒有語意” 的情況，以此掌握陣列這個資料結構，

二次封裝陣列類設計

基本設計

這里我將這個封裝的陣列類取名為 Array，其中封裝了一個 Java 的靜態陣列 data[] 變數，然后基于這個 data[] 進行二次封裝實作增、刪、改、查的操作，接下來將一一實作，

由于陣列本身是靜態的，在創建的時候需指定大小，此時我將這個大小用變數 capacity 表示，即容量，表示陣列空間最多裝幾個元素，但并不需要在類中宣告，只需在建構式的引數串列中宣告即可，因為陣列的容量也就是 data[] 的長度，不需要再宣告一個變數來進行維護，

對于陣列中實際擁有的元素個數，這里我用變數 size 來表示，初始時其值為 0，

這個 size 也能表示為 陣列中第一個沒有存放元素的位置，

例如陣列為空時，size 為 0，此時索引 0 處為陣列中第一個沒有存放元素的位置；再如陣列中有兩個元素時，size 為 2，此時索引 0 和 1 處都有元素，索引 2 處沒有，也就是陣列中第一個沒有存放元素的位置，

所以可先創建 Array 類如下所示：

/**
 * 基于靜態陣列封裝的陣列類
 *
 * @author 踏雪彡尋梅
 * @date 2019-12-17 - 22:26
 */
public class Array {
    /**
     * 靜態陣列 data,基于該陣列進行封裝該陣列類
     * data 的長度對應其容量
     */
    private int[] data;

    /**
     * 陣列當前擁有的元素個數
     */
    private int size;

    /**
     * 默認建構式,用戶不知道要創建多少容量的陣列時使用
     * 默認創建容量為 10 的陣列
     */
    public Array() {
        // 默認創建容量為 10 的陣列
        this(10);
    }

    /**
     * 建構式,傳入陣列的容量 capacity 構造 Array
     * 
     * @param capacity 需要開辟的陣列容量,由用戶指定
     */
    public Array(int capacity) {
        // 初始化 data[] 和 size
        data = https://www.cnblogs.com/txxunmei/p/new int[capacity];
        size = 0;
    }

    /**
     * 獲得陣列當前的元素個數
     * 
     * @return 回傳陣列當前的元素個數
     */
    public int getSize() {
        return size;
    }

    /**
     * 獲得陣列的容量
     * 
     * @return 回傳陣列的容量
     */
    public int getCapacity() {
        // data[] 的長度對于其容量
        return data.length;
    }

    /**
     * 判斷陣列是否為空
     * 
     * @return 陣列為慷訓傳 true;否則回傳 false
     */
    public boolean isEmpty() {
        // 當前 data[] 的元素個數為 0 代表陣列為空,否則非空
        return size == 0;
    }
}

向陣列中添加元素

向陣列末尾添加元素

對于向陣列中添加元素，向陣列末尾添加元素是最簡單的，原理如下：

顯而易見，往陣列末尾添加元素是添加操作中最簡單的操作，因為我們已經知道 size 這個變數指向的是陣列第一個沒有元素的地方，很容易理解，size 這個位置就是陣列末尾的位置，所以往這個位置添加元素時也就是往陣列末尾添加元素了，添加后維護 size 的值將其加一即可，添加時也需要注意陣列空間是否已經滿了，

添加程序如下圖所示：

用代碼來表示就如下所示：

/**
 * 向陣列末尾添加一個新元素
 * 
 * @param element 添加的新元素
 */
public void addLast(int element) {
    // 檢查陣列空間是否已滿
    if (size == data.length) {
        throw new IllegalArgumentException("向陣列末尾添加元素失敗, 陣列已滿!");
    }
    // 在陣列末尾添加新元素
    data[size] = element;
    // 添加后維護 size 變數
    size++;
}

向陣列指定索引位置添加元素

當然，也不能總是往陣列末尾添加元素，當用戶有往指定索引位置添加元素的需求時，也要將其實作，

對于往指定索引位置添加元素，首先需要做的便是將該索引位置及其后面所有的元素都往后面移一個位置，將這個索引位置空出來，

需要注意：并不是真的空出來，這個位置如果之前有元素的話還是存在原來的元素，只不過是為原來元素制作了一個副本并將其往后移動了一個位置，

其次再將元素添加到該索引位置，

如果這個位置之前有元素的話實質上就是將新元素覆寫到原來的元素上，

最后再維護存盤陣列當前元素個數的變數 size 將其值加一，

當然在插入的時候也要確認陣列是否有足夠的空間以及確認插入的索引位置是否合法（該位置的合法值應該為 0 到 size 這個范圍），

具體程序如下圖所示：

用代碼來表示該程序就如下所示：

/**
 * 在陣列的 index 索引處插入一個新元素 element
 * 
 * @param index 要插入元素的索引
 * @param element 要插入的新元素
 */
public void add(int index, int element) {
    // 檢查陣列空間是否已滿
    if (size == data.length) {
        throw new IllegalArgumentException("向陣列指定索引位置添加元素失敗, 陣列已滿!");
    }

    // 檢查 index 是否合法
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("向陣列指定索引位置添加元素失敗, index 應在 [0, size] 范圍中!");
    }

    // 將 index 及其后面所有的元素都往后面移一個位置
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }

    // 將新元素 element 添加到 index 位置
    data[index] = element;
	
    // 維護 size 變數
    size++;
}

在實作上面方法之后，對于之前實作的 addLast 方法又可以進行簡化了，只需在其中復用 add 方法，將 size 變數和要添加的元素變數 element 傳進去即可，如下所示：

/**
 * 向陣列末尾添加一個新元素
 * 
 * @param element 添加的新元素
 */
public void addLast(int element) {
	// 復用 add 方法實作該方法
    add(size, element);
}

同理，也可再依此實作一個方法實作往陣列首部添加一個新元素，如下所示：

/**
 * 在陣列首部添加一個新元素
 * 
 * @param element 添加的新元素
 */
public void addFirst(int element) {
	// 復用 add 方法實作該方法
    add(0, element);
}

至此，對于添加操作的基本實作，已經撰寫完成，接下來就接著實作在陣列中查詢元素和修改元素這兩個操作，

在陣列中查詢元素和修改元素

查詢元素時我們需要直觀地知道陣列中的資訊，所以在查詢元素和修改元素之前需要先重寫 toString 方法，以讓后面我們可以直觀地看到陣列中的資訊，實作如下：

/**
 * 重寫 toString 方法,顯示陣列資訊
 * 
 * @return 回傳陣列中的資訊
 */
@Override
public String toString() {
    StringBuilder arrayInfo = new StringBuilder();

    arrayInfo.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));

    arrayInfo.append("[");
    for (int i = 0; i < size; i++) {
        arrayInfo.append(data[i]);
        
        // 判斷是否為最后一個元素
        if (i != size - 1) {
            arrayInfo.append(", ");
        }
    }
    arrayInfo.append("]");

    return arrayInfo.toString();
}

那么接下來就可以開始實作這些操作了:

首先先實作查詢的方法, 這里實作一個獲取指定索引位置的元素的方法提供給用戶用于查詢指定位置的元素，

對于這個方法，我們知道這個類是基于一個靜態陣列 data[] 進行封裝的，那么對于獲取指定索引位置的元素，我們只需使用 data[index] 就可獲取到相應的元素，并且對用戶指定的索引位置 index 進行合法性檢測即可，

同時，對于 data 我們之前已經做了 private 處理，那么使用該方法來封裝獲取元素的操作也可以避免用戶直接對 data 進行操作，并且在此方法中進行了 idnex 的合法性檢測，那么對于用戶而言，對于陣列中未使用的空間，他們是永遠訪問不到的，這保證了資料的安全，他們只需知道陣列中已使用的空間中的元素能夠進行訪問即可，

具體代碼實作如下：

/**
 * 獲取 index 索引位置的元素
 * 
 * @param index 要獲取元素的索引位置
 * @return 回傳用戶指定的索引位置處的元素
 */
public int get(int index) {
    // 檢查 index 是否合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("獲取 index 索引位置的元素失敗, index 應在 [0, size) 范圍中!");
    }

    // 回傳用戶指定的索引位置處的元素
    return data[index];
}

同理，可以實作修改元素的方法如下：

/**
* 修改 index 索引位置的元素為 element
* 
* @param index 用戶指定的索引位置
* @param element 要放到 index 處的元素
*/
public void set(int index, int element) {
    // 檢查 index 是否合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("修改 index 索引位置的元素為指定元素失敗, index 應在 [0, size) 范圍中!");
    }

    // 修改 index 索引位置的元素為 element
    data[index] = element;
}

該方法實作的內容則是修改指定位置的老元素為新元素，同樣也進行了 index 的合法性檢測，對于用戶而言是修改不了陣列的那些未使用的空間的，

實作了以上方法，就可以接著實作陣列中的包含、搜索和洗掉這些方法了，

陣列中的包含、搜索和洗掉元素

在很多時候，我們在陣列中存盤了許多元素，有時需要知道這些元素中是否包含了某個元素，這時候就要實作一個方法來判斷陣列中是否包含我們需要的元素了，

對于該方法，實作起來也很容易，只需遍歷整個陣列，逐一判斷是否包含有需要的元素即可，實作如下：

/**
 * 查找陣列中是否有元素 element
 * 
 * @param element 用戶需要知道是否存在于陣列中的元素
 * @return 如果陣列中包含有 element 則回傳 true;否則回傳 false
 */
public boolean contains(int element) {
    // 遍歷陣列,逐一判斷
    for (int i = 0; i < size; i++) {
        if (data[i] == element) {
            return true;
        }
    }

    return false;
}

不過有些時候用戶不僅需要知道陣列中是否包含需要的元素，還需要知道其所在的索引位置處，這時候就要實作一個方法來搜索用戶想要知道的元素在陣列中的位置了，

對于這個方法，具體實作和上面的包含方法差不多，也是遍歷整個陣列然后逐一判斷，不同的是如果存在需要的元素則是回傳該元素的索引，如果不存在則回傳 -1 表示沒有找到，實作如下：

/**
 * 查找陣列中元素 element 所在的索引
 * 
 * @param element 進行搜索的元素
 * @return 如果元素 element 存在則回傳其索引;不存在則回傳 -1
 */
public int find(int element) {
    // 遍歷陣列,逐一判斷
    for (int i = 0; i < size; i++) {
        if (data[i] == element) {
            return i;
        }
    }

    return -1;
}

最后，則實作在陣列中洗掉元素的方法，先實作洗掉指定位置元素的方法，

對于洗掉指定位置元素這個方法，其實和之前實作的在指定位置添加元素的方法的思路差不多，只不過反轉了過來，

對于洗掉來說，只需從指定位置后一個位置開始，把指定位置后面的所有元素一一往前移動一個位置覆寫前面的元素，最后再維護 size 將其值減一并且回傳洗掉的元素，就完成了洗掉指定位置的元素這個操作了，當然也需要進行指定位置的合法性判斷，

此時完成了洗掉之后，雖然 size 處還可能含有洗掉之前的陣列的最后一個元素或者含有陣列的默認值，（創建陣列時，每個位置都有一個默認值 0），但對用戶而言，這個資料他們是拿不到的，因為對于獲取元素的方法，已經設定了 index 的合法性檢測，其中限制了 index 的范圍為大于等于 0 且小于 size，所以 size 這個位置的元素用戶是取不到的，綜上該位置如含有之前的元素是不影響接下來的操作的，

洗掉指定位置元素的具體程序圖示如下：

代碼實作如下：

/**
 * 從陣列中洗掉 index 位置的元素并且回傳洗掉的元素
 * 
 * @param index 要洗掉元素的索引
 * @return 回傳洗掉的元素
 */
public int remove(int index) {
    // 檢查 index 是否合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("洗掉指定位置的元素失敗, index 應在 [0, size) 范圍中!");
    }

    // 存盤待洗掉的元素,以便回傳
    int removeElement = data[index];

    // 進行洗掉
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    // 維護 size
    size--;

    // 回傳洗掉的元素
    return removeElement;
}

實作了洗掉指定位置的元素的方法之后，我們可以根據該方法再衍生出兩個簡單的方法：洗掉陣列中第一個元素的方法、洗掉陣列中最后一個元素的方法，實作如下：

洗掉陣列中第一個元素：

/**
 * 從陣列中洗掉第一個元素并且回傳洗掉的元素
 * 
 * @return 回傳洗掉的元素
 */
public int removeFirst() {
    // 復用 remove 方法實作該方法
    return remove(0);
}

洗掉陣列中最后一個元素：

/**
 * 從陣列中洗掉最后一個元素并且回傳洗掉的元素
 * 
 * @return 回傳洗掉的元素
 */
public int removeLast() {
    // 復用 remove 方法實作該方法
    return remove(size - 1);
}

還可以根據 remove 方法結合上之前實作的 find 方法實作一個洗掉指定元素 element 的方法：

該方法實作邏輯為：

先通過 find 方法查找這個需要洗掉的元素 element，如果找的到則會回傳該元素的索引，再使用該索引呼叫 remove 方法進行洗掉并且回傳 true, 如果找不到則回傳 false，

實作如下：

/**
 * 從陣列中洗掉元素 element
 * 
 * @param element 用戶指定的要洗掉的元素
 * @return 如果洗掉 element 成功則回傳 true;否則回傳 false
 */
public boolean removeElement(int element) {
    // 使用 find 方法查找該元素的索引
    int index = find(element);

    // 如果找到,進行洗掉
    if (index != -1) {
        remove(index);
        return true;
    } else {
        return false;
    }
}

需要注意的是當前陣列中是可以存在重復的元素的，如果存在重復的元素，在進行以上操作后只是洗掉了一個元素，并沒有完全洗掉掉陣列中的所有這個元素，對于 find 方法也是如此，如果存在重復的元素，那么查找到的索引則是第一個查找到的元素的索引，

所以可以接著再實作一個能洗掉陣列中重復元素的方法 removeAllElement:

對于該方法，實作邏輯為：

1. 先使用 find 方法尋找一次用戶指定要洗掉元素 element 的索引 index，

2. 再使用 while 回圈對 index 進行判斷：

3. 如果 index 不等于 -1，則在回圈中呼叫 remove 方法將第一次查找到的索引傳進去進行洗掉，

4. 然后再次使用 find 方法查找是否還有該元素再在下一次回圈中進行判斷，

5. 以此類推直到回圈結束就可以洗掉掉陣列中所有的該元素了，

為了判斷陣列中是否有進行過洗掉操作，我使用了一個變數 i 來記錄洗掉操作的次數：

如果 while 回圈結束后 i 的值大于 0 則表示進行過洗掉操作，此時回傳 true 代表洗掉元素成功，反之回傳 false 代表沒有這個元素進行洗掉，

具體實作代碼如下：

/**
 * 洗掉陣列中的所有這個元素 element
 * 
 * @param element 用戶指定的要洗掉的元素
 * @return 洗掉成功回傳 true;否則回傳 false
 */
public boolean removeAllElement(int element) {
    // 使用 find 方法查找該元素的索引
    int index = find(element);

    // 用于記錄是否有洗掉過元素 element
    int i = 0;

    // 通過 white 回圈洗掉陣列中的所有這個元素
    while (index != -1) {
        remove(index);
        index = find(element);
        i++;
    }

    // 有洗掉過元素 element,回傳 true
    // 找不到元素 element 進行洗掉,回傳 false
    return i > 0;
}

對于查找一個元素在陣列中的所有索引的方法這里就不再實作了，有興趣的朋友可以自行實作，

至此，這個類當中的基本方法都基本實作完成了，接下來要做的操作便是使用泛型對這個類進行一些改造使其更加通用，能夠存放 “任意” 資料型別的資料，

使用泛型使該類更加通用（能夠存放 “任意” 資料型別的資料）

我們知道對于泛型而言，是不能夠存盤基本資料型別的，但是這些基本資料型別都有相對應的包裝類，所以對于這些基本資料型別只需使用它們對應的包裝類即可，

對于將該類修改成泛型類非常簡單，只需要更改幾個地方即可，不過需要注意以下幾點：

1. 對于泛型而言，Java 是不支持形如 data = https://www.cnblogs.com/txxunmei/p/new E[capacity]; 直接 new 一個泛型陣列的，需要繞一個彎子來實作，如下所示：

   data = https://www.cnblogs.com/txxunmei/p/(E[]) new Object[capacity];
   

2. 在上面實作 contains 方法和 find 方法時，我們在其中進行了資料間的對比操作：if (data[i] == element)，在我們將類轉變為泛型類之后，我們需要對這個判斷做些修改，因為在使用泛型之后，我們陣列中的資料是參考物件，我們知道參考物件之間的對比使用 equals 方法來進行比較為好，所以做出了如下修改：

   if (data[i].equals(element)) {
       ...
   }
   

3. 如上所述，在使用了泛型之后，陣列中的資料都是參考物件，所以在 remove 方法的實作中，對于維護 size 變數之后，我們已經知道此時 size 的位置是可能存在之前資料的參考的，所以此時我們可以將 size 這個位置置為 null，讓垃圾回收可以較為快速地將這個不需要的參考回收，避免物件的游離，修改如下：

   /**
   * 從陣列中洗掉 index 位置的元素并且回傳洗掉的元素
   * 
   * @param index 要洗掉元素的索引
   * @return 回傳洗掉的元素
   */
   public E remove(int index) {
       ...
       
       // 維護 size
       size--;
   
       // 釋放 size 處的參考,避免物件游離
       data[size] = null;
       
       ...
   }
   

綜上, 將該類轉變為泛型類的總修改如下所示：

public class Array<E> {

    /**
     * 靜態陣列 data,基于該陣列進行封裝該陣列類
     * data 的長度對應其容量
     */
    private E[] data;

    /**
     * 陣列當前擁有的元素個數
     */
    private int size;

    /**
     * 默認建構式,用戶不知道要創建多少容量的陣列時使用
     */
    public Array() {
        // 默認創建容量為 10 的陣列
        this(10);
    }

    /**
     * 建構式,傳入陣列的容量 capacity 構造 Array
     * 
     * @param capacity 需要開辟的陣列容量,由用戶指定
     */
    public Array(int capacity) {
        // 初始化 data
        data = https://www.cnblogs.com/txxunmei/p/(E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 獲得陣列當前的元素個數
     * 
     * @return 回傳陣列當前的元素個數
     */
    public int getSize() {
        return size;
    }

    /**
     * 獲得陣列的容量
     * 
     * @return 回傳陣列的容量
     */
    public int getCapacity() {
        return data.length;
    }

    /**
     * 判斷陣列是否為空
     * 
     * @return 陣列為慷訓傳 true;否則回傳 false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在陣列的 index 索引處插入一個新元素 element
     * 
     * @param index 要插入元素的索引
     * @param element 要插入的新元素
     */
    public void add(int index, E element) {
        // 檢查陣列空間是否已滿
        if (size == data.length) {
            throw new IllegalArgumentException("向陣列指定索引位置添加元素失敗, 陣列已滿!");
        }
    
        // 檢查 index 是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("向陣列指定索引位置添加元素失敗, index 應在 [0, size] 范圍中!");
        }
    
        // 將 index 及其后面所有的元素都往后面移一個位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 將新元素 element 添加到 index 位置
        data[index] = element;
        
        // 維護 size 變數
        size++;
    }

    /**
     * 在陣列首部添加一個新元素
     * 
     * @param element 添加的新元素
     */
    public void addFirst(E element) {
        // 復用 add 方法實作該方法
        add(0, element);
    }

    /**
     * 向陣列末尾添加一個新元素
     * 
     * @param element 添加的新元素
     */
    public void addLast(E element) {
        // 復用 add 方法實作該方法
        add(size, element);
    }

    /**
     * 獲取 index 索引位置的元素
     * 
     * @param index 要獲取元素的索引位置
     * @return 回傳用戶指定的索引位置處的元素
     */
    public E get(int index) {
        // 檢查 index 是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("獲取 index 索引位置的元素失敗, index 應在 [0, size) 范圍中!");
        }
        
        // 回傳用戶指定的索引位置處的元素
        return data[index];
    }

    /**
     * 修改 index 索引位置的元素為 element
     * 
     * @param index 用戶指定的索引位置
     * @param element 要放到 index 處的元素
     */
    public void set(int index, E element) {
        // 檢查 index 是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("修改 index 索引位置的元素為指定元素失敗, index 應在 [0, size) 范圍中!");
        }

        // 修改 index 索引位置的元素為 element
        data[index] = element;
    }

    /**
     * 查找陣列中是否有元素 element
     * 
     * @param element 用戶需要知道是否存在于陣列中的元素
     * @return 如果陣列中包含有 element 則回傳 true;否則回傳 false
     */
    public boolean contains(E element) {
        // 遍歷陣列,逐一判斷
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 查找陣列中元素 element 所在的索引
     * 
     * @param element 進行搜索的元素
     * @return 如果元素 element 存在則回傳其索引;不存在則回傳 -1
     */
    public int find(E element) {
        // 遍歷陣列,逐一判斷
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 從陣列中洗掉 index 位置的元素并且回傳洗掉的元素
     * 
     * @param index 要洗掉元素的索引
     * @return 回傳洗掉的元素
     */
    public E remove(int index) {
        // 檢查 index 是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("洗掉指定位置的元素失敗, index 應在 [0, size) 范圍中!");
        }

        // 存盤待洗掉的元素,以便回傳
        E removeElement = data[index];

        // 進行洗掉
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        // 維護 size
        size--;

        // 釋放 size 處的參考,避免物件游離
        data[size] = null;

        // 回傳洗掉的元素
        return removeElement;
    }

    /**
     * 從陣列中洗掉第一個元素并且回傳洗掉的元素
     * 
     * @return 回傳洗掉的元素
     */
    public E removeFirst() {
        // 復用 remove 方法實作該方法
        return remove(0);
    }

    /**
     * 從陣列中洗掉最后一個元素并且回傳洗掉的元素
     * 
     * @return 回傳洗掉的元素
     */
    public E removeLast() {
        // 復用 remove 方法實作該方法
        return remove(size - 1);
    }

    /**
     * 從陣列中洗掉元素 element
     * 
     * @param element 用戶指定的要洗掉的元素
     * @return 如果洗掉 element 成功則回傳 true;否則回傳 false
     */
    public boolean removeElement(E element) {
        // 使用 find 方法查找該元素的索引
        int index = find(element);

        // 如果找到,進行洗掉
        if (index != -1) {
            remove(index);
            return true;
        } else {
            return false;
        }
    }

    /**
     * 洗掉陣列中的所有這個元素 element
     * 
     * @param element 用戶指定的要洗掉的元素
     * @return 洗掉成功回傳 true;否則回傳 false
     */
    public boolean removeAllElement(E element) {
        // 使用 find 方法查找該元素的索引
        int index = find(element);

        // 用于記錄是否有洗掉過元素 element
        int i = 0;

        // 通過 white 回圈洗掉陣列中的所有這個元素
        while (index != -1) {
            remove(index);
            index = find(element);
            i++;
        }

        // 有洗掉過元素 element,回傳 true
        // 找不到元素 element 進行洗掉,回傳 false
        return i > 0;
    }

    /**
     * 重寫 toString 方法,顯示陣列資訊
     * 
     * @return 回傳陣列中的資訊
     */
    @Override
    public String toString() {
        StringBuilder arrayInfo = new StringBuilder();

        arrayInfo.append(String.format("Array: size = %d, capacity = %d/n", size, data.length));

        arrayInfo.append("[");
        for (int i = 0; i < size; i++) {
            arrayInfo.append(data[i]);
            // 判斷是否為最后一個元素
            if (i != size - 1) {
                arrayInfo.append(", ");
            }
        }
        arrayInfo.append("]");

        return arrayInfo.toString();
    }
}

此時可以做一些測驗：

測驗代碼：

public static void main(String[] args) {
    Array<Integer> array = new Array<>(20);

    for (int i = 0; i < 10; i++) {
        array.addLast(i);
    }

    System.out.println(array + "\n");

    array.add(1, 20);
    System.out.println(array);

    array.addFirst(35);
    System.out.println(array);

    array.addLast(40);
    System.out.println(array + "\n");

    Integer e = array.remove(6);
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    e = array.removeLast();
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    e = array.removeFirst();
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    int size = array.getSize();
    int capacity = array.getCapacity();
    System.out.println("size: " + size + ", capacity: " + capacity + "\n");

    e = array.get(3);
    System.out.println("e: " + e);

    array.set(3, 66);
    e = array.get(3);
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    boolean empty = array.isEmpty();
    System.out.println("empty: " + empty);

    boolean contains = array.contains(9);
    System.out.println("contains: " + contains + "\n");

    int index = array.find(9);
    System.out.println(array);
    System.out.println("index: " + index + "\n");

    boolean b = array.removeElement(9);
    System.out.println(array);
    System.out.println("b: " + b + "\n");

    array.addLast(88);
    array.addLast(88);
    array.addLast(88);
    System.out.println(array);

    b = array.removeAllElement(88);
    System.out.println(array);
    System.out.println("b: " + b);
}

測驗結果：

Array: size = 10, capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Array: size = 11, capacity = 20
[0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12, capacity = 20
[35, 0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 13, capacity = 20
[35, 0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 40]

e: 4
Array: size = 12, capacity = 20
[35, 0, 20, 1, 2, 3, 5, 6, 7, 8, 9, 40]

e: 40
Array: size = 11, capacity = 20
[35, 0, 20, 1, 2, 3, 5, 6, 7, 8, 9]

e: 35
Array: size = 10, capacity = 20
[0, 20, 1, 2, 3, 5, 6, 7, 8, 9]

size: 10, capacity: 20

e: 2
e: 66
Array: size = 10, capacity = 20
[0, 20, 1, 66, 3, 5, 6, 7, 8, 9]

empty: false
contains: true

Array: size = 10, capacity = 20
[0, 20, 1, 66, 3, 5, 6, 7, 8, 9]
index: 9

Array: size = 9, capacity = 20
[0, 20, 1, 66, 3, 5, 6, 7, 8]
b: true

Array: size = 12, capacity = 20
[0, 20, 1, 66, 3, 5, 6, 7, 8, 88, 88, 88]
Array: size = 9, capacity = 20
[0, 20, 1, 66, 3, 5, 6, 7, 8]
b: true

行程已結束，退出代碼 0

在將這個類轉換為泛型類以支持存盤 “任意” 型別的資料之后，還可以對這個類進行一些修改，使其能夠根據存盤的資料量動態地擴展以及縮小自身的空間以節約資源，

升級為動態陣列

對于動態陣列，我們需要實作的效果為使其能夠根據自身資料量的大小自動伸縮自身的空間，所以就相對應著兩種情況：當陣列空間滿的時候進行擴容、當陣列空間少到一定程度時進行減容，接下來一一實作，

當陣列空間滿的時候進行擴容

對于這種情況，在我們先前的實作中，在陣列空間用完時我們往其中添加新資料我們是不能再往陣列中添加的，所以此時我們需要在 add 方法中做擴容操作以使能夠添加新資料進去，

對于擴容操作，可以實作一個 更改容量的方法 resize 來實作：

1. 先構造一個容量為當前陣列兩倍的新陣列 newData，

   • 對于為何擴容原來空間的兩倍而不是擴容一個常數，是因為如果擴容一個常數不知道要擴容多少空間，

   • 比如原先已有幾萬個元素此時擴容幾十個容量那是十分低效的，因為如果要再添加很多資料需要擴容很多次，

   • 又比如一次擴容很多容量又顯得十分浪費，比如原有 10 個資料此時擴容 1000 個容量那么可能會有很多空間會被浪費，

   • 而對于擴容為原來容量的二倍（也可以擴容為其他倍數，如 1.5 倍），是和當前陣列有多少容量是相關的，擴容的量和已有的容量是一個數量級的，比如原有容量為 100 那么擴容成 200，原有容量為 10000 那么擴容為 20000，這樣子擴容是比較有優勢的，之后會進行復雜度分析分析其中的優勢，

2. 使用回圈將當前陣列的資料一一復制到新陣列中，

3. 將當前陣列的參考變數 data 參考到 newData 上，

4. 對于 size 的操作依然還是之前 add 方法中的操作，不用在擴容方法中進行操作，

5. 對于 data 之前的參考，因為此時 data 已經參考到了新陣列上，沒有其他變數參考它們，所以原來的參考會被垃圾回收自動回收掉，

6. 對于 newData 這個變數由于它是區域變數在執行完添加資料這個方法之后會自動消失,不用對其進行額外的操作，

7. 所以最后 data 這個變數參考的就是陣列擴容后并添加了新資料后的所有資料，

以上程序圖示如下：

修改過后的代碼如下所示：

/**
 * 在陣列的 index 索引處插入一個新元素 element
 * 
 * @param index 要插入元素的索引
 * @param element 要插入的新元素
 */
public void add(int index, E element) {
    // 檢查 index 是否合法
    if (index < 0 || index > size) {
       throw new IllegalArgumentException("向陣列指定索引位置添加元素失敗, index 應在 [0, size] 范圍中!");
    }

    // 檢查陣列空間是否已滿,如果已滿進行擴容,再進行添加資料的操作
    if (size == data.length) {
        // 對 data 進行擴容,擴容為原先容量的兩倍
        resize(2 * data.length);
    }

    // 將 index 及其后面所有的元素都往后面移一個位置
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }

    // 將新元素 element 添加到 index 位置
    data[index] = element;

    // 維護 size 變數
    size++;
}

/**
 * 更改 data 的容量
 * 
 * @param newCapacity data 的新容量
 */
private void resize(int newCapacity) {
    E[] newData = https://www.cnblogs.com/txxunmei/p/(E[]) new Object[newCapacity];

    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }

    data = newData;
}

當陣列空間少到一定程度時進行減容

對于這種情況，在先前的 remove 方法實作中，洗掉了元素之后是沒有進行別的操作的，此時我們需要進行一個判斷，判斷陣列在洗掉元素后此時剩余的元素個數是否達到了一個比較小的值，如果達到我們就進行減容操作，此時先將這個值設定為陣列原來容量的二分之一，如果剩余的元素個數等于這個值，這里先暫時將陣列的容量減小一半，

這時候就可以復用上面實作的更改陣列容量的方法了，具體代碼實作如下：

/**
 * 從陣列中洗掉 index 位置的元素并且回傳洗掉的元素
 * 
 * @param index 要洗掉元素的索引
 * @return 回傳洗掉的元素
 */
public E remove(int index) {
    // 檢查 index 是否合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("洗掉指定位置的元素失敗, index 應在 [0, size) 范圍中!");
    }

    // 存盤待洗掉的元素,以便回傳
    E removeElement = data[index];

    // 進行洗掉
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    // 維護 size
    size--;

    // 釋放 size 處的參考,避免物件游離
    data[size] = null;

    // 判斷當前 data 中的元素個數是否達到了該進行減容操作的個數,如果達到進行減容
    if (size == data.length / 2) {
        // 減容操作,減小容量為原先的二分之一
        resize(data.length / 2);
    }

    // 回傳洗掉的元素
    return removeElement;
}

至此，已經基本實作了動態陣列該具有的功能，接著對當前實作的方法進行一些簡單的時間復雜度分析以找到一些還能提升效率的地方進行修改使這個陣列類更加完善，

簡單的時間復雜度分析與一些改進

對于添加操作的時間復雜度分析

對于添加操作，已經實作了三個方法，分別是：addLast、addFirst、add 方法，接下來一一簡單地分析一下它們的時間復雜度：

addLast：對于這個方法，每一次添加都是在陣列末尾直接賦值，不需要移動元素，所以可以得出該方法的時間復雜度為 O(1)，

addFirst：對于該方法，每一次添加都需要把陣列所有元素往后移動一個位置以騰出第一個位置來放置新元素，可以得出該方法的時間復雜度為 O(n)，

add：對于該方法，可能有時在陣列較前面添加、可能有時在陣列較后面添加，但綜合而言，移動元素的次數大約為 n/2，所以該方法的時間復雜度為 O(n/2) = O(n)，

所以總的來說，添加操作的時間復雜度為 O(n)，（最壞情況）

對于添加操作中的 resize 方法，每一次執行都會復制一次陣列中的所有元素，所以該方法的時間復雜度為 O(n)，

對于洗掉操作的時間復雜度分析

由上面的添加操作的時間復雜度分析可以很快的得出洗掉操作的時間復雜度如下：

removeLast：O(1)

removeFirst：O(n)

remove：O(n/2) = O(n)

總的來說，洗掉操作的時間復雜度為 O(n)，（最壞情況）

其中的 resize 方法上面已經分析過，時間復雜度為 O(n)，

對于修改操作的時間復雜度分析

對于修改操作而言，實作了 set 方法，對于該方法存在兩種情況：

知道要修改元素的索引：如果知道索引，那么可以瞬間找出要修改的元素并修改為新元素，所以時間復雜度為 O(1)，

不知道要修改元素的索引：如果不知道索引，可以借助 find 方法找到索引位置再進行修改，所以這種情況需要先找后改，時間復雜度為 O(n)，

對于查找操作的時間復雜度分析

對于查詢操作，實作了三個方法 get、contains、find：

get：該方法為使用索引獲取元素，時間復雜度為 O(1)，

contains：該方法是一一判斷元素是否存在，時間復雜度為 O(n)，

find：該方法是一一判斷元素是否存在找到其位置，時間復雜度為 O(n)，

總的來說，如果知道索引，查找操作時間復雜度為 O(1)；如果不知道索引，時間復雜度為 O(n)，

此時再著重觀察一下添加和洗掉操作，如果我們總是只對最后一個元素進行操作（addLast 或 removeLast），那么此時時間復雜度是否還是為 O(n)?resize 方法是否會影響?

可以進行一些簡單的分析：

1. 首先先看 resize 方法，對于這個方法，是不是在每一次添加或洗掉元素時會影響到陣列的性能呢？很顯然不是的，對于 reszie 而言并不是每次執行添加和洗掉操作時都會觸發它，

2. 比如一個陣列初始容量為 10，那么它要執行 10 次添加操作才會執行一次 resize 方法，此時容量為 20，這時要再執行 10 次添加操作才會再執行 resize 方法，然后容量變為 40，這時需要執行 20 次添加操作才會再一次執行 resize 方法，

3. 即正常情況下，需要執行 n 次添加操作才會觸發一次 resize 方法，

接著進行如下分析：

1. 假設陣列當前容量為 10，并且每一次添加操作都使用 addLast：

2. 前十次添加是沒有任何問題的，進行了 10 次 addLast 操作，

3. 在第十一次添加時，觸發了一次 resize 方法，此時復制 10 個元素，進行了 10 次基本操作，

4. 執行完 resize 方法之后，添加了第十一個元素，此時又進行了一次 addLast 操作，

5. 所以到此時，一共執行了 11 次 addLast 操作，觸發了一次 resize，總共進行了 21 次基本操作，

6. 那么平均而言，每次 addLast 操作，大約進行 2 次基本操作，時間復雜度為 O(1)，

以上可歸納如下：

假設陣列容量為 n，執行了 n+1 次 addLast，觸發 resize，總共進行 2n+1 次基本操作，平均每次 addLast 操作進行大約 2 次基本操作，這樣均攤計算，時間復雜度是 O(1) 的，

同理，removeLast 操作的均攤復雜度也為 O(1)，

不過此時，在我們之前的代碼實作中還存在著一個特殊情況：同時進行 addLast 和 removeLast 操作（復雜度震蕩），

以一個例子說明：

假設當前陣列容量已滿為 n，此時進行一次 addLast 操作，那么會觸發一次 resize 方法將容量擴容為 2n，然后緊接著又執行一次 removeLast 操作，此時元素個數為 n 為容量 2n 的一半又會觸發一次 resize 方法，接著又執行一次 addLast 方法，再接著執行 removeLast 方法，以此類推，回圈往復，resize 方法就會一直被觸發，每次的時間復雜度都為 O(n)，這時再也不是如之前分析的那般每 n 次添加操作才會觸發一次 resize 方法了，也就是不再均攤復雜度了，這種情況也就是復雜度震蕩（從預想的 O(1) 一下上升到了 O(n)），

那么此時需要進行一些改進，從上面例子可以分析出出現這種特殊情況的原因：removeLast 時觸發 resize 過于著急，

也就是當元素個數為當前容量二分之一時就進行了減容操作，將容量減少為二分之一，此時容量是滿的，這時再添加一個元素自然而然的就再一次觸發 resize 方法進行擴容了，

所以可以這樣修改：在進行 removeLast 操作時，原先實作的判斷元素個數等于容量的二分之一就進行減容的操作修改為當元素個數等于容量的四分之一時才進行減容操作，減少容量為原先的一半，這樣子減容之后，還預留了一半的空間用于添加元素，避免了以上的復雜度震蕩，

所以修改代碼如下（需要注意的是在減容的程序中可能陣列容量會出現等于 1 的情況，如果容量為 1，傳進 resize 方法的引數就是 1/2=0 了，這時會 new 一個空間為 0 的陣列，所以需要避免這種情況）：

/**
 * 從陣列中洗掉 index 位置的元素并且回傳洗掉的元素
 * 
 * @param index 要洗掉元素的索引
 * @return 回傳洗掉的元素
 */
public E remove(int index) {
    // 檢查 index 是否合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("洗掉指定位置的元素失敗, index 應在 [0, size) 范圍中!");
    }

    // 存盤待洗掉的元素,以便回傳
    E removeElement = data[index];

    // 進行洗掉
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    // 維護 size
    size--;

    // 釋放 size 處的參考,避免物件游離
    data[size] = null;

    // 當 size == capacity / 4 時,進行減容操作
    if (size == data.length / 4 && data.length / 2 != 0) {
        // 減容操作,減小容量為原先的二分之一
        resize(data.length / 2);
    }

    // 回傳洗掉的元素
    return removeElement;
}

至此，這個陣列類就封裝完成了，總的來說這個類基于一個靜態陣列實作了一個支持增刪改查資料、動態更改陣列空間和支持存盤 “任意” 資料型別的資料的陣列資料結構，

如有寫的不足的，請見諒，請大家多多指教，

標籤：其他

上一篇：單鏈表上的基本操作

下一篇：資料結構導論之第七章排序