0. 序言

• 數(shù)組是線性表的代表，是很多復雜數(shù)據(jù)結構的底層實現(xiàn)；對數(shù)組的特性認識越深刻，對學習和設計復雜的數(shù)據(jù)結構大有裨益，總之不要小瞧數(shù)組。
• 本文為了處理“索引沒有語意”的情況，即當索引沒有語意的時候，如何表示剩余的數(shù)組空間空元素這種情況，以及如何添加元素和如何刪除元素（Java中給出的數(shù)組是沒有添加元素和刪除元素的功能的，為了處理索引沒有語意的情況以及更好的理解Java的數(shù)組，我們二次封裝了自己的數(shù)組類，實現(xiàn)增刪改查【一些復雜數(shù)據(jù)結構的背后都有數(shù)組的身影，而且通過數(shù)組的二次封裝實現(xiàn)增刪改查】，為后面學習棧、隊列等做準備）。
• 這里我們實現(xiàn)一個動態(tài)數(shù)組，來實現(xiàn)增刪改查以及實現(xiàn)動態(tài)擴容和縮容，避免內存空間的浪費。而這里所說的“動態(tài)數(shù)組”，當你看完這篇文章后，你會發(fā)現(xiàn)這個動態(tài)數(shù)組的底層其實是一個靜態(tài)數(shù)組，只不過是通過resize來解決固定容量的問題。
• 如果你覺得我對第二段話不是很理解，那么不妨一點點往下看，終有柳暗花明又一村的那一刻。

1. 數(shù)組基礎

• 本質：數(shù)組是典型的線性表，由N個具有相同類型的數(shù)據(jù)元素組成的有限序列。
• 特征：元素之間的關系是一對一的關系，即除了第一個和最后一個元素之外，其他元素都是首尾相接的。
• 類型：數(shù)組是靜態(tài)數(shù)據(jù)結構，在內存中的空間分配是連續(xù)的，用于區(qū)分各個元素的數(shù)字編號稱為下標或索引。

2. 數(shù)組優(yōu)缺點

• 優(yōu)點：
  ① 設計時相當簡單。
  ② 讀取和修改列表中的任一元素的時間都是固定的。
• 缺點：
  ① 刪除和添加數(shù)據(jù)時需要移動大量的數(shù)據(jù)。
  ② 在編譯器就要把內存分配給相關變量，所以在創(chuàng)建初期，必須事先聲明最大可能需要的固定存儲空間，這就可能造成內存的浪費。

3.數(shù)組代碼展示

• 聲明

int[] arr = new int[10];
int[] scores = new int[]{100,99,98};

• 大小

arr.length

• 遍歷

for (int i = 0; i <arr.length; i++) {
            
}
for (int score:scores) {
    System.out.println(score);
}

• 增加和修改

arr[i] = i;

4. 數(shù)組需注意的地方

• 數(shù)組最大的優(yōu)點：快速查詢
  因為是靜態(tài)數(shù)據(jù)結構，在內存中是連續(xù)分配的空間，根據(jù)索引就可以區(qū)分元素所帶來的好處就是根據(jù)索引就可以快速查詢元素。
• 數(shù)組最好應用于“索引有語意"的情況
  比如查詢學生的成績，只需要讓學號作為索引，根據(jù)學號來查成績。但如果索引沒有語意的話，就無法根據(jù)索引快速查詢元素。
• 并非所有有語意的索引都適用于數(shù)組
  比如查詢學生的成績，你可以把身份證號作為索引來區(qū)分學生的成績，這明顯是有語意的。但如果索引是身份證號，在創(chuàng)建數(shù)組的時候就需要開辟超級大的內存空間，顯然這是不合理的。

5. 動態(tài)數(shù)組的設計

定義自己的數(shù)組類

public class Array {
    private int[] data;
    private int size;

    // 構造函數(shù)，傳入數(shù)組的容量capacity構造Array
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    // 無參數(shù)的構造函數(shù)，默認數(shù)組的容量capacity = 10
    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;
    }
}

說明：
① capacity是創(chuàng)建數(shù)組時設置的數(shù)組的最大可容納的元素數(shù)，即數(shù)組的length。
② size是當前數(shù)組中元素的個數(shù)，數(shù)組初始化的時候，size = 0 ，指向數(shù)組中索引為0的地方。
③ data是我們定義的數(shù)組，如果沒有給定數(shù)組的大小，默認大小是10.
④ isEmpty是判斷數(shù)組是否為空。

6. 添加元素

添加元素

當添加一個元素的時候，size的個數(shù)是1，此時指向索引是1的地方。注意：我們不允許在索引0沒有元素的情況下，往索引1的位置添加元素，也就是添加元素的時候，索引不能大于size。

添加元素到指定索引.jpg

假設數(shù)組中有4個元素，當往索引1的位置添加元素的時候，元素99需要首先先往后移動1位，以此類推，元素88再往后移動1位，元素77再往后移動1位，這個時候索引為1的地方的元素值依然是77，然后把索引為1的位置的元素77替換為我們想要設置的元素值即可，當然最后需要把size往后移動1位。

  // 在第index個位置插入一個新元素e
    public void add(int index, int e) {
        if (size == data.length) // 1
            throw new IllegalArgumentException("AddLast failed. Array is full");

        if (index < 0 || index > size) { // 2
            throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
        }

        for (int i = size - 1; i >= index; i--) // 3
            data[i + 1] = data[i];

        data[index] = e; // 4
        size++; // 5
    }

說明：
① 代碼1：當數(shù)組中的元素個數(shù)達到數(shù)組的最大存儲空間的時候，不允許添加元素并拋出異常。
② 代碼2：不允許向索引小于0以及索引比size大的地方添加數(shù)據(jù)并拋出異常。
③ 代碼3：size-1位置到等于我們指定的添加元素的索引的位置的元素全部往后挪動1位，即賦值給后1位且從后開始執(zhí)行。
④ 代碼4：把index位置的元素替換為我們想要設置的元素e。
⑤ 代碼5：size的位置往后移動1位。
既然有了添加元素的方法，那么可以衍生出來往數(shù)組第一個位置和最后一個位置添加元素的方法：

  // 向第一個索引位置添加一個元素
    public void addFirst(int e) {
        add(0, e);
    }

    // 向所有元素后添加一個新元素
    public void addLast(int e) {
        add(size, e);
    }

7. 查詢和修改元素

• 查詢數(shù)組內容

 @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append(String.format("Array: size = %d,capacity = %d\n", 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();
    }

在這里我們重寫了類的toString方法，用來打印data數(shù)組中的內容，以便我們進行我們的方法測試。

• 檢測

public class TestArray {
    public static void main(String[] args){
        Array array = new Array(20);
        for (int i = 0; i < 10 ; i++) {
            array.addLast(i);
        }
        System.out.println(array);

        array.add(1,100);
        System.out.println(array);

        array.addFirst(-1);
        System.out.println(array);
    }
}

Array: size = 10,capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11,capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12,capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

通過以上測試：添加元素的三個方法都是正確的。

• 查詢元素

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

    // 獲取數(shù)組中最后一個元素
    public E getLast() {
        return get(size - 1);
    }

    // 獲取數(shù)組中第一個元素
    public E getFirst() {
        return get(0);
    }

• 修改元素

    // 修改index索引位置的元素為e
    void set(int index, int e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        data[index] = e;
    }

8. 包含、搜索和刪除

• 包含和搜索

    // 查找數(shù)組中是否有元素e
    public boolean contains(int e){
        for (int i = 0; i < size ; i++) {
            if (data[i] == e)
                return true;
        }
        return false;
    }

    // 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1
    public int find(int e){
         for (int i = 0; i < size ; i++) {
            if (data[i] == e)
                return i;
        }
        return -1;
    }

當包含元素e的時候返回true，否則返回false。當數(shù)組中含有元素e的時候，返回e元素所在的索引，否則返回-1。

• 刪除指定索引的元素

  
  
  刪除指定位置的元素
  
  

  當要刪除索引為1的元素的時候，索引2、3和4位置的元素都會往前面移動1位，所謂移動1位指的是索引為2的元素值賦值給索引1的元素，索引為3的元素值賦值給索引2的元素，索引為4的元素值賦值給索引3的元素。最后別忘記size往前移動1位。

  
  
  刪除指定位置的元素.jpg
  
  可能你會說size一般指向的沒有元素的索引，這里size指向了100，會不會有問題呢？答案是否定的，因為我們操作索引上的元素的時候，會校驗索引的合法性。

    // 從數(shù)組中刪除index位置的元素，返回刪除的元素
    public int remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        int ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        return ret;
    }

