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!

推薦閱讀: