摘要：數組中有一個很重要的概念叫做索引，也就是數組元素的編號，編號從開始的，所以最后一個元素的索引為數組的長度即，可以通過數組名索引來訪問數組中的元素。

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文章大概的內容如下：
Arrays(數組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)

源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對數據結構想了解并且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學習數據結構的人或者正在學習數據結構的人群有幫助。

把數據碼成一排進行存放

強語言中數據的類型是確認的，

弱語言中數據的類型是不確認的，

但是也有方法可以進行確認。

數組就是把一個一個的數據近挨著排成一排。

可以給一個數組起一個名字，起名字要有語義化。

數組中有一個很重要的概念叫做索引，

也就是數組元素的編號，編號從 0 開始的，

所以最后一個元素的索引為數組的長度-1 即 n-1，

可以通過數組名[索引]來訪問數組中的元素。

java 中的數組是有局限性的。

   public class Main {

         public static void main(String[] args) {
            // 輸出
               System.out.println("Array");

               // 定義數組
               int[] arr = new int[10];

               // 循環賦值
               for (int i = 0; i < arr.length; i++) {
                     arr[i] = i;
               }

               // 定義數組
               int[] scores = new int[]{100, 99, 88};

               // for循環遍歷 數組
               for (int i = 0; i < scores.length ; i++) {
                     System.out.println(scores[i]);
               }

               // 修改數組中某個元素
               scores[0] = 60;

               // foreach 遍歷數組
               for (int score: scores) {
                     System.out.println(score);
               }

         }
   }

數組的索引可以有語意也可以沒有語意。

如 scores[2] 代表一個班級中第三個學生。

數組的最大優點

快速查詢，如 scores[2]

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

如果索引沒有語意的話，

那么使用別的數據結構那會是一個更好的選擇。

計算機處理的問題有千千萬萬個

有很多場景即使能給索引定義出來語意，

但是它有可能不適用于數組。

比如身份證號可以設計為一個數組，

用來存儲相應的工資情況，

如果想索引到不同的人，

那么使用身份證號就是一個很好的方式，

但是身份證號不能作為一個數組的索引，

因為這個身份證號太大了，

如果想要使用身份證號作為一個數組的索引，

那么開辟的空間會非常的大，

例如arr[110103198512112312]，

對于一般的計算機來說開辟這樣的一塊兒空間，

是非常不值當的，甚至是不可能的，

而且大部分空間都是浪費的，

比如你就想考察 100 個人的工資情況，

你卻開辟了 1000 兆倍的空間。

數組也可以處理“索引沒有語意”的情況。

在索引有語意的情況下使用數組非常簡單，

直接就可以查到相應的數據。

在索引沒有語義的情況下使用數組，

那么就會產生很多新的問題。

因為這個時候數組只是一個待存

放那些要考察的數據的空間，

例如你開辟了 8 個元素的空間，

但是你只考察 2 個元素，

此時就有問題了，剩下的空間都沒有元素，

可能訪問剩下的空間就是非法的，

因為從用戶的角度上來看是沒有那么多元素的，

只有兩個元素。

索引沒有語意，如何表示沒有元素？

如何添加元素？如何刪除元素？

等等更多問題，

例如添加元素時，

因為數組創建的時候數組的大小就固定了。

在 java 中數組沒有這些功能，

所以需要基于 Java 的數組，

二次封裝屬于我們自己的數組類。

也就是將原本的靜態數據變成動態的數組。

將原本 Java 中的數組封裝到一個類中，

從而封裝一個屬于自己的數組，這個類就叫做 MyArray，

在這個類中封裝一個 java 的數組，這個數組叫做 data，

對這個數組進行增刪改插等等的功能。

數據結構的本質也是存儲數據，

之后再進行高效的對這些數據進行操作，

只不過你設計的數據結構會把這些數據存儲在內存中，

所以針對這些數據結構的所添加的操作在大的類別的劃分上，

也是增刪改查。

針對不同的數據結構，

對應的增刪改查的方式是截然不同的，

甚至某些數據結構會忽略掉增刪改查中的某一個操作，

但是增刪改查可以作為研究某一個數據結構的相應的脈絡，

數組本身是靜態的，必須在創建的時候指定他的大小，

可以把這個容量叫做 capacity，

也就是數組空間最多可以裝多少個元素，

數組空間最多可以裝多少個元素與

數組中實際裝多少個元素是沒有關系的，

因為這是兩回事兒，

數組中實際能夠裝多少個元素可以叫做 size，

通過它來控制，在初始化的時候，

數組中一個元素都沒有，所以 size 為 0，

這個 size 相當于數組中第一個沒有盛放元素的相應索引，

增加數組元素和刪除數組元素的時候就要維護這個 size。

代碼示例(class: MyArray)

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

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

         // 無參數的構造函數，默認數組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

         // 獲取數組中的元素實際個數
         public int getSize () {
               return size;
         }

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

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

向數組添加元素最簡單的形式

就是在數組的末尾添加一個元素，

size 這個變量其實就是指向數組中的末尾，

添加完元素之后其實也需要維護這個 size，

因為數組中的元素多了一個，所以要讓它加加。

如果是給元素進行插入的操作

那么要先判數組的容量是否已經裝滿了，

然后再判斷索引是否小于 0 或者大于 size，

都沒有問題了，就可以根據索引來進行插入了，

插入的原理就是那個索引位置及其后的元素，

全都都往后移動一位，所以循環是從后往前的，

最后讓該索引處的舊元素被新元素覆蓋，

但舊元素并沒消失，而是位置往后移動了一位，

最后要記得維護 size。

向數組中添加元素可以復用向數組中插入元素的方法，

因為插入元素的方法也是在給數組添加元素，

并且插入元素的方法可以在任何位置插入新元素，

那么就可以擴展兩個方法，

一個插入到數組最前面（插入到索引為 0 的位置），

一個是插入到數組最后面

（插入到索引為 數組最后一個元素的索引+1 的位置）。

給數組添加元素的時候如果元素為數字（添加時可排序可不排序）

那么每一次添加操作時可以給數組中的元素進行排序，

排序方式是按照從小到大來進行排序。

先判斷添加的這個元素大于數組中哪一個元素，

然后將那個元素及其后面的所有元素往后移一位，

最后將添加的這個元素插入到那個元素后面。

先要對數組中的容量進行判斷，

如果超過了就不添加，并且報錯，

每次添加之前要判斷一下插入的位置，

它后面還有沒有元素或者這個數組是否為空。

記住每次添加操作都要維護 size 這個變量。

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

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

         // 無參數的構造函數，默認數組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

         // 獲取數組中的元素實際個數
         public int getSize () {
               return size;
         }

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

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

         // 給數組添加一個新元素
         public void add (int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

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

         // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
         public void addLast (int e) {

               // 復用插入元素的方法
               insert(size, e);
         }

         // 在所有元素前添加一個新元素 unshift
         public void addFirst (int e) {
               insert(0, e);
         }

         // 在index索引的位置插入一個新元素e
         public void insert (int index, int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException(
                                 "insert error. require index < 0 or index > size"
                     );
               }

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

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

如果你要覆蓋父類中的方法，記得要加備注

如 // @Override: 方法名 日期-開發人員

獲取自定義數組中指定索引位置的元素

首先要判斷索引是否小于 0 或者

大于等于 實際元素的個數，都沒有問題時，

就可以返回索引位置的元素了。

用戶沒有辦法去訪問那些沒有使用的數組空間。

修改自動數組中指定索引位置的元素

和獲取是一樣的，要先判斷，

只能設置已有存在的元素索引位置的元素，

用戶沒有辦法去修改那些沒有使用的數組空間。

MyArray

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

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

         // 無參數的構造函數，默認數組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

         // 獲取數組中的元素實際個數
         public int getSize () {
               return size;
         }

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

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

         // 給數組添加一個新元素
         public void add (int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

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

         // 向所有元素后添加一個新元素 （與 add方法功能一樣）push
         public void addLast (int e) {

               // 復用插入元素的方法
               insert(size, e);
         }

         // 在所有元素前添加一個新元素 unshift
         public void addFirst (int e) {

               insert(0, e);
         }

         // 在index索引的位置插入一個新元素e
         public void insert (int index, int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("insert error. require index < 0 or index > size");
               }

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

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

         // 獲取index索引位置的元素
         public int get (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size ");
               }
               return data[index];
         }

         // 修改index索引位置的元素為e
         public void  set (int index, int e) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size ");
               }
               data[index] = e;
         }

         @Override
         // @Override: 方法名 日期-開發人員
         public String toString () {

               StringBuilder sb = new StringBuilder();
               String arrInfo = "Array: size = %d，capacity = %d
";
               sb.append(String.format(arrInfo, size, data.length));
               sb.append("[");
               for (int i = 0; i < size - 1; i ++) {
                     sb.append(data[i]);
                     sb.append(",");
               }
               if(!isEmpty()) {
                     sb.append(data[size - 1]);
               }
               sb.append("]");

               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
      // write your code here
               MyArray ma = new MyArray(20);
               for (int i = 1; i <= 10 ; i++) {
                     ma.add(i);
               }
               System.out.println(ma);

               ma.insert(1, 200);
               System.out.println(ma);

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

               ma.addLast(9999);
               System.out.println(ma);

               ma.set(5, 8888);
               System.out.println(ma.get(5));
         }
   }

繼續對自定義的數組增加新功能

包含、搜索、刪除這三個功能。

包含：

判斷數組中 是否存在這個元素，

不存在返回 false。

搜索：

根據這個元素來進行 索引的獲取，

找不到返回 非法索引 -1。

刪除：

首先要判斷索引的合法性，

其次這個操作與插入的操作其實原理類似，

只不過是一個反向的過程，

指定索引位置的元素其后面的元素的位置

全部往前一位，循環時 初始索引為 指定的這個索引，

從前往后的不斷向前移動，這樣被刪除的元素就被覆蓋了，

覆蓋之前要保存一下指定索引的元素的值，

這個值要作為返回值來進行返回，

然后讓 size 減減，因為覆蓋掉這個元素，

由于數組訪問會有索引合法性的判斷

一定要小于 size，于是用戶是訪問不到 size 位置的元素了，

所以 size 位置的元素可以不用去處理它，

但你也可以手動的將這個元素值設置為默認值。

有了指定索引刪除某個元素并返回被刪除的這個元素的操作

那么就可以擴展出兩個方法，

和使用插入方法來進行擴展的那兩個方法類似，

分別是 刪除第一個元素和刪除最后一個元素，

并且返回被刪除的元素，

刪除數組元素時會判斷數組索引的合法性，

如果數組為空，那么合法性驗證就無法通過。

根據元素來刪除數組中的某個元素

首先通過 包含 的那個方法來判斷這個元素是否存在，

如果元素不存在那就不進行刪除操作，也可以報一個異常，

如果元素存在，那就根據 搜索 的那個方法來獲取這個元素的索引，

最后根據 獲取到合法索引 來進行元素的刪除。

其實你可以使用通過 搜索 的那個方法直接返回元素的索引，

如果索引合法你就直接刪除，

如果索引不合法那就不刪除然后也可以報一個異常。

可以對那些方法進行擴展

如 刪除數組中所有的指定元素

如 找到數組中所有的指定元素的索引

關于自定義的數組已經實現了很多功能，

但是這個自定義數組還有很多的局限性，

在后面會慢慢解決這些局限性，

如 這個數組能存放的數據類型不能是任意的數據類型，

如果 這個數組的容量是一開始就固定好的，超出就報異常。

MyArray

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

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

         // 無參數的構造函數，默認數組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

         // 獲取數組中的元素實際個數
         public int getSize () {
               return size;
         }

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

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

         // 給數組添加一個新元素
         public void add (int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

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

         // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
         public void addLast (int e) {

               // 復用插入元素的方法
               insert(size, e);
         }

         // 在所有元素前添加一個新元素 unshift
         public void addFirst (int e) {

               insert(0, e);
         }

         // 在index索引的位置插入一個新元素e
         public void insert (int index, int e) {

               if (size == data.length) {
                     throw new IllegalArgumentException("add error. Array is full.");
               }

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("insert error. require index < 0 or index > size");
               }

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

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

         // 獲取index索引位置的元素
         public int get (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size ");
               }
               return data[index];
         }

         // 修改index索引位置的元素為e
         public void  set (int index, int e) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size ");
               }
               data[index] = e;
         }

         // 查找數組中是否有元素e
         public boolean contain (int e) {

               for (int i = 0; i < size; i++) {
                     if (data[i] == e) {
                           return true;
                     }
               }
               return false;
         }

         // 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
         public int find (int e) {

               for (int i = 0; i < size; i++) {
                     if (data[i] == e) {
                           return i;
                     }
               }
               return -1;
         }

         // 查找數組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數組
         public MyArray findAll (int e) {

               MyArray ma = new MyArray(20);

               for (int i = 0; i < size; i++) {
                     if (data[i] == e) {
                           ma.add(i);
                     }
               }

               return  ma;

   //        int[] result = new int[ma.getSize()];
   //        for (int i = 0; i < ma.getSize(); i++) {
   //            result[i] = ma.get(i);
   //        }
   //
   //        return  result;
         }

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

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

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

         // 從數組中刪除所有元素e
         public void removeAllElement (int e) {

               int index = find(e);
               while (index != -1) {
                     remove(index);
                     index = find(e);
               }
   //        while (contain(e)) {
   //            removeElement(e);
   //        }
         }

         // 從數組中刪除index位置的元素, 返回刪除的元素
         public int remove (int index) {

               if (index < 0 || index >= size) {
                     throw new IllegalArgumentException("get error. index < 0 or index >= size ");
               }

               int temp = data[index];

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

               return temp;
         }

         @Override
         // @Override: 方法名 日期-開發人員
         public String toString () {

               StringBuilder sb = new StringBuilder();
               String arrInfo = "Array: size = %d，capacity = %d
";
               sb.append(String.format(arrInfo, size, data.length));
               sb.append("[");
               for (int i = 0; i < size - 1; i ++) {
                     sb.append(data[i]);
                     sb.append(",");
               }
               if(!isEmpty()) {
                     sb.append(data[size - 1]);
               }
               sb.append("]");

               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
               // 創建一個自定義的數組對象
               MyArray ma = new MyArray(20);
               for (int i = 1; i <= 10 ; i++) {
                     ma.add(i);
               }
               /*
               * Array: size = 10，capacity = 20

              */
              System.out.println(ma);

              ma.insert(1, 200);

              /*
               * Array: size = 11，capacity = 20
               * [1,200,2,3,4,5,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.addFirst(-1);
              /*
               * Array: size = 12，capacity = 20
               * [-1,1,200,2,3,4,5,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.addLast(9999);
              /*
               * Array: size = 13，capacity = 20
               * [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
               */
              System.out.println(ma);

              ma.set(5, 8888);
              /*
               * 8888
               */
              System.out.println(ma.get(5));

              /*
               * Array: size = 13，capacity = 20
               * [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
               * true
               * 6
               */
              System.out.println(ma);
              System.out.println(ma.contain(5));
              System.out.println(ma.find(5));

              ma.remove(ma.find(5));
              /*
               * Array: size = 12，capacity = 20
               * [-1,1,200,2,3,8888,6,7,8,9,10,9999]
               */
              System.out.println(ma);

              /*
               * -1
               * 9999
               * Array: size = 10，capacity = 20
               * [1,200,2,3,8888,6,7,8,9,10]
               */
              System.out.println(ma.removeFirst());
              System.out.println(ma.removeLast());
              System.out.println(ma);

              ma.removeElement(8888);
              /*
               * Array: size = 9，capacity = 20
               * [1,200,2,3,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.add(123456);
              ma.add(123456);
              ma.add(123456);
              /*
               * Array: size = 3，capacity = 20
               * [9,10,11]
               * Array: size = 12，capacity = 20
               * [1,200,2,3,6,7,8,9,10,123456,123456,123456]
               */
              System.out.println(ma.findAll(123456));
              System.out.println(ma);

              ma.removeAllElement(123456);
              /*
               * Array: size = 9，capacity = 20
               * [1,200,2,3,6,7,8,9,10]
               */
              System.out.println(ma);
        }
  }

## 讓自己的數組可存放任何數據類類型

