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

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

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

int[] arr = new int[10];

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

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

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

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

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

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

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

public class Array {

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

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

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

    // 數(shù)組的實(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++;
}

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

// 最后一個(gè)位置插入
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ù)組中的第一個(gè)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];
}

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

// 刪除最后一個(gè)
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)建了一個(gè)最最最最最基本的數(shù)組類（見下圖）。當(dāng)然，你也可以去添加一些自己需要的方法，例如：removeAll、findAll之類的。

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

首先，為什么我要在任意這兩個(gè)字加上引號(hào)，因?yàn)閖ava的泛型不支持基本數(shù)據(jù)類型，只能是類的對(duì)象。
但是，這并不代表如果我們使用了泛型，就不可以使用基本數(shù)據(jù)類型了，因?yàn)槊恳粋€(gè)基本數(shù)據(jù)類型都有一個(gè)對(duì)應(yīng)的包裝類。
使用泛型的時(shí)候，我們只需要傳入對(duì)應(yīng)的包裝類即可。

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

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

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

    // 數(shù)組的實(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++;
    }

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

    // 最后一個(gè)位置插入
    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ù)組中的第一個(gè)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]);
        }
        // 空間釋放，垃圾回收會(huì)自動(dòng)回收
        data[--size] = null;

        return result;
    }

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

    // 刪除最后一個(gè)
    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ù)組時(shí)，只需ArrayNew arr = new ArrayNew<>(20);即可。

原理：其實(shí)，動(dòng)態(tài)數(shù)組的原理非常簡單，如果我們希望我們的數(shù)組具有可伸縮性，只需要我們?cè)谔砑踊蛘邉h除元素時(shí)判斷size是否到達(dá)臨界。然后去創(chuàng)建一個(gè)新capacity的數(shù)組，然后把舊數(shù)組的引用指向新數(shù)組即可。
所以，我們上述代碼的改變極小，只需要改變add、remove即可。然后添加一個(gè)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ù)組中的第一個(gè)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]);
    }
    // 空間釋放，垃圾回收會(huì)自動(dòng)回收
    data[--size] = null;

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

    return result;
}

// 自動(dòng)伸縮數(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;
}

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

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

讓我們拿 增 來舉例

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

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

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

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

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

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

怎么去解決這種情況？

因?yàn)槲覀冎安扇〉拇胧┦?b>Eager

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

具體代碼如下，其實(shí)只是對(duì)remove進(jìn)行了極小的改變

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];
    }
    // 空間釋放，垃圾回收會(huì)自動(dòng)回收
    data[--size] = null;

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

    return result;
}