Java 動態數組的實現示例
靜態數組
Java中最基本的數組大傢肯定不會陌生:
int[] array = new int[6]; for (int i = 0; i < array.length; i++){ array[i] = 2 * i + 1; }
通過循環把元素放入指定的位置中,類似於這樣:
這是一個靜態數組,因為我們在第一步初始化的時候就已經固定瞭它的長度,後面再也無法改變。所以,由於有這個限制,靜態數組不適用於那些不確定儲存多少數據的場景。
但是如果數組滿瞭,能否再新建一個更長一些的數組,把原數組這些元素再轉移到新數組中呢?這樣一來,數組就可以繼續使用瞭。按照這個思路,我們就可以創建基於靜態數組的動態數組。
動態數組的實現原理
“動態”主要體現在以下幾方面:
1.添加元素
不局限於隻在數組末尾添加,而是能夠隨意選擇索引位置(隻要不超過數組長度)。例如在索引為1處添加元素4:
從圖中可以看出,需要將index處及右側的元素依次向右移動一個單位(從末位元素開始),最後用新增元素覆蓋index處元素。
2.刪除元素
同添加元素,也可根據索引進行選擇。例如刪除索引為0處的元素3:
刪除元素移動元素的方向與添加元素正好相反,從index處開始,直接使用後一位元素覆蓋前一位元素,最後將末位元素置為null。
3.數組擴容
數組一旦裝滿元素,可觸發數組擴容,即新建一個更長的數組,將原數組元素轉移到新數組中,並將引用指向新數組,完成數組的變更;
4.數組縮減
如果數組元素相對總容量來說過少(例如數組元素個數小於數組容量的1/4),便可觸發數組縮減,即新建一個更短的數組,並轉移元素至新數組。
代碼實現
以下通過新建一個 Array 類,依次實現這幾個重要功能:
public class Array<E> { private E[] data; // 使用靜態數組存放數組元素 private int size; // 記錄數組元素數量 public Array(int capacity) { this.data = (E[]) new Object[capacity]; this.size = 0; } public Array() { this(10); // 默認capacity為10 } // 數組擴容/縮減 public void resize(int newCapacity) { // 新數組長度必須大於0 if (newCapacity < 0) throw new IllegalArgumentException("capacity must > 0!"); // 創建新數組 E[] newData = (E[]) new Object[newCapacity]; // 將原數組元素放入新數組中 for (int i = 0; i < size; i++) { newData[i] = data[i]; } // 將引用指向新數組 data = newData; } /** * 在指定位置添加元素 * 指定位置處的元素需要向右側移動一個單位 * @param index 索引 * @param element 要添加的元素 */ public void add(int index, E element) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and <= size!"); // 數組滿員觸發擴容 if (size == data.length) { resize(2 * data.length); // 擴容為原數組的2倍 } // 從尾部開始,向右移動元素,直到index for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } // 添加元素 data[index] = element; size++; } // 數組頭部添加元素 public void addFirst(E element) { add(0, element); } // 數組尾部添加元素 public void addLast(E element) { add(size, element); } /** * 刪除指定位置元素 * 通過向左移動一位,覆蓋指定位置處的元素,實現刪除元素(data[size - 1] = null) * @param index 索引 */ public E remove(int index) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!"); // 數組長度為0時拋出異常 if (size == 0) throw new IllegalArgumentException("Empty array!"); E removedElement = data[index]; // 向左移動元素 for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } // 將尾部空閑出的位置置為空,釋放資源 data[size - 1] = null; size--; // size過小觸發數組縮減 if (size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return removedElement; } // 刪除頭部元素 public E removeFirst() { return remove(0); } // 刪除尾部元素 public E removeLast() { return remove(size - 1); } // 重寫Override方法,自定義數組顯示格式 @Override public String toString() { StringBuilder str = new StringBuilder(); // 顯示數組的整體情況(長度、總容量) str.append(String.format("Array: size = %d, capacity = %d\n[", size, data.length)); // 循環添加數組元素至str for (int i = 0; i < size; i++) { str.append(data[i]); if (i < size - 1) str.append(", "); } str.append("]"); return str.toString(); } }
接下來我們測試一下這個數組的使用情況:
public static void main(String[] args) { // 添加10個元素 Array<Integer> arr = new Array<>(); for (int i = 0; i < 10; i++) arr.add(i, i); // 查看數組當前狀態 System.out.println(arr); // 繼續添加元素,觀察是否擴容 arr.add(arr.size, 7); System.out.println(arr); // 再刪除6個元素,觀察是否縮減 for (int i = 0; i < 6; i++) { System.out.println("元素" + arr.removeFirst() + "已被刪除!"); } System.out.println(arr); } /* 輸出結果: Array: size = 10, capacity = 10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Array: size = 11, capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 7] 元素0已被刪除! 元素1已被刪除! 元素2已被刪除! 元素3已被刪除! 元素4已被刪除! 元素5已被刪除! Array: size = 5, capacity = 10 [6, 7, 8, 9, 7] */
可以看到,當數組滿員後,繼續添加元素可以成功觸發數組擴容;而當數組元素過少時,也會觸發縮減。
再實現幾個常用方法來完善我們的動態數組類:
// 獲取數組長度 public int getSize() { return size; } // 獲取數組總容量 public int getCapacity() { return data.length; } // 判斷數組是否為空 public boolean isEmpty() { return getSize() == 0; } // 查找指定元素在數組中的位置 public int search(E element) { for (int i = 0; i < getSize(); i++) { if (data[i].equals(element)) { return i; } } // -1表示未找到 return -1; } // 判斷指定元素是否在數組中 public boolean contains(E element) { return search(element) != -1; } // 按照索引查找元素值 public E get(int index) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!"); return data[index]; } // 查找頭部元素 public E getFirst() { return get(0); } // 查找尾部元素 public E getLast() { return get(getSize() - 1); } // 設置指定位置的元素值 public void set(int index, E element) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!"); data[index] = element; } /** * 按照元素值刪除 * 隻刪除數組中第一個元素值與指定值相等的元素 * @param element 指定元素值 */ public boolean removeElement(E element) { int index = search(element); if (index != -1) { remove(index); return true; } return false; } /** * 按照元素值刪除 * 刪除數組中所有值與指定值相等的元素 * * @param element 指定元素值 */ public boolean removeElementAll(E element) { boolean isRemoved = false; int i = getSize() - 1; while (i >= 0) { if (data[i].equals(element)) { remove(i); isRemoved = true; } i--; } return isRemoved; }
從外部調用者的角度,無法覺察到其中的數組變更操作,感覺就是一個動態數組,但是由於擴容和縮減操作均需要新建數組,並且遍歷原數組,會導致過多的開銷,所以從性能上來說,並不是好的解決方案。後面我們將學習更加高效的數據結構。
到此這篇關於Java 動態數組的實現示例的文章就介紹到這瞭,更多相關Java 動態數組內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!