1. 泛型技術可以讓數據結構放置“任何”數據類型
2. 在 Java 中泛型的類型不可以是基本數據類型
1. 只能是類類型，也就是說只能存放對象，
2. 不可以存放基本數據類型的值。
3. 在 java 語言中有八種數據基本數據類型
1. boolean、byte、char、short、
2. int、long、float、double。
4. 每個基本數據類型都有對應的包裝類
1. 這樣就把不是類對象這樣的數據變成類對象，
2. Boolean、Byte、Char、Short、
3. Int、Long、Float、Double，
4. 名字完全一樣，只不過首字母進行了大寫，
5. 這些包裝類與他們對應的基本數據類型之間可以無縫的進行轉換
1. 這個自動的轉換過程就叫作自動的加包或者解包，
2. 也就是基本類型在需要的時候會自動轉換為他所對應的包裝類，
3. 而這些包裝類也會在他們需要的時候自動的轉換為
4. 他們所對的基本類型，這樣一來就可以將一個數組變成
5. 一個可以放置任何數據類型的泛型數組。
6. 通過在自定義的數組類型后面加上``
1. E 表示一個任意的類型，
2. 而`<>`表示這個類型擁有了泛型的能力，
3. 在你具體使用的時候可以將`<>`中的 E
4. 改成你想要存放的數據的類型。
7. 泛型這個能力并不是 Java 一開始就有的，
1. 是從 Java1.5 才開始支持的，
2. 在如果在定義的類中使用這個任意類型 E，
3. 需要繞一個彎子，將使用到 E 的地方改成 Object，
4. Object 類是任意類的父類，
5. 然后再對這個類的對象進行強制類型的轉換，
6. 如`(E[])new Object[capacity]`，
7. 這樣的語法是合法的，這樣就相當于在這個類中
8. new 出來一個還沒有指定類型的 E 類型的數組，
9. 當你在使用這個類的時候，那么 E 可以變成任意的類型。
8. 比較泛型 E 類型的對象時不能再用`==`
1. 值比較 用 `==`，
2. 引用比較 用 `equals()`
9. 在刪除操作時
1. java 中有一個垃圾回收機制，
2. 但是如果引用一直存在的話，
3. 就不會回收，所以可以在刪除操作時，
4. 給這個數組 size 位置的元素賦值為 null，
5. 這樣相當于就給元素設置默認值 null 了。
10.   loitering objects != memory leak
11.   閑置的對象并不等于內存泄漏，
12.   只不過是這個對象沒有用了，
13.   還是在這個程序中游蕩，
14.   也沒有辦法被垃圾回收機制回收掉，
15.   但是為了程序優化，
16.   可以手動的把這個閑置的對象去除掉那就更好。
17.   泛型可以存放所有的數據類型
18.   非常的方便，原理還是編譯時的代碼檢查，
19.   最終會編譯成具體的數據類型，
20.   或者原理是泛型中存放的數據類型會被編譯成新的類型。

### 代碼示例`(class: MyArray, class: Main, class: Student)`

1. Myarray

  public class MyArray {
        private E [] data;
        private int size;

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

        // 無參數的構造函數，默認數組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

        // 獲取數組中的元素實際個數
        public int getSize () {
              return size;
        }

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

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

        // 給數組添加一個新元素
        public void add (E e) {

              if (size == data.length) {
                    throw new IllegalArgumentException("add error. Array is full.");
              }

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

        // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
        public void addLast (E e) {

              // 復用插入元素的方法
              insert(size, e);
        }

        // 在所有元素前添加一個新元素 unshift
        public void addFirst (E e) {

              insert(0, e);
        }

        // 在index索引的位置插入一個新元素e
        public void insert (int index, E e) {

              if (size == data.length) {
                    throw new IllegalArgumentException("add error. Array is full.");
              }

              if (index < 0 || index > size) {
                    throw new IllegalArgumentException("insert error. require index < 0 or 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 error. index < 0 or index >= size ");
              }
              return data[index];
        }

        // 修改index索引位置的元素為e
        public void  set (int index, E e) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              data[index] = e;
        }

        // 查找數組中是否有元素e
        public boolean contain (E e) {

              for (int i = 0; i < size; i++) {
  //            if (data[i] == e) { // 值比較 用 ==
                    if (data[i].equals(e)) { // 引用比較 用 equals()

                                return true;
                    }
              }
              return false;
        }

        // 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
        public int find (E e) {

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          return i;
                    }
              }
              return -1;
        }

        // 查找數組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數組
        public MyArray findAll (E e) {

              MyArray ma = new MyArray(20);

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          ma.add(i);
                    }
              }

              return  ma;

  //        int[] result = new int[ma.getSize()];
  //        for (int i = 0; i < ma.getSize(); i++) {
  //            result[i] = ma.get(i);
  //        }
  //
  //        return  result;
        }

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

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

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

        // 從數組中刪除所有元素e
        public void removeAllElement (E e) {

              int index = find(e);
              while (index != -1) {
                    remove(index);
                    index = find(e);
              }
  //        while (contain(e)) {
  //            removeElement(e);
  //        }
        }

        // 從數組中刪除index位置的元素, 返回刪除的元素
        public E remove (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }

              E temp = data[index];

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

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {

              StringBuilder sb = new StringBuilder();
              String arrInfo = "Array: size = %d，capacity = %d
";
              sb.append(String.format(arrInfo, size, data.length));
              sb.append("[");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(data[i]);
                    sb.append(",");
              }
              if(!isEmpty()) {
                    sb.append(data[size - 1]);
              }
              sb.append("]");

              return sb.toString();
        }
  }

