一篇文章讓你了解動態數組的數據結構的實現過程（Java 實現）
- 2020 年 4 月 1 日
- 筆記
數組基礎簡單回顧
- 數組是一種數據結構，用來存儲同一類型值的集合。
- 數組就是存儲數據長度固定的容器，保證多個數據的數據類型要一致。
- 數組是一種引用數據類型。
- 簡單來說，數組就是把需要存儲的數據排成一排進行存放。
- 數組的索引從 0 開始計數，最後一個位置的索引是數組的長度 – 1（n – 1）。
- 可以使用數組的索引來存取數據。
- 數組的索引可以有語意，也可以沒有語意。
- 例如，一個存儲學生成績的數組如果索引有語意，那麼索引可以看成學生的學號，此時對於使用索引操作數組就可以看成對學號是 xxx 的學生進行存取成績的操作。那麼如果沒有語意，就是隨意存取學生的成績到該數組中。
- 數組最大的優點：快速查詢。例如：arr[index]。
- 根據此優點，可以知道數組最好應用於 「索引有語意」 的情況。因為索引有了語意，那麼我們就可以知道要取的數據是什麼、是在哪個位置，可以很方便地查詢到數據。
- 但也並非是所有有語意的索引都適用於數組，例如身份證號。我們知道，一個身份證號的號碼有 18 位的長度，如果索引為一個身份證號，其對應著一個人，那麼數組就要開啟很大的空間，要開啟空間到一個索引能有 18 位長度的數字這麼大。那麼此時如果只存取幾個人，空間就會很浪費，而且這麼多空間里並不是每一個索引都能是一個身份證號，有些是和身份證號的格式對應不上的，這些空間就會被浪費，所以並非是所有有語意的索引都適用於數組，要根據情況來決定使用。
- 數組也可以處理「索引沒有語意」的情況。比如一個數組有 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 = 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("AddLast failed. Array is full."); } // 在數組末尾添加新元素 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("Add failed. Array is full."); } // 檢查 index 是否合法 if (index < 0 || index > size) { // 拋出一個非法參數異常表示向數組指定索引位置添加元素失敗,應該讓 index 在 0 到 size 這個範圍才行 throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= 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 = %dn", 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) { // 拋出一個非法參數異常表示獲取 index 索引位置的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Get failed. Index is illegal."); } // 返回用戶指定的索引位置處的元素 return data[index]; }
-
-
-
同理，可以實現修改元素的方法如下：
/** * 修改 index 索引位置的元素為 element * @param index 用戶指定的索引位置 * @param element 要放到 index 處的元素 */ public void set(int index, int element) { // 檢查 index 是否合法 if (index < 0 || index >= size) { // 拋出一個非法參數異常表示修改 index 索引位置的元素為 element 失敗,因為 index 是非法值 throw new IllegalArgumentException("Set failed. Index is illegal."); } // 修改 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) { // 拋出一個非法參數異常表示從數組中刪除 index 位置的元素並且返回刪除的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Remove failed. Index is illegal."); } // 存儲待刪除的元素,以便返回 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:
-
對於該方法，實現邏輯為：
- 先使用 find 方法尋找一次用戶指定要刪除元素 element 的索引 index。
- 再使用 while 循環對 index 進行判斷：
- 如果 index 不等於 -1，則在循環中調用 remove 方法將第一次查找到的索引傳進去進行刪除。
- 然後再次使用 find 方法查找是否還有該元素再在下一次循環中進行判斷。
- 以此類推直到循環結束就可以刪除掉數組中所有的該元素了。
-
為了判斷數組中是否有進行過刪除操作，我使用了一個變數 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; } -
對於查找一個元素在數組中的所有索引的方法這裡就不再實現了，有興趣的朋友可以自行實現。
-
-
-
-
至此，這個類當中的基本方法都基本實現完成了，接下來要做的操作便是使用泛型對這個類進行一些改造使其更加通用，能夠存放 「任意」 數據類型的數據。
使用泛型使該類更加通用（能夠存放 「任意」 數據類型的數據）
-
我們知道對於泛型而言，是不能夠存儲基本數據類型的，但是這些基本數據類型都有相對應的包裝類，所以對於這些基本數據類型只需使用它們對應的包裝類即可。
-
對於將該類修改成泛型類非常簡單，只需要更改幾個地方即可，不過需要注意以下幾點：
-
對於泛型而言，Java 是不支援形如 data = new E[capacity]; 直接 new 一個泛型數組的，需要繞一個彎子來實現，如下所示：
data = (E[]) new Object[capacity]; -
在上面實現 contains 方法和 find 方法時，我們在其中進行了數據間的對比操作：if (data[i] == element)。在我們將類轉變為泛型類之後，我們需要對這個判斷做些修改，因為在使用泛型之後，我們數組中的數據是引用對象，我們知道引用對象之間的對比使用 equals 方法來進行比較為好，所以做出了如下修改：
if (data[i].equals(element)) { ... } -
如上所述，在使用了泛型之後，數組中的數據都是引用對象，所以在 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 = (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("Add failed. Array is full."); } // 檢查 index 是否合法 if (index < 0 || index > size) { // 拋出一個非法參數異常表示向數組指定索引位置添加元素失敗,應該讓 index 在 0 到 size 這個範圍才行 throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= 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) { // 拋出一個非法參數異常表示獲取 index 索引位置的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Get failed. Index is illegal."); } // 返回用戶指定的索引位置處的元素 return data[index]; } /** * 修改 index 索引位置的元素為 element * @param index 用戶指定的索引位置 * @param element 要放到 index 處的元素 */ public void set(int index, E element) { // 檢查 index 是否合法 if (index < 0 || index >= size) { // 拋出一個非法參數異常表示修改 index 索引位置的元素為 element 失敗,因為 index 是非法值 throw new IllegalArgumentException("Set failed. Index is illegal."); } // 修改 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) { // 拋出一個非法參數異常表示從數組中刪除 index 位置的元素並且返回刪除的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Remove failed. Index is illegal."); } // 存儲待刪除的元素,以便返回 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 = %dn", 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來實現：
-
先構造一個容量為當前數組兩倍的新數組 newData。
- 對於為何擴容原來空間的兩倍而不是擴容一個常數，是因為如果擴容一個常數不知道要擴容多少空間。
- 比如原先已有幾萬個元素此時擴容幾十個容量那是十分低效的，因為如果要再添加很多數據需要擴容很多次。
- 又比如一次擴容很多容量又顯得十分浪費，比如原有 10 個數據此時擴容 1000 個容量那麼可能會有很多空間會被浪費。
- 而對於擴容為原來容量的二倍（也可以擴容為其他倍數，如 1.5 倍），是和當前數組有多少容量是相關的，擴容的量和已有的容量是一個數量級的，比如原有容量為 100 那麼擴容成 200，原有容量為 10000 那麼擴容為 20000，這樣子擴容是比較有優勢的，之後會進行複雜度分析分析其中的優勢。
-
使用循環將當前數組的數據一一複製到新數組中。
-
將當前數組的引用變數 data 引用到 newData 上。
-
對於 size 的操作依然還是之前 add 方法中的操作，不用在擴容方法中進行操作。
-
對於 data 之前的引用，因為此時 data 已經引用到了新數組上，沒有其他變數引用它們，所以原來的引用會被垃圾回收自動回收掉。
-
對於 newData 這個變數由於它是局部變數在執行完添加數據這個方法之後會自動消失,不用對其進行額外的操作。
-
所以最後 data 這個變數引用的就是數組擴容後並添加了新數據後的所有數據。
-
-
以上過程圖示如下：
-
修改過後的程式碼如下所示：
/** * 在數組的 index 索引處插入一個新元素 element * @param index 要插入元素的索引 * @param element 要插入的新元素 */ public void add(int index, E element) { // 檢查 index 是否合法 if (index < 0 || index > size) { // 拋出一個非法參數異常表示向數組指定索引位置添加元素失敗,應該讓 index 在 0 到 size 這個範圍才行 throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= 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 = (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) { // 拋出一個非法參數異常表示從數組中刪除 index 位置的元素並且返回刪除的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Remove failed. Index is illegal."); } // 存儲待刪除的元素,以便返回 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)。
- 對於添加操作，已經實現了三個方法，分別是：addLast、addFirst、add 方法。接下來一一簡單地分析一下它們的時間複雜度：
-
對於刪除操作的時間複雜度分析
- 由上面的添加操作的時間複雜度分析可以很快的得出刪除操作的時間複雜度如下：
- removeLast：O(1)
- removeFirst：O(n)
- remove：O(n/2) = O(n)
- 總的來說，刪除操作的時間複雜度為 O(n)。（最壞情況）
- 其中的 resize 方法上面已經分析過，時間複雜度為 O(n)。
- 由上面的添加操作的時間複雜度分析可以很快的得出刪除操作的時間複雜度如下：
-
對於修改操作的時間複雜度分析
- 對於修改操作而言，實現了 set 方法，對於該方法存在兩種情況：
- 知道要修改元素的索引：如果知道索引，那麼可以瞬間找出要修改的元素並修改為新元素，所以時間複雜度為 O(1)。
- 不知道要修改元素的索引：如果不知道索引，可以藉助 find 方法找到索引位置再進行修改，所以這種情況需要先找後改，時間複雜度為 O(n)。
- 對於修改操作而言，實現了 set 方法，對於該方法存在兩種情況：
-
對於查找操作的時間複雜度分析
- 對於查詢操作，實現了三個方法 get、contains、find：
- get：該方法為使用索引獲取元素，時間複雜度為 O(1)。
- contains：該方法是一一判斷元素是否存在，時間複雜度為 O(n)。
- find：該方法是一一判斷元素是否存在找到其位置，時間複雜度為 O(n)。
- 總的來說，如果知道索引，查找操作時間複雜度為 O(1)；如果不知道索引，時間複雜度為 O(n)。
- 對於查詢操作，實現了三個方法 get、contains、find：
-
此時再著重觀察一下添加和刪除操作，如果我們總是只對最後一個元素進行操作（addLast 或 removeLast），那麼此時時間複雜度是否還是為 O(n)?resize 方法是否會影響?
-
可以進行一些簡單的分析：
-
首先先看 resize 方法，對於這個方法，是不是在每一次添加或刪除元素時會影響到數組的性能呢？很顯然不是的，對於 reszie 而言並不是每次執行添加和刪除操作時都會觸發它。
-
比如一個數組初始容量為 10，那麼它要執行 10 次添加操作才會執行一次 resize 方法，此時容量為 20，這時要再執行 10 次添加操作才會再執行 resize 方法，然後容量變為 40，這時需要執行 20 次添加操作才會再一次執行 resize 方法。
- 即正常情況下，需要執行 n 次添加操作才會觸發一次 resize 方法。
-
接著進行如下分析：
- 假設數組當前容量為 10，並且每一次添加操作都使用 addLast：
- 前十次添加是沒有任何問題的，進行了 10 次 addLast 操作。
- 在第十一次添加時，觸發了一次 resize 方法，此時複製 10 個元素，進行了 10 次基本操作。
- 執行完 resize 方法之後，添加了第十一個元素，此時又進行了一次 addLast 操作。
- 所以到此時，一共執行了 11 次 addLast 操作，觸發了一次 resize，總共進行了 21 次基本操作。
- 那麼平均而言，每次 addLast 操作，大約進行 2 次基本操作。時間複雜度為 O(1)。
- 以上可歸納如下：
- 假設數組容量為 n，執行了 n+1 次 addLast，觸發 resize，總共進行 2n+1 次基本操作，平均每次 addLast 操作進行大約 2 次基本操作，這樣均攤計算，時間複雜度是 O(1) 的。
- 假設數組當前容量為 10，並且每一次添加操作都使用 addLast：
-
同理，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) { // 拋出一個非法參數異常表示從數組中刪除 index 位置的元素並且返回刪除的元素失敗,因為 index 是非法值 throw new IllegalArgumentException("Remove failed. Index is illegal."); } // 存儲待刪除的元素,以便返回 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; }
-
-
-
至此，這個數組類就封裝完成了，總的來說這個類基於一個靜態數組實現了一個支援增刪改查數據、動態更改數組空間和支援存儲 「任意」 數據類型的數據的數組數據結構
如有寫的不足的，請見諒，請大家多多指教。(*^▽^*)
