摘要：我理解的數據結構一數組首先，我是一個，但是畢竟是一個腳本語言，如果使用腳本語言去理解數據結構具有一定的局限性。

首先，我是一個phper，但是畢竟php是一個腳本語言，如果使用腳本語言去理解數據結構具有一定的局限性。因為腳本語言是不需要編譯的，如果你的語法寫的不錯，可能執行起來會要比用一個更好的數據結構來的更快、更高效（在數據量不大的情況下）。而且數據結構是脫離任何一門語言存在的。所以，下面會選用java去更深入的理解數據結構。

注：這里不會去過多的解釋java的語法。

int[] arr = new int[10];

int[] arr = new int[] {10, 20, 30};

數組的容量在數組一開始定義的時候就固定了。

數組最大的優點：根據索引快速查詢。如：arr[2]。

數組最好應用于“索引有語意”的情況下。

但并非所有有語意的索引都適用于數組：比如索引是一個人的身份證號，會開辟過大的空間，不現實。

下面會討論數組“索引沒有語意”的情況，基于java數組，二次封裝屬于我們自己的數組類，更深入的理解數組。

學習任何一個數據結構，CRUD必不可少。下面，讓我們來一起一步步完善屬于我們自己的數組的增、刪、改、查

public class Array {

    // 數組的實際大小
    private int size;
    // 數組
    private int[] data;

    // 構造函數，根據傳入的容納量定義一個int類型的數組
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    // 重載，沒有傳入容納量，定義一個長度為10的int類型數組
    public Array() {
        this(10);
    }

    // 數組的實際大小
    public int getSize() {
        return size;
    }

    // 數組的容納量
    public int getCapacity() {
        return data.length;
    }

    // 數組是否為空
    public boolean isEmpty() {
        return size == 0;
    }
}

//往數組的任意位置插入
public void add(int index, int ele) {

    // 數組已滿
    if (size == data.length) {
        throw new IllegalArgumentException("add failed. arr is full");
    }

    // 插入的索引位不合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("add failed. index < 0 or index >= size");
    }

    // 從index向后的所有元素均向后賦值
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = ele;
    size++;
}

// 第一個位置插入
public void addFirst(int ele) {
    add(0, ele);
}

// 最后一個位置插入
public void addLast(int ele) {
    add(size, ele);
}

// 查詢index索引位置的元素
public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("get failed. index is illegal");
    }
    return data[index];
}

// 查詢ele元素的索引，不存在返回-1
public int find(int ele) {
    for (int i = 0; i < size; i++) {
        if (data[i] == ele) {
            return i;
        }
    }
    return  -1;
}

// 更新Index的元素
public void set(int index, int ele) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("get failed. index is illegal");
    }
    data[index] = ele;
}

// 根據索引刪除數組中的第一個ele，返回ele
public int remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }

    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    size--;

    return data[index];
}

// 刪除第一個元素
public int removeFirst() {
    return remove(0);
}

// 刪除最后一個
public int removeLast() {
    return remove(size - 1);
}

// 刪除指定元素
public void removeElement(int ele) {
    int index = find(ele);
    if (index != -1) {
        remove(index);
    }
}