2. Main

  public class Main {

        public static void main(String[] args) {
              // 創建一個自定義的數組對象
              MyArray ma = new MyArray(20);
              for (int i = 1; i <= 10 ; i++) {
                    ma.add(i);
              }

              /*
              * Array: size = 10，capacity = 20
              * [1,2,3,4,5,6,7,8,9,10]
              */
              System.out.println(ma);

              ma.insert(1, 200);

              /*
               * Array: size = 11，capacity = 20
               * [1,200,2,3,4,5,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.addFirst(-1);
              /*
               * Array: size = 12，capacity = 20
               * [-1,1,200,2,3,4,5,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.addLast(9999);
              /*
               * Array: size = 13，capacity = 20
               * [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
               */
              System.out.println(ma);

              ma.set(5, 8888);
              /*
               * 8888
               */
              System.out.println(ma.get(5));

              /*
               * Array: size = 13，capacity = 20
               * [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
               * true
               * 6
               */
              System.out.println(ma);
              System.out.println(ma.contain(5));
              System.out.println(ma.find(5));

              ma.remove(ma.find(5));
              /*
               * Array: size = 12，capacity = 20
               * [-1,1,200,2,3,8888,6,7,8,9,10,9999]
               */
              System.out.println(ma);

              /*
               * -1
               * 9999
               * Array: size = 10，capacity = 20
               * [1,200,2,3,8888,6,7,8,9,10]
               */
              System.out.println(ma.removeFirst());
              System.out.println(ma.removeLast());
              System.out.println(ma);

              ma.removeElement(8888);
              /*
               * Array: size = 9，capacity = 20
               * [1,200,2,3,6,7,8,9,10]
               */
              System.out.println(ma);

              ma.add(123456);
              ma.add(123456);
              ma.add(123456);
              /*
               * Array: size = 3，capacity = 20
               * [9,10,11]
               * Array: size = 12，capacity = 20
               * [1,200,2,3,6,7,8,9,10,123456,123456,123456]
               */
              System.out.println(ma.findAll(123456));
              System.out.println(ma);

              ma.removeAllElement(123456);
              /*
               * Array: size = 9，capacity = 20
               * [1,200,2,3,6,7,8,9,10]
               */
              System.out.println(ma);
        }
  }

3. Student

  public class Student {

        private String name;
        private int score;

        public Student(String studentName, int studentScore){
              name = studentName;
              score = studentScore;
        }

        @Override
        // @Override 方法名 日期-開發人員
        public String toString(){
              return String.format("Student(name: %s, score: %d)", name, score);
        }

        // 增加入口方法，就可以直接執行代碼了
        public static void main(String[] args) {

              MyArray arr = new MyArray();
              arr.addLast(new Student("Alice", 100));
              arr.addLast(new Student("Bob", 66));
              arr.addLast(new Student("Charlie", 88));
              System.out.println(arr);
        }
  }

## 讓自己的數組成為動態數組

1. 自定義數組的局限性還有容量為固定的大小，
1. 因為內部還是使用的 java 的靜態數組，
2. 靜態數組的容量從定義開始就是固定的，
3. 如果一開始就把容量開的太大了，
4. 那么就會浪費很多的空間，
5. 如果容量開的太小了，
6. 那就可能存放的空間不夠用。
2. 使用一種解決方案，讓自定義數據的容量可伸縮
1. 讓自定義數組變成一個動態的數組，
2. 當自定義數組中的空間已經滿了，
3. 那就創建一個新的數組，
4. 這個數組的容量定義為原來的容量的兩倍，
5. 然后將舊數組中的元素全部放到新數組中，
6. 以循環的方式放入新數組中。
3. 讓新數組替代掉舊數組，
1. 當`size == capcity`時創建新數組，容量翻倍，
2. 當`size == capcity / 2`時創建新數組，容量縮小一倍，
3. 最終都會讓新數組替代掉舊數組。
4. 使用這種方式會讓整體性能上很有優勢。
5. 在 Java 的動態數組中選擇是擴容倍數是 1.5，
6. 然后無論是 1.5 還是 2 或者 3 都是可以的，
7. 只不過是一個參數的選擇，
8. 你可以根據使用場景來進行擴容。
4. 自定義數組的這些操作及性能需要分析。
1. 也就是要進行一個時間復雜度的分析。

### 代碼示例`(class: MyArray, class: Main)`

1. Myarray

  public class MyArray {
        private E [] data;
        private int size;

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

        // 無參數的構造函數，默認數組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

        // 獲取數組中的元素實際個數
        public int getSize () {
              return size;
        }

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

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

        // 重新給數組擴容
        private void resize (int newCapacity) {

              E[] newData = (E[])new Object[newCapacity];

              int index = size - 1;
              while (index > -1) {
                    newData[index] = get(index);
                    index --;
              }

              data = newData;
        }

        // 給數組添加一個新元素
        public void add (E e) {

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

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

        // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
        public void addLast (E e) {

              // 復用插入元素的方法
              insert(size, e);
        }

        // 在所有元素前添加一個新元素 unshift
        public void addFirst (E e) {

              insert(0, e);
        }

        // 在index索引的位置插入一個新元素e
        public void insert (int index, E e) {

              if (index < 0 || index > size) {
                    throw new IllegalArgumentException("insert error. require index < 0 or index > size");
              }

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

              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 error. index < 0 or index >= size ");
              }
              return data[index];
        }

        // 修改index索引位置的元素為e
        public void  set (int index, E e) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              data[index] = e;
        }

        // 查找數組中是否有元素e
        public boolean contain (E e) {

              for (int i = 0; i < size; i++) {
  //            if (data[i] == e) { // 值比較 用 ==
                    if (data[i].equals(e)) { // 引用比較 用 equals()

                                return true;
                    }
              }
              return false;
        }

        // 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
        public int find (E e) {

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          return i;
                    }
              }
              return -1;
        }

        // 查找數組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數組
        public MyArray findAll (E e) {

              MyArray ma = new MyArray(20);

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          ma.add(i);
                    }
              }

              return  ma;

  //        int[] result = new int[ma.getSize()];
  //        for (int i = 0; i < ma.getSize(); i++) {
  //            result[i] = ma.get(i);
  //        }
  //
  //        return  result;
        }

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

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

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

        // 從數組中刪除所有元素e
        public void removeAllElement (E e) {

              int index = find(e);
              while (index != -1) {
                    remove(index);
                    index = find(e);
              }
  //        while (contain(e)) {
  //            removeElement(e);
  //        }
        }

        // 從數組中刪除index位置的元素, 返回刪除的元素
        public E remove (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }

              E temp = data[index];

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

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

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {

              StringBuilder sb = new StringBuilder();
              String arrInfo = "Array: size = %d，capacity = %d
";
              sb.append(String.format(arrInfo, size, data.length));
              sb.append("[");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(data[i]);
                    sb.append(",");
              }
              if(!isEmpty()) {
                    sb.append(data[size - 1]);
              }
              sb.append("]");

              return sb.toString();
        }
  }