有了刪除的方法，可以設計刪除數(shù)組中第一個元素和最后一個元素的方法：

    // 從數(shù)組中刪除第一個元素，返回刪除的元素
    public int removeFirst(){
        return remove(0);
    }

    // 從數(shù)組中刪除最后一個元素，返回刪除的元素
    public int removeLast(){
        return remove(size-1);
    }

• 刪除指定的元素

    // 從數(shù)組中刪除元素e
    public void removeElement(int e){
        int index = find(e);
        if (index != -1)
            remove(index);
    }

這里有兩點需要注意：
① 這里的刪除元素的方法，只能刪除一個元素，即可能存在相同的兩個或多個元素，而這個方法只會刪除其中一個元素。同樣，find方法也存在相同的問題，感興趣的可以對方法重新設計。
② 可能你會說這個方法沒有返回成功或者失敗。這個你也可以自行設計。
而兩項只是設計上的問題，方法并沒有問題，暫時先這樣，因為這不是重點。

• 檢測

//        [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        array.remove(2);
        System.out.println(array);

        array.removeElement(4);
        System.out.println(array);
        
        array.removeFirst();
        System.out.println(array);
        
        array.removeLast();
        System.out.println(array);

        int i = array.find(0);
        System.out.println(i);

        boolean contains = array.contains(0);
        System.out.println(contains);

        int i1 = array.get(0);
        System.out.println(i1);

        array.set(0,10);
        System.out.println(array);

        Array: size = 11,capacity = 20
        [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        Array: size = 10,capacity = 20
        [-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
        Array: size = 9,capacity = 20
        [0, 1, 2, 3, 5, 6, 7, 8, 9]
        Array: size = 8,capacity = 20
        [0, 1, 2, 3, 5, 6, 7, 8]
        0
        true
        Array: size = 8,capacity = 20
        [10, 1, 2, 3, 5, 6, 7, 8]

通過檢測，會發(fā)現(xiàn)以上的方法正確，讓我們繼續(xù)。

9. 泛型

以上我的數(shù)組類Array，只能放置int數(shù)據(jù)類型的數(shù)據(jù)，為了讓Array可以放置“任何”數(shù)據(jù)類型，我們選擇使用泛型，當然“任何”二字之所以加引號，是因為數(shù)據(jù)類型不可以是基本數(shù)據(jù)類型，只能是類對象，所以我們定義基本數(shù)據(jù)類型的包裝類即可，這樣當遇到基本數(shù)據(jù)類型的時候，Java會自動裝箱為對應的包裝類。

public class Array<E> {
    private E[] data;
    private int size;

    // 構造函數(shù)，傳入數(shù)組的容量capacity構造Array
    public Array(int capacity) {
        data = (E[]) new Object[capacity]; // 4
        size = 0;
    }

    // 無參數(shù)的構造函數(shù)，默認數(shù)組的容量capacity = 10
    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;
    }

    // 向第一個索引位置添加一個元素
    public void addFirst(E e) {
        add(0, e);
    }

    // 向所有元素后添加一個新元素
    public void addLast(E e) {
        add(size, e);
    }

    // 在第index個位置插入一個新元素e
    public void add(int index, E e) {
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. Array is full");

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
        }

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        data[index] = e;
        size++;
    }

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

    // 修改index索引位置的元素為e
    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找數(shù)組中是否有元素e
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) // 1
                return true;
        }
        return false;
    }

    // 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i] .equals(e) ) // 2
                return i;
        }
        return -1;
    }

    // 從數(shù)組中刪除index位置的元素，返回刪除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null; // 程序優(yōu)化——實際上是一個閑散的對象！=內存泄露 // 3
        return ret;
    }

    // 從數(shù)組中刪除第一個元素，返回刪除的元素
    public E removeFirst() {
        return remove(0);
    }

    // 從數(shù)組中刪除最后一個元素，返回刪除的元素
    public E removeLast() {
        return remove(size - 1);
    }

    // 從數(shù)組中刪除元素e
    public void removeElement(E e) {
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append(String.format("Array: size = %d,capacity = %d\n", 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();
    }
}

有兩個地方需要注意：
① 代碼1和代碼2：類對象之間的對比用的是equals而不是“=”
② 代碼3：size此時指向的是一個對象的引用，出于程序優(yōu)化的目的，這里選擇把它置為null。這個對象的引用并非是內存泄露，因為我們在數(shù)組后面插入數(shù)據(jù)后，data[size]所指代的對象引用就會發(fā)生變化，之前的對象的引用就會引起垃圾回收機制的注意，根據(jù)垃圾回收機制會被回收掉?？傊且粋€閑散的對象，而非內存泄露，處理它是出于程序優(yōu)化的目的。
③ 代碼4：泛型并不能new出來，而是需要new一個Object對象，然后強轉為泛型對象。

Array<Integer> array = new Array<>(20);

之前我們測試數(shù)組，就可以修改為Interger類型即可。

public class Student {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public String toString() {
        return String.format("Student(name:%s,score:%d",name,score);
    }

    public static void main(String[] args){
        Array<Student> array = new Array<>();
        array.addLast(new Student("小明",99));
        array.addLast(new Student("小紅",100));
        System.out.println(array);
    }
}

Array: size = 2,capacity = 10
[Student(name:小明,score:99, Student(name:小紅,score:100]

證明我們的泛型添加正確，達到了預期效果。

10. 動態(tài)數(shù)組

現(xiàn)在我們的數(shù)組Array依然是一個靜態(tài)數(shù)組，如果開的太大可能造成空間的浪費，如果開的太小可能空間不夠，所以這里我們讓數(shù)組Array容量動態(tài)伸縮，即讓Array成為一個動態(tài)數(shù)組。

動態(tài)數(shù)組

原來的數(shù)組為data，數(shù)組中有6個元素，當我們想再添加新的元素的時候，由于數(shù)組空間不夠，所以我們新創(chuàng)建一個數(shù)組newdata，數(shù)組容量大小是data數(shù)組的2倍，然后遍歷data數(shù)組中的元素，賦值到newdata中，然后把data數(shù)組的引入指向newdata數(shù)組，這樣以來data數(shù)組就擁有了動態(tài)擴容的技能。而為什么是之前數(shù)組容量的2倍，而不是10或者1000呢？是因為這里不想引入一個常數(shù)，因為10可能擴容得太小，1000可能擴容的太大，而2倍可以和之前的數(shù)組容量相關，它們處在一個數(shù)量級上，所以更加合適，而為什么是2倍，而不是1.5倍等等，后續(xù)會詳細探討這部分內容。

 // 在第index個位置插入一個新元素e
    public void add(int index, E e) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
        }

        if (size == data.length)
            resize(2 * data.length);

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        data[index] = e;
        size++;
    }

    // 數(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;
     }

