摘要：我理解的數(shù)據(jù)結(jié)構(gòu)一數(shù)組首先，我是一個，但是畢竟是一個腳本語言，如果使用腳本語言去理解數(shù)據(jù)結(jié)構(gòu)具有一定的局限性。

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

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

int[] arr = new int[10];

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

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

數(shù)組最大的優(yōu)點：根據(jù)索引快速查詢。如：arr[2]。

數(shù)組最好應(yīng)用于“索引有語意”的情況下。

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

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

學(xué)習(xí)任何一個數(shù)據(jù)結(jié)構(gòu)，CRUD必不可少。下面，讓我們來一起一步步完善屬于我們自己的數(shù)組的增、刪、改、查

public class Array {

    // 數(shù)組的實際大小
    private int size;
    // 數(shù)組
    private int[] data;

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

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

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

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

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

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

    // 數(shù)組已滿
    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;
}

// 根據(jù)索引刪除數(shù)組中的第一個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();
}

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

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

但是，我們現(xiàn)在的數(shù)組只支持int類型，太過局限。接下來，我們?nèi)ソo我們的數(shù)組升華一哈~

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

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

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

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

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

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

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

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

        // 數(shù)組已滿
        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;
    }

    // 根據(jù)索引刪除數(shù)組中的第一個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);
        }
    }

    // 查詢數(shù)組中是否包含元素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();
    }

}

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

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

// 往數(shù)組的任意位置插入
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，數(shù)組長度已滿
    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++;
}

// 根據(jù)索引刪除數(shù)組中的第一個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;

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

    return result;
}

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

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

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

讓我們拿 增 來舉例

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

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

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

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

為什么我們會產(chǎn)生這種震蕩？

add情況下，我們?nèi)U容數(shù)組無可厚非。但是remove情況下，我們立刻去縮容數(shù)組就有點不合適了。

怎么去解決這種情況？

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

所以，我們采取一種Lazy的方式：當(dāng)size == data.length / 2，我們不要立刻縮容，當(dāng)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;

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

    return result;
}