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

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

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

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

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

把數(shù)據(jù)碼成一排進(jìn)行存放

強(qiáng)語言中數(shù)據(jù)的類型是確認(rèn)的，

弱語言中數(shù)據(jù)的類型是不確認(rèn)的，

但是也有方法可以進(jìn)行確認(rèn)。

數(shù)組就是把一個一個的數(shù)據(jù)近挨著排成一排。

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

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

也就是數(shù)組元素的編號，編號從 0 開始的，

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

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

java 中的數(shù)組是有局限性的。

   public class Main {

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

               // 定義數(shù)組
               int[] arr = new int[10];

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

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

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

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

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

         }
   }

數(shù)組的索引可以有語意也可以沒有語意。

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

數(shù)組的最大優(yōu)點(diǎn)

快速查詢，如 scores[2]

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

如果索引沒有語意的話，

那么使用別的數(shù)據(jù)結(jié)構(gòu)那會是一個更好的選擇。

計算機(jī)處理的問題有千千萬萬個

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

但是它有可能不適用于數(shù)組。

比如身份證號可以設(shè)計為一個數(shù)組，

用來存儲相應(yīng)的工資情況，

如果想索引到不同的人，

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

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

因?yàn)檫@個身份證號太大了，

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

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

例如arr[110103198512112312]，

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

是非常不值當(dāng)?shù)模踔潦遣豢赡艿模?/p>

而且大部分空間都是浪費(fèi)的，

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

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

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

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

直接就可以查到相應(yīng)的數(shù)據(jù)。

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

那么就會產(chǎn)生很多新的問題。

因?yàn)檫@個時候數(shù)組只是一個待存

放那些要考察的數(shù)據(jù)的空間，

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

但是你只考察 2 個元素，

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

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

因?yàn)閺挠脩舻慕嵌壬蟻砜词菦]有那么多元素的，

只有兩個元素。

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

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

等等更多問題，

例如添加元素時，

因?yàn)閿?shù)組創(chuàng)建的時候數(shù)組的大小就固定了。

在 java 中數(shù)組沒有這些功能，

所以需要基于 Java 的數(shù)組，

二次封裝屬于我們自己的數(shù)組類。

也就是將原本的靜態(tài)數(shù)據(jù)變成動態(tài)的數(shù)組。

將原本 Java 中的數(shù)組封裝到一個類中，

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

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

對這個數(shù)組進(jìn)行增刪改插等等的功能。

數(shù)據(jù)結(jié)構(gòu)的本質(zhì)也是存儲數(shù)據(jù)，

之后再進(jìn)行高效的對這些數(shù)據(jù)進(jìn)行操作，

只不過你設(shè)計的數(shù)據(jù)結(jié)構(gòu)會把這些數(shù)據(jù)存儲在內(nèi)存中，

所以針對這些數(shù)據(jù)結(jié)構(gòu)的所添加的操作在大的類別的劃分上，

也是增刪改查。

針對不同的數(shù)據(jù)結(jié)構(gòu)，

對應(yīng)的增刪改查的方式是截然不同的，

甚至某些數(shù)據(jù)結(jié)構(gòu)會忽略掉增刪改查中的某一個操作，

但是增刪改查可以作為研究某一個數(shù)據(jù)結(jié)構(gòu)的相應(yīng)的脈絡(luò)，

數(shù)組本身是靜態(tài)的，必須在創(chuàng)建的時候指定他的大小，

可以把這個容量叫做 capacity，

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

數(shù)組空間最多可以裝多少個元素與

數(shù)組中實(shí)際裝多少個元素是沒有關(guān)系的，

因?yàn)檫@是兩回事兒，

數(shù)組中實(shí)際能夠裝多少個元素可以叫做 size，

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

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

這個 size 相當(dāng)于數(shù)組中第一個沒有盛放元素的相應(yīng)索引，

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

代碼示例(class: MyArray)

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

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

         // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

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

         // 獲取數(shù)組的總?cè)萘?         public int getCapacity () {
               return data.length;
         }

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