添加元素，如果發(fā)現(xiàn)size == data.length，那么就執(zhí)行擴容函數(shù)resize，數(shù)組的擴容大小是之前的2倍，然后把之前的數(shù)組元素賦值給新的數(shù)組，然后讓原來的數(shù)組引用指向新創(chuàng)建的數(shù)組，由于newData是局部變量，在函數(shù)執(zhí)行完以后它就失效了，而data是成員變量，所以data依然有效。

        Array<Integer> array = new Array<>();
        for (int i = 0; i < 10 ; i++) {
            array.addLast(i);
        }
        System.out.println(array);

        array.add(1,100);
        System.out.println(array);

        array.addFirst(-1);
        System.out.println(array);

        Array: size = 10,capacity = 10
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        Array: size = 11,capacity = 20
        [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        Array: size = 12,capacity = 20
        [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

從以上示例來看，數(shù)組Array自動擴容了，非常酷！那擴容實現(xiàn)了，縮容也很簡單，當我們刪除元素，發(fā)現(xiàn)現(xiàn)有的數(shù)組的元素size是容量capacity的一半的時候，我們調用下resize，讓數(shù)組的容量變?yōu)橹暗?/2：

    // 從數(shù)組中刪除index位置的元素，返回刪除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null; // 程序優(yōu)化——實際上是一個閑散的對象！=內存泄露

        if (size == data.length / 2)
            resize(data.length/2);
        return ret;
    }

