摘要：數(shù)組中有一個(gè)很重要的概念叫做索引，也就是數(shù)組元素的編號，編號從開始的，所以最后一個(gè)元素的索引為數(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(哈希表)

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

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

本文章適合 對數(shù)據(jù)結(jié)構(gòu)想了解并且感興趣的人群，文章風(fēng)格一如既往如此，就覺得手機(jī)上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時(shí)間跨度也算將近半年時(shí)間了，希望對想學(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ù)組就是把一個(gè)一個(gè)的數(shù)據(jù)近挨著排成一排。

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

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

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

所以最后一個(gè)元素的索引為數(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ù)組中某個(gè)元素
               scores[0] = 60;

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

         }
   }

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

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

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

快速查詢，如 scores[2]

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

如果索引沒有語意的話，

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

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

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

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

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

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

如果想索引到不同的人，

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

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

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

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

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

例如arr[110103198512112312]，

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

是非常不值當(dāng)?shù)?，甚至是不可能的?/p>

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

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

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

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

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

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

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

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

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

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

例如你開辟了 8 個(gè)元素的空間，

但是你只考察 2 個(gè)元素，

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

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

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

只有兩個(gè)元素。

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

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

等等更多問題，

例如添加元素時(shí)，

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

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

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

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

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

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

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

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

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

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

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

只不過你設(shè)計(jì)的數(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)會忽略掉增刪改查中的某一個(gè)操作，

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

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

可以把這個(gè)容量叫做 capacity，

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

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

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

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

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

通過它來控制，在初始化的時(shí)候，

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

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

增加數(shù)組元素和刪除數(shù)組元素的時(shí)候就要維護(hù)這個(gè) 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í)際個(gè)數(shù)
         public int getSize () {
               return size;
         }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

但舊元素并沒消失，而是位置往后移動(dòng)了一位，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果超過了就不添加，并且報(bào)錯(cuò)，

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

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

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

   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í)際個(gè)數(shù)
         public int getSize () {
               return size;
         }

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

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

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

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

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

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

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

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

         // 在index索引的位置插入一個(gè)新元素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í)際元素的個(gè)數(shù)，都沒有問題時(shí)，

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

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

修改自動(dòng)數(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í)際個(gè)數(shù)
         public int getSize () {
               return size;
         }

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

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

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

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

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

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

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

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

               insert(0, e);
         }

         // 在index索引的位置插入一個(gè)新元素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ù)組增加新功能

包含、搜索、刪除這三個(gè)功能。

包含：

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

不存在返回 false。

搜索：

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

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

刪除：

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

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

只不過是一個(gè)反向的過程，

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

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

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

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

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

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

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

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

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

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

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

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

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

分別是 刪除第一個(gè)元素和刪除最后一個(gè)元素，

并且返回被刪除的元素，

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

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

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

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

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

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

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

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

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

如果索引不合法那就不刪除然后也可以報(bào)一個(gè)異常。

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

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

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

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

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

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

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

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

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í)際個(gè)數(shù)
         public int getSize () {
               return size;
         }

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

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

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

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

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

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

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

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

               insert(0, e);
         }

         // 在index索引的位置插入一個(gè)新元素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ù)組中刪除第一個(gè)元素, 返回刪除的元素
         public int removeFirst () {
               return remove(0);
         }

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

         // 從數(shù)組中刪除第一個(gè)元素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)建一個(gè)自定義的數(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. 每個(gè)基本數(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. 這個(gè)自動(dòng)的轉(zhuǎn)換過程就叫作自動(dòng)的加包或者解包，