向數(shù)組添加元素最簡單的形式

就是在數(shù)組的末尾添加一個元素，

size 這個變量其實(shí)就是指向數(shù)組中的末尾，

添加完元素之后其實(shí)也需要維護(hù)這個 size，

因?yàn)閿?shù)組中的元素多了一個，所以要讓它加加。

如果是給元素進(jìn)行插入的操作

那么要先判數(shù)組的容量是否已經(jīng)裝滿了，

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

都沒有問題了，就可以根據(jù)索引來進(jìn)行插入了，

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

全都都往后移動一位，所以循環(huán)是從后往前的，

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

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

最后要記得維護(hù) size。

向數(shù)組中添加元素可以復(fù)用向數(shù)組中插入元素的方法，

因?yàn)椴迦朐氐姆椒ㄒ彩窃诮o數(shù)組添加元素，

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

那么就可以擴(kuò)展兩個方法，

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

一個是插入到數(shù)組最后面

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

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

那么每一次添加操作時可以給數(shù)組中的元素進(jìn)行排序，

排序方式是按照從小到大來進(jìn)行排序。

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

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

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

先要對數(shù)組中的容量進(jìn)行判斷，

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

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

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

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

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

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

         // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

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

         // 獲取數(shù)組的總?cè)萘?         public int getCapacity () {
               return data.length;
         }

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

         // 給數(shù)組添加一個新元素
         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) {

               // 復(fù)用插入元素的方法
               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: 方法名 日期-開發(fā)人員

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

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

大于等于 實(shí)際元素的個數(shù)，都沒有問題時，

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

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

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

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

只能設(shè)置已有存在的元素索引位置的元素，

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

MyArray

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

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

         // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

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

         // 獲取數(shù)組的總?cè)萘?         public int getCapacity () {
               return data.length;
         }

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

         // 給數(shù)組添加一個新元素
         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) {

               // 復(fù)用插入元素的方法
               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: 方法名 日期-開發(fā)人員
         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));
         }
   }

繼續(xù)對自定義的數(shù)組增加新功能

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

包含：

判斷數(shù)組中 是否存在這個元素，

不存在返回 false。

搜索：

根據(jù)這個元素來進(jìn)行 索引的獲取，

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

刪除：

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

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

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

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

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

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

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

這個值要作為返回值來進(jìn)行返回，

然后讓 size 減減，因?yàn)楦采w掉這個元素，

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

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

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

但你也可以手動的將這個元素值設(shè)置為默認(rèn)值。

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

那么就可以擴(kuò)展出兩個方法，

和使用插入方法來進(jìn)行擴(kuò)展的那兩個方法類似，

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

并且返回被刪除的元素，

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

如果數(shù)組為空，那么合法性驗(yàn)證就無法通過。

根據(jù)元素來刪除數(shù)組中的某個元素

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

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

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

最后根據(jù) 獲取到合法索引 來進(jìn)行元素的刪除。

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

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

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

可以對那些方法進(jìn)行擴(kuò)展

如 刪除數(shù)組中所有的指定元素

如 找到數(shù)組中所有的指定元素的索引

關(guān)于自定義的數(shù)組已經(jīng)實(shí)現(xiàn)了很多功能，

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

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

如 這個數(shù)組能存放的數(shù)據(jù)類型不能是任意的數(shù)據(jù)類型，

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

MyArray

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

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

         // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
         public MyArray () {
   //        this( capacity: 10);
               this(10);
         }

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

         // 獲取數(shù)組的總?cè)萘?         public int getCapacity () {
               return data.length;
         }

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

         // 給數(shù)組添加一個新元素
         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) {

               // 復(fù)用插入元素的方法
               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;
         }

         // 查找數(shù)組中是否有元素e
         public boolean contain (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;
         }

         // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組
         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;
         }

         // 從數(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);
               }
   //        if (contain(e)) {
   //            int index = find(e);
   //            remove(index);
   //        }
         }

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

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

         // 從數(shù)組中刪除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: 方法名 日期-開發(fā)人員
         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) {
               // 創(chuàng)建一個自定義的數(shù)組對象
               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);
        }
  }