讓我們測試下：

      array.remove(2);
      System.out.println(array);

      array.removeElement(4);
      System.out.println(array);

      array.removeFirst();
      System.out.println(array);

      Array: size = 11,capacity = 20
      [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
      Array: size = 10,capacity = 10
      [-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
      Array: size = 9,capacity = 10
      [0, 1, 2, 3, 5, 6, 7, 8, 9]
      Array: size = 8,capacity = 10
      [0, 1, 2, 3, 5, 6, 7, 8]

當數(shù)組的size為11的時候，數(shù)組的容量并沒有發(fā)生變化，當數(shù)組的size為10的時候，數(shù)組容量縮小到了10.非?？幔?/p>

11. 復雜度分析

如果對復雜度分析不了解，請?zhí)D閱讀：http://www.itdecent.cn/p/2d5e5f1bc77e
如果對平均時間復雜度不了解，請?zhí)D閱讀：http://www.itdecent.cn/p/08d1d509c5db
如果對均攤時間復雜度不了解，請?zhí)D閱讀：http://www.itdecent.cn/p/59f380c6ffcd

• 添加操作
  ① addLast(e)---O(1)
  ② addFirst(e)---O(n)
  因為需要進行數(shù)據(jù)的搬移工作，所以時間復雜度為O(n)
  ③ add(index,e)---O(n)
  ④ resize---O(n)
  一共是n個索引，索引范圍是0～n-1，索引添加數(shù)據(jù)而造成的搬移數(shù)據(jù)量分別是1+2+3+...+n-1+n，每個位置被插入數(shù)據(jù)的概率是1/2,所以平均數(shù)據(jù)搬移量是1/2乘以（1+2+3+...+n-1+n)/n = (n+1)/4個數(shù)據(jù)，用大O時間復雜度表示法表示平均時間復雜度為O(n).
  綜上：根據(jù)時間復雜度分析之加法法則，添加操作的時間復雜度為O(n)
• 刪除操作
  ① removeLast(e)---O(1)
  ② removeFirst(e)---O(n)
  ③ remove(index,e)---O(n)(同添加操作分析)
  ④ resize---O(n)
  綜上：根據(jù)時間復雜度分析之加法法則，添加操作的時間復雜度為O(n)
• 修改操作
  set(index,e)---O(1)
  數(shù)組支持隨機訪問，這是數(shù)組最大的優(yōu)勢。
• 查找操作
  ① get(index)---O(1)
  ② contains(e)---O(n)
  ③ find(e)---O(n)

綜上：

• 增：O(n)
• 刪：O(n)
• 改：已知索引O(1);未知索引O(n)
• 查：已知索引O(1);未知索引O(n)

12.addLast+resize的時間復雜度

添加操作的addLast的時間復雜度是O(1),resize的時間復雜度是O(n),而resize只有滿足條件的時候才會觸發(fā)，所以不能簡單的說addLast+reszie的時間復雜度就是O(n),這個時候就應該用均攤時間復雜度分析，不了解均攤時間復雜度分析的，請?zhí)D閱讀：http://www.itdecent.cn/p/59f380c6ffcd

假設capacity = 8 ，并且每次添加操作都使用addLast，那9次的addLast操作，才會觸發(fā)resize，總共進行了17次基本操作。根據(jù)均攤復雜度分析，平均每次addLast操作進行2次基本操作。即假設capacity=n，n+1次addLast，觸發(fā)resize，總共進行2n+1次操作，平均每次addLast操作，進行2次基本操作。

綜上：addLast+resize，根據(jù)均攤時間復雜度分析，得知時間復雜度為O(1)。同理，removeLast操作，均攤復雜度也為O(1)。

13. 復雜度震蕩

看下我們之間的addLast和removeLast操作，會發(fā)現(xiàn)有點問題。addLast當size == capacity的時候會進行擴容操作，而此時執(zhí)行removeLast操作，由于size =capacity/2會執(zhí)行縮容的操作，循環(huán)往復的話，就非常不合理，addLast和removeLast都導致了時間復雜度為O(n)的操作，我們稱這種情況為復雜度震蕩。

解決方案：每次removeLast時，size = capacity/4的時候再進行縮容操作—稱為Lazy解決方案：

 // 從數(shù)組中刪除index位置的元素，返回刪除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null; // 程序優(yōu)化——實際上是一個閑散的對象！=內存泄露

        if (size == data.length / 4 && data.length/2 !=0) // 1
            resize(data.length/2);
        return ret;
    }

代碼1處，需要注意data.length/2可能為0，畢竟數(shù)組容量不能初始化為0，所以這里要注意。

14. 后續(xù)

如果大家喜歡這篇文章，歡迎點贊！
如果想看更多 數(shù)據(jù)結構 方面的文章，歡迎關注!