2. Main

  public class Main {

        public static void main(String[] args) {
              // 創建一個自定義的數組對象
              MyArray ma = new MyArray();
              for (int i = 1; i <= 10 ; i++) {
                    ma.add(i);
              }

              /*
              * Array: size = 10，capacity = 10
              * [1,2,3,4,5,6,7,8,9,10]
              */
              System.out.println(ma);

              ma.insert(8, 99999);
              /*
               * Array: size = 10，capacity = 20
               * [1,2,3,4,5,6,7,8,99999,9,10]
               */
              System.out.println(ma);

              ma.remove(8);
              /*
               * Array: size = 10，capacity = 10
               * [1,2,3,4,5,6,7,8,9,10]
               */
              System.out.println(ma);

        }
  }

## 簡單的時間復雜度分析

1. 在算法和數據結構領域有一個非常重要的內容
1. 使用復雜度分析的方式來查看代碼相應的性能好不好，
2. 時間復雜度分析是一個理論化的領域，
3. 如果非要非常嚴謹的去研究它，
4. 那就會涉及到很多數學方面的內容以及很多新概念，
5. 所以只需要對時間復雜度有一個簡單的認識即可。
2. 常見的算法的時間復雜度
1. `O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)`等等
3. 這個大 O 簡單的來說描述的是
1. 算法的運行時間和輸入數據之間的關系。
2. 如最簡單的求和，使用 for 循環來進行求和
3. 他的時間復雜度就是 `O(n)`，
4. 這個 n 表示的是求和 for 循環遍歷的次數，
5. 這個算法運行的時間和 for 循環遍歷的次數成線性關系，
6. 算法和 n 呈線性關系就是`O(n)`。
4. 為什么要用大 O，為什么要叫做`O(n)`？
1. 因為忽略掉了很多的常數，
2. 實際時間用線性方程來表示：`T = c1*n + c2`，
3. 其中的 c1 表示循環遍歷的每一次的時間，
4. 遍歷的次數就為 n，
5. c2 表示遍歷之前和之后的代碼執行時間，
6. 也就是其它地方的代碼執行消耗的時間
7. 如 你要初始化一個變量 sum，
8. 如果你寫的是一個方法，你要返回最終結果 sum

  public static int calcSum (int[] nums) {
     int sum = 0;
     for (int num: nums) {sum += num;}
     return sum;
  }

5. 如果在具體分析算法的時候把 c1 和 c2 也都具體的分析出來，
1. 其實那樣沒有什么必要，并且在有些情況下也不可能做到，
2. 例如不同的語言實現，執行的時間是不等的，
3. 因為轉換為機器碼后的指令數也是不一樣的，
4. 就算指令都一樣，還有不同系統 cpu 執行的操作也是不一樣的，
5. 很難判斷出來 c1 是幾條指令、c2 又是幾條指令，
6. 正因為如此所以在分析時間復雜度的時候，
7. 是一定要忽略掉這些常數的，
8. 忽略掉這些常數之后，
9. 算法一：`T = 2*n + 2`、算法二：`T = 2000*n + 10000`，
10.   他們的時候復雜度都是 `O(n)`，
11.   換句話來說他們都是線性時間的算法，
12.   這些算法消耗的時間和輸入數據的規模是成一個線性關系。
6. 如果有一個算法三：`T = 1*n*n + 0`
1. 不要認為這個 1 很小、0 也很小，
2. 但是它依然是一個`O(n^2)`級別的一個算法，
3. 也就是說這個算法消耗的時間和這個數據的規模成一個平方關系的，
4. `O(n^2)`要比`O(n)`性能差很多，因為前者是 N 的平方級別的，
5. 雖然第二個算法的常數 2000 和 10000 特別的大，
6. 而第三個算法的常數 1 和 0 特別的小，
7. 的確如此，假設這個 n 為 10，
8. 那么第三個算法消耗的時間會比第二個算法消耗的時間要長，
9. 但是那并不能證明第三個算法比第二個算法性能就要差，
10.   因為這個本來就要分具體情況，常數會影響到執行的時間，
11.   但是計算時間復雜度就是要忽略掉常數的，
12.   因為你實際使用沒有辦法控制所有常數。
7. 這個 O 其實表示的一個`漸進的時間復雜度`
1. 這個漸進 描述的是當 n 趨近于無窮大的時候，
2. 例如第二個算法與第三個算法中的 n 為 3000，
3. 那么很明顯第三個算法肯定要比第二個算法執行時間長，
4. 當這個 n 比 3000 還要大的時候，
5. 那么`O(n^2)`要比`O(n)`的執行時間差的越來越大，
6. 所以當 n 越大，一個低階算法的性能就越能體現出來，
7. 也就是 n 越大就越能看出來`O(n^2)`要比`O(n)`快。
8. 在實際使用時可能會用到高階算法
1. 當 n 比較小的時候有可能因為他的常數比較低，
2. 反而可能會快于一個低階算法，
3. 例如 高階的排序算法 歸并排序、快速排序，
4. 這些高階排序法都可以對于比較小的數組轉而使用插入排序這種方式，
5. 可以很好的進行優化，通常這種優化能獲得百分之 10 到百分之 15 性能提升，
6. 它的眼里實際上是插入排序算法的常數要比歸并排序、快速排序算法的常數小一些，
7. 這樣低階的算法執行時間要比高階的算法執行時間要快一些。
9. 大 O 描述的是一個算法或者操作的一個漸進式的時間復雜度，
1. 也就是在說這個算法操作所消耗的時間和輸入數據的規模之間的關系
2. 由于大 O 描述的是 n 趨近于無窮大的情況下這個算法的時間復雜度，
3. 所以當出現這種算法時`T = 2*n*n + 300n + 10`，
4. 他的時間復雜度還是`O(n^2)`，
5. 如果這個算法的時間和 n 成 2 次方關系的話，
6. 相應這個算法的時間和 n 成 1 次方的關系會被忽略掉，
7. 因為在這種情況下 低階項會被忽略掉，
8. 因為當 n 趨近于無窮的時候 低階項起到的作用太小了，
9. 所以當 n 無窮大的時候低階項的大小是可以忽略不計的，
10.   所以`T = 2*n*n + 300n + 10`的時間復雜度還是`O(n^2)`。