## 讓自己的數(shù)組可存放任何數(shù)據(jù)類類型

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

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

1. Myarray

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

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

        // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

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

        // 獲取數(shù)組的總?cè)萘?        public int getCapacity () {
              return data.length;
        }

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

        // 給數(shù)組添加一個新元素
        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) {

              // 復(fù)用插入元素的方法
              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;
        }

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

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

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

        // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組
        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;
        }

        // 從數(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);
              }
  //        if (contain(e)) {
  //            int index = find(e);
  //            remove(index);
  //        }
        }

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

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

        // 從數(shù)組中刪除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: 方法名 日期-開發(fā)人員
        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) {
              // 創(chuàng)建一個自定義的數(shù)組對象
              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 方法名 日期-開發(fā)人員
        public String toString(){
              return String.format("Student(name: %s, score: %d)", name, score);
        }

        // 增加入口方法，就可以直接執(zhí)行代碼了
        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);
        }
  }

## 讓自己的數(shù)組成為動態(tài)數(shù)組

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

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

1. Myarray

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

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

        // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

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

        // 獲取數(shù)組的總?cè)萘?        public int getCapacity () {
              return data.length;
        }

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

        // 重新給數(shù)組擴(kuò)容
        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;
        }

        // 給數(shù)組添加一個新元素
        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) {

              // 復(fù)用插入元素的方法
              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;
        }

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

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

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

        // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組
        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;
        }

        // 從數(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);
              }
  //        if (contain(e)) {
  //            int index = find(e);
  //            remove(index);
  //        }
        }

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

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

        // 從數(shù)組中刪除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: 方法名 日期-開發(fā)人員
        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) {
              // 創(chuàng)建一個自定義的數(shù)組對象
              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);

        }
  }

## 簡單的時間復(fù)雜度分析

1. 在算法和數(shù)據(jù)結(jié)構(gòu)領(lǐng)域有一個非常重要的內(nèi)容
1. 使用復(fù)雜度分析的方式來查看代碼相應(yīng)的性能好不好，
2. 時間復(fù)雜度分析是一個理論化的領(lǐng)域，
3. 如果非要非常嚴(yán)謹(jǐn)?shù)娜パ芯克?4. 那就會涉及到很多數(shù)學(xué)方面的內(nèi)容以及很多新概念，
5. 所以只需要對時間復(fù)雜度有一個簡單的認(rèn)識即可。
2. 常見的算法的時間復(fù)雜度
1. `O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)`等等
3. 這個大 O 簡單的來說描述的是
1. 算法的運(yùn)行時間和輸入數(shù)據(jù)之間的關(guān)系。
2. 如最簡單的求和，使用 for 循環(huán)來進(jìn)行求和
3. 他的時間復(fù)雜度就是 `O(n)`，
4. 這個 n 表示的是求和 for 循環(huán)遍歷的次數(shù)，
5. 這個算法運(yùn)行的時間和 for 循環(huán)遍歷的次數(shù)成線性關(guān)系，
6. 算法和 n 呈線性關(guān)系就是`O(n)`。
4. 為什么要用大 O，為什么要叫做`O(n)`？
1. 因?yàn)楹雎缘袅撕芏嗟某?shù)，
2. 實(shí)際時間用線性方程來表示：`T = c1*n + c2`，
3. 其中的 c1 表示循環(huán)遍歷的每一次的時間，
4. 遍歷的次數(shù)就為 n，
5. c2 表示遍歷之前和之后的代碼執(zhí)行時間，
6. 也就是其它地方的代碼執(zhí)行消耗的時間
7. 如 你要初始化一個變量 sum，
8. 如果你寫的是一個方法，你要返回最終結(jié)果 sum

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

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

### 分析動態(tài)數(shù)組的時間復(fù)雜度

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

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

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

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

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

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

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

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

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

#### 其它擴(kuò)展操作

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