Override
public String toString() {
    StringBuffer res = new StringBuffer();
    res.append(String.format("Array: size = %d, capacity = %d
", size, data.length));
    res.append("[");

    for (int i = 0; i < size; i++) {

        res.append(data[i]);
        if (i != size - 1) {
            res.append(", ");
        }
    }
    res.append("]");
    return res.toString();
}

// 查詢數組中是否包含元素ele
public boolean contain(int ele) {
    for (int i = 0; i < size; i++) {
        if (data[i] == ele) {
            return true;
        }
    }
    return  false;
}

注：通過以上方法我們已經創建了一個最最最最最基本的數組類（見下圖）。當然，你也可以去添加一些自己需要的方法，例如：removeAll、findAll之類的。

但是，我們現在的數組只支持int類型，太過局限。接下來，我們去給我們的數組升華一哈~

首先，為什么我要在任意這兩個字加上引號，因為java的泛型不支持基本數據類型，只能是類的對象。
但是，這并不代表如果我們使用了泛型，就不可以使用基本數據類型了，因為每一個基本數據類型都有一個對應的包裝類。
使用泛型的時候，我們只需要傳入對應的包裝類即可。

public class ArrayNew {
    // 數組的實際大小
    private int size;
    // 數組
    private E[] data;

    // 構造函數，根據傳入的容納量定義一個 E 類型的數組
    public ArrayNew(int capacity) {
        // 強轉
        data = (E[]) new Object[capacity];
        size = 0;
    }

    // 重載，沒有傳入容納量，定義一個長度為10的int類型數組
    public ArrayNew() {
        this(10);
    }

    // 數組的實際大小
    public int getSize() {
        return size;
    }

    // 數組的容納量
    public int getCapacity() {
        return data.length;
    }

    // 數組是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // 往數組的任意位置插入
    public void add(int index, E ele) {

        // 數組已滿
        if (size == data.length) {
            throw new IllegalArgumentException("add failed. arr is full");
        }

        // 插入的索引位不合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add failed. index < 0 or index > size");
        }

        // 從index向后的所有元素均向后賦值
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = ele;
        size++;
    }

    // 第一個位置插入
    public void addFirst(E ele) {
        add(0, ele);
    }

    // 最后一個位置插入
    public void addLast(E ele) {
        add(size, ele);
    }

    // 查詢index索引位置的元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed. index is illegal");
        }
        return data[index];
    }

    // 查詢ele元素的索引，不存在返回-1
    public int find(E ele) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(ele)) {
                return i;
            }
        }
        return  -1;
    }

    // 更新Index的元素
    public void set(int index, E ele) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed. index is illegal");
        }
        data[index] = ele;
    }

    // 根據索引刪除數組中的第一個ele，返回ele
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed. index is illegal");
        }
        
        E result = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = (data[i]);
        }
        // 空間釋放，垃圾回收會自動回收
        data[--size] = null;

        return result;
    }

    // 刪除第一個元素
    public E removeFirst() {
        return remove(0);
    }

    // 刪除最后一個
    public E removeLast() {
        return remove(size - 1);
    }

    // 刪除指定元素
    public void removeElement(E ele) {
        int index = find(ele);
        if (index != -1) {
            remove(index);
        }
    }

    // 查詢數組中是否包含元素ele
    public boolean contain(E ele) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(ele)) {
                return true;
            }
        }
        return  false;
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append(String.format("Array: size = %d, capacity = %d
", size, data.length));
        res.append("[");

        for (int i = 0; i < size; i++) {

            res.append(data[i]);
            if (i != size - 1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

}

注：創建數組時，只需ArrayNew arr = new ArrayNew<>(20);即可。

原理：其實，動態數組的原理非常簡單，如果我們希望我們的數組具有可伸縮性，只需要我們在添加或者刪除元素時判斷size是否到達臨界。然后去創建一個新capacity的數組，然后把舊數組的引用指向新數組即可。
所以，我們上述代碼的改變極小，只需要改變add、remove即可。然后添加一個resize方法。

// 往數組的任意位置插入
public void add(int index, E ele) {
    // 插入的索引位不合法
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add failed. index < 0 or index > size");
    }

    // 如果size == data.length，數組長度已滿
    if (size == data.length) {
        resize(data.length * 2);
    }

    // 從index向后的所有元素均向后賦值
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = ele;
    size++;
}

// 根據索引刪除數組中的第一個ele，返回ele
public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }

    E result = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = (data[i]);
    }
    // 空間釋放，垃圾回收會自動回收
    data[--size] = null;

    // 減小數組長度，不要浪費空間
    if (size == data.length / 2 && size != 0) {
        resize(size);
    }

    return result;
}

// 自動伸縮數組
private void resize(int newCapacity) {
    E[] newData = (E[])new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData;
}

通過上面的分析和代碼實現，我們封裝了一個自己的數組，并且實現了一些數組最基本的功能，包括支持增、刪、改、查、支持任意數據類型以及動態數組。那么我們就來分析一下我們自己封裝數組的復雜度。

但是：在我們的數組中，增和刪我們都調用了resize方法，如果size < data.length，其實我們執行addLast復雜度只是O(1)而已（removeLast同理）。所以，我們應該怎么去分析resize方法所帶來的復雜度呢？

讓我們拿 增 來舉例

其實，在執行addLast的時候，我們并不是每次都會觸發resize方法，更多的時候，復雜度只是O(1)而已。
比方說：
當前的capacity = 8，并且每一次添加操作都使用addLast，第9次addLast操作，觸發resize，總共17次基本操作（resize方法會進行8次操作，addLast方法進行9次操作）。平均，每次addLast操作，進行2次基本操作（17 / 9 ≈ 2）。
假設：
capacity = n， n + 1次addLast，觸發resize，總共進行了2n + 1次操作，平均每次addLast操作，進行了2次基本操作。

這樣均攤計算，時間復雜度是O(1)！

讓我們來假設這樣一種情況：
當size == data.length時，我們執行了addLast方法添加一個元素，這個時候我們需要去執行resize方法，此時，addLast的復雜度為O(n)。
然后，我去removeLast，此時的removeLast復雜度也是O(n)。
再然后，我再去執行addLast。
.
.
.

有沒有發現，在這樣一種極端情況下，addLast和removeLast的復雜度變成了O(n)，其實，這個就是復雜度的震蕩。

為什么我們會產生這種震蕩？

add情況下，我們去擴容數組無可厚非。但是remove情況下，我們立刻去縮容數組就有點不合適了。

怎么去解決這種情況？

因為我們之前采取的措施是Eager

所以，我們采取一種Lazy的方式：當size == data.length / 2，我們不要立刻縮容，當size == data.length / 4時，我們才去縮容，就可以很好的解決這種震蕩。

具體代碼如下，其實只是對remove進行了極小的改變

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }
    
    E result = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    // 空間釋放，垃圾回收會自動回收
    data[--size] = null;

    // 減小數組長度，不要浪費空間，防止震蕩
    if (size == data.length / 4 && data.length / 2 != 0) {
        resize(data.length / 2);
    }

    return result;
}