### 分析動態數組的時間復雜度

1. 增：O(n)
2. 刪：O(n)
3. 改：已知索引 O(1)，未知索引 O(n)
4. 查找：已知索引 O(1)，未知索引 O(n)
5. 其它
1. 未知索引的刪除，需要先查后刪：O(n^2)
2. 未知索引的刪除全部，需要先遍歷再查再刪：O(n^3)
3. 未置索引的查找全部，需要先遍歷：O(n)
6. 所以在使用數組的時候
1. 索引要具有一定語意，
2. 這樣就可以直接通過索引來進行操作，
3. 如果索引沒有語意，
4. 那么修改和查找會讓性能大幅度降低。
7. 增和刪如果只對最后一個元素進行操作
1. 那么時間復雜度就為`O(1)`，
2. 但是動態數組要有 resize 伸縮容量的功能，
3. 所以增和刪的時間復雜度依然是`O(n)`。
8. 一旦要 resize 了，就需要把整個元素全都復制一遍
1. 復制給一片新的空間，
2. 雖然說 resize 好像是一個性能很差的操作，
3. 但是實際上并不是這樣的，
4. 完全使用最壞情況的時間復雜度來分析 resize 是不合理的，
5. 應該使用均攤時間復雜度分析來分析 resize，
6. 其實 resize 所消耗的性能在整體上沒有那么的糟糕。

#### 添加操作：時間復雜度為 O(n)

1. `addLast(e)`：向數組末尾添加一個元素
1. 非常簡單，只是簡單的給`data[size]`賦值，
2. 所以它的時間復雜度為 `O(1)`
3. `O(1)`的時間復雜度表示這個操作所消耗的時間
4. 與 數據的規模是沒有關系的，
5. 在分析數組的時間復雜度的時候，
6. 那個時間復雜度與這個數組有多少個元素有關系，
7. 由于你要遍歷數組中每一個元素，
8. 那么這個時間復雜度就為`O(n)`（操作 n 個元素），
9. addLast 都能在常數時間內完成，
10.   所以他的時間復雜度就為`O(1)`（操作 1 個元素）。
2. `addFirst(e)`：向數組頭部添加一個元素
1. 需要把數組中的元素都往后移動一個位置，
2. 所以這涉及到遍歷數組中每一個元素，
3. 那么這個時間復雜度就為`O(n)`（操作 n 個元素），
4. 雖然最后也有`O(1)`（操作 1 個元素）的操作 ，
5. 但是在有`O(n)`情況時，
6. 更低階項`O(1)`會被忽略掉。
3. `insert(index, e)`：在 index 索引這個位置插入一個元素
1. 當 index 為 0 的時候就和`addFirst(e)`一樣要向后移動 n 個元素，
2. 當 index 為 size(數組中實際元素個數)的時候就和`addLast(e)`一樣
3. 只是簡單的給`data[size]`賦值，
4. 由于這個 index 可以取 0 到 size 中任何一個值，有那么多種可能性，
5. 那么就可以進行假設在具體操作的時候取到每一個值的概率都是一樣的，
6. 在這種情況下進行操作時它所消耗的時間的期望，
7. 有些情況 index 會小一些，那么向后移動位置的元素會多一些，
8. 有些情況 index 會大一些，那么向后移動位置的元素會少一些，
9. 平均而言這個算法的時間復雜度為`O(n/2)`，
10.   但是這個 2 是一個常數，需要忽略常數，
11.   所以忽略常數后這個算法的時間復雜度為`O(n)`
12.   所以最好的情況下時間復雜就為`O(1)`，
13.   最壞的情況下時間復雜度就為`O(n)`，
14.   中等的情況下時間復雜度就為`O(n/2)`。
4. 添加操作綜合來看是一個`O(n)`級別的算法
1. `addLast(e)`：`O(1)`，
2. `addFirst(e)`：`O(n)`，
3. `insert(index, e)`：`O(n/2)=O(n)`。
4. 嚴格計算就需要一些概率論上的知識，
5. 所以在算法復雜度分析上，
6. 通常關注的是某個算法時間復雜度的最壞情況、最糟糕的情況，
7. 也會有一些特例，但是在現實生活中你不能按照最好的情況去解決問題。
8. 例如 你去上班，公司距離你家的位置最快只需要 5 分鐘，
9. 然后你每次去上班只留五分鐘的時間從家里出來到公司去，
10.   你這樣做就是很高概率的讓每次上班都會遲到。
11.   例如 在考試時，考試最好的情況是考滿分，
12.   然后你每次都考試都以為自己能考滿分的蒙題而不去準備，
13.   你這樣做的就是很高概率的讓每次考試都會不及格。
14.   在大多數情況下去考慮最好的情況是沒有多大意義的，
15.   在算法分析的領域通常會比較嚴格一些去考察最壞的情況。
5. 在添加操作時，自定義的動態數組容量已滿
1. 就會進行 resize 操作，這個 resize 操作顯然是`O(n)`，
2. 以為因為要給新數組重新賦值一遍。