2. 也就是基本類型在需要的時(shí)候會自動(dòng)轉(zhuǎn)換為他所對應(yīng)的包裝類，
3. 而這些包裝類也會在他們需要的時(shí)候自動(dòng)的轉(zhuǎn)換為
4. 他們所對的基本類型，這樣一來就可以將一個(gè)數(shù)組變成
5. 一個(gè)可以放置任何數(shù)據(jù)類型的泛型數(shù)組。
6. 通過在自定義的數(shù)組類型后面加上``
1. E 表示一個(gè)任意的類型，
2. 而`<>`表示這個(gè)類型擁有了泛型的能力，
3. 在你具體使用的時(shí)候可以將`<>`中的 E
4. 改成你想要存放的數(shù)據(jù)的類型。
7. 泛型這個(gè)能力并不是 Java 一開始就有的，
1. 是從 Java1.5 才開始支持的，
2. 在如果在定義的類中使用這個(gè)任意類型 E，
3. 需要繞一個(gè)彎子，將使用到 E 的地方改成 Object，
4. Object 類是任意類的父類，
5. 然后再對這個(gè)類的對象進(jìn)行強(qiáng)制類型的轉(zhuǎn)換，
6. 如`(E[])new Object[capacity]`，
7. 這樣的語法是合法的，這樣就相當(dāng)于在這個(gè)類中
8. new 出來一個(gè)還沒有指定類型的 E 類型的數(shù)組，
9. 當(dāng)你在使用這個(gè)類的時(shí)候，那么 E 可以變成任意的類型。
8. 比較泛型 E 類型的對象時(shí)不能再用`==`
1. 值比較 用 `==`，
2. 引用比較 用 `equals()`
9. 在刪除操作時(shí)
1. java 中有一個(gè)垃圾回收機(jī)制，
2. 但是如果引用一直存在的話，
3. 就不會回收，所以可以在刪除操作時(shí)，
4. 給這個(gè)數(shù)組 size 位置的元素賦值為 null，
5. 這樣相當(dāng)于就給元素設(shè)置默認(rèn)值 null 了。
10.   loitering objects != memory leak
11.   閑置的對象并不等于內(nèi)存泄漏，
12.   只不過是這個(gè)對象沒有用了，
13.   還是在這個(gè)程序中游蕩，
14.   也沒有辦法被垃圾回收機(jī)制回收掉，
15.   但是為了程序優(yōu)化，
16.   可以手動(dòng)的把這個(gè)閑置的對象去除掉那就更好。
17.   泛型可以存放所有的數(shù)據(jù)類型
18.   非常的方便，原理還是編譯時(shí)的代碼檢查，
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í)際個(gè)數(shù)
        public int getSize () {
              return size;
        }

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

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

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

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

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

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

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

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

              insert(0, e);
        }

        // 在index索引的位置插入一個(gè)新元素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ù)組中刪除第一個(gè)元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

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

        // 從數(shù)組中刪除第一個(gè)元素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)建一個(gè)自定義的數(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ù)組成為動(dòng)態(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ù)組變成一個(gè)動(dòng)態(tài)的數(shù)組，
2. 當(dāng)自定義數(shù)組中的空間已經(jīng)滿了，
3. 那就創(chuàng)建一個(gè)新的數(shù)組，
4. 這個(gè)數(shù)組的容量定義為原來的容量的兩倍，
5. 然后將舊數(shù)組中的元素全部放到新數(shù)組中，
6. 以循環(huán)的方式放入新數(shù)組中。
3. 讓新數(shù)組替代掉舊數(shù)組，
1. 當(dāng)`size == capcity`時(shí)創(chuàng)建新數(shù)組，容量翻倍，
2. 當(dāng)`size == capcity / 2`時(shí)創(chuàng)建新數(shù)組，容量縮小一倍，
3. 最終都會讓新數(shù)組替代掉舊數(shù)組。
4. 使用這種方式會讓整體性能上很有優(yōu)勢。
5. 在 Java 的動(dòng)態(tài)數(shù)組中選擇是擴(kuò)容倍數(shù)是 1.5，
6. 然后無論是 1.5 還是 2 或者 3 都是可以的，
7. 只不過是一個(gè)參數(shù)的選擇，
8. 你可以根據(jù)使用場景來進(jìn)行擴(kuò)容。
4. 自定義數(shù)組的這些操作及性能需要分析。
1. 也就是要進(jìn)行一個(gè)時(shí)間復(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í)際個(gè)數(shù)
        public int getSize () {
              return size;
        }

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

        // 返回?cái)?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ù)組添加一個(gè)新元素
        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++;
        }

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

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

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

              insert(0, e);
        }

        // 在index索引的位置插入一個(gè)新元素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ù)組中刪除第一個(gè)元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

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

        // 從數(shù)組中刪除第一個(gè)元素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)建一個(gè)自定義的數(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);

        }
  }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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