#### 刪除操作：時間復雜度為 O(n)

1. `removeLast()`：在數組末尾刪除一個元素
1. 給末尾的數組元素設置默認值，然后`size--`，
2. 所以它的時間復雜度為 `O(1)`
3. `O(1)`的時間復雜度表示這個操作所消耗的時間
4. 與 數據的規模是沒有關系的，
5. 他每次只是操作一個數組元素。
2. `removeFirst()`：在數組頭部刪除一個元素
1. 需要把數組中的元素都往前移動一個位置，
2. 所以這涉及到遍歷數組中每一個元素，
3. 那么這個時間復雜度就為`O(n)`（操作 n 個元素），
4. 雖然最后也有`O(1)`（操作 1 個元素）的操作 ，
5. 給末尾的數組元素設置默認值，然后`size--`，
6. 但是在有`O(n)`情況時，
7. 更低階項`O(1)`會被忽略掉。
3. `remove(index)`：刪除指定索引位置處的元素并返回
1. 所以最好的情況下時間復雜就為`O(1)`，
2. 最壞的情況下時間復雜度就為`O(n)`，
3. 中等的情況下時間復雜度就為`O(n/2)`，
4. 忽略常數后這個算法的時間復雜度為`O(n)`。
4. 刪除操作綜合來看是一個`O(n)`級別的算法
1. `removeLast()`：`O(1)`，
2. `removeFirst()`：`O(n)`，
3. `remove(index)`：`O(n/2)=O(n)`。
5. 在刪除操作時，自定義的動態數組中實際元素個數為其容量的一半時，
1. 就會進行 resize 操作，這個 resize 操作顯然是`O(n)`，
2. 以為因為要給新數組重新賦值一遍。

#### 修改操作：時間復雜度為 O(1)

1. `set(index, e)`：指定索引修改一個元素的值
1. 簡單的賦值操作，時間復雜度為`O(1)`。
2. 數組最大的優勢就是支持隨機訪問，
3. 訪問到對應索引的值后就可以修改對應索引的值了，
4. 性能超級好。

#### 查詢操作：時間復雜度為 O(n)

1. `get(index)`：指定索引查找一個元素的值
1. 簡單的獲取操作，時間復雜度為`O(1)`。
2. 數組最大的優勢就是支持隨機訪問，
3. 只要知道我要訪問的索引是那個數字，
4. 就能夠一下子訪問到對應索引的值，
5. 性能超級好。
2. `contains(e)`：指定元素來查找，判斷元素是否存在
1. 復雜的獲取操作，時間復雜度為`O(n)`。
2. 需要遍歷整個數組從而找到相同的元素，
3. 這個元素在數組中可能找的到也可能找不到，
4. 所以最好的情況下時間復雜就為`O(1)`，第一個，
5. 最壞的情況下時間復雜度就為`O(n)`，最后一個或者沒找到，
6. 中等的情況下時間復雜度就為`O(n/2)`，在中間，
7. 忽略常數后這個算法的時間復雜度為`O(n)`，
8. 分析算法要關注最壞的情況。
3. `find(e)`：指定元素來查找，返回該元素對應的索引
1. 復雜的獲取操作，時間復雜度為`O(n)`。
2. 需要遍歷整個數組從而找到相同的元素，
3. 這個元素在數組中可能找的到也可能找不到，
4. 所以最好的情況下時間復雜就為`O(1)`，第一個，
5. 最壞的情況下時間復雜度就為`O(n)`，最后一個或者沒找到，
6. 中等的情況下時間復雜度就為`O(n/2)`，在中間，
7. 忽略常數后這個算法的時間復雜度為`O(n)`，
8. 分析算法要關注最壞的情況。

#### 其它擴展操作

1. `removeElement(e)`：根據指定元素來進行刪除第一相同的元素
1. 首先要進行遍歷操作，然后找到指定元素的索引，
2. 最后根據索引來進行刪除操作，刪除操作中又會進行元素位置移動
3. 于是就有兩輪循環了，所以時間復雜度為`O(n^2)`。
2. `removeAll(e)`：：根據指定元素來進行刪除所有相同的元素
1. 首先要進行遍歷操作，找到一個元素后就刪除這個元素，
2. 會復用到`removeElement(e)`，于是有三輪循環了，
3. 所以這個操作是`O(n^3)`。
3. `findAll(e)`：根據指定元素來進行查找，找到所有的元素
1. 首先要進行遍歷操作，找到一個元素后就將元素的索引存起來，
2.