摘要：鏈表鏈表是最基礎的動態數據結構鏈表是非常重要的線性數據結構以下三種，底層都是依托靜態數組，靠解決固定容量問題。要清楚什么時候使用數組這樣的靜態數據結構，什么時候使用鏈表這類的動態數據結構。

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

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

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

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

鏈表是最基礎的動態數據結構

鏈表是非常重要的線性數據結構

以下三種，底層都是依托靜態數組，靠 resize 解決固定容量問題。

動態數組：所謂動態，是從用戶的角度上來看的。

棧

隊列

鏈表是真正的動態數據結構

它是數據結構中的一個重點，

也有可能是一個難點，

它是最簡單的一種動態數據結構，

其它更高級的動態數據結構有 二分搜索樹、Trie、

平衡二叉樹、AVL、紅黑樹等等，

熟悉了最簡單的動態數據結構，

那么對于更高級的也會比較容易掌握了。

對于鏈表來說它涉及到了計算機領域一個非常重要的概念

更深入的理解引用（或者指針），

這個概念和內存相關，

在 java 里面不需要手動的管理內存，

但是對鏈表這種數據結構更加深入的理解，

可以讓你對 引用、指針甚至計算機系統中

和內存管理相關很多話題有更加深入的認識。

鏈表本身也是有它非常清晰的遞歸結構的，

只不過由于鏈表這種數據結構它本身是一種線性的數據結構，

所以依然可以非常容易的使用循環的方式來對鏈表進行操作，

但是鏈表本身由于它天生也是具有這種遞歸結構的性質，

所以它也能讓你更加深入的理解遞歸機制相應的這種數據結構，

在學習更加復雜的數據結構的時候，

對遞歸這種邏輯機制深入的理解是必不可缺的。

鏈表這種數據結構本身就具有功能性

它可以用來組成更加復雜的數據結構，

比如 圖結構、hash 表、棧(鏈表版)、隊列(鏈表版)，

所以他可以輔助組成其它數據結構。

數據存儲在“節點”（Node）中

把數據存在一種多帶帶的結構中，

這個結構通常管它叫做節點，

對于鏈表節點來說他通常只有兩部分，

一部分就是存儲真正的數據，

另一部分存儲的是當前節點的下一個節點，

鏈表其實就像一個火車，每一個節點都是一節車廂，

在車廂中存儲數據，而車廂和車廂之間還會進行連接，

以使得這些數據是整合在一起的，

這樣用戶可以方便的在所有的這些數據上進行查詢等等其它的操作，

數據與數據之間連接就是用下面的這個 next 來完成的

   class Node {
      E e;
      Node next;
   }

鏈表的優點

真正的動態，不需要處理固定容量的問題，

它不像靜態數組那樣一下子 new 出來一片空間，

也根本不需要考慮這個空間是不是不夠用，

也根本不用去考慮這個空間是不是開多了。

對于鏈表來說，你需要多少個數據。

你就可以生成多少個節點，

把它們掛接起來了，這就是所謂的動態。

鏈表的缺點

和數組相比，它喪失了隨機訪問的能力。

不能像數組那樣給一個索引

就能直接訪問對應索引位置的元素，

這是因為從底層機制上數組所開辟的空間

在內存里是連續分布的，

所以才能夠直接去向索引對應的偏移

計算出相應的數據所存儲的內存地址，

然后就能夠直接用O(1)的復雜度取出這個元素，

但是鏈表不同，鏈表由于是靠 next 一層一層連接的，

所以在計算機的底層，每一個節點他所在的內存的位置是不同的，

只能夠靠這個 next 來一層一層的找到這個元素，

這就是鏈表最大的缺點。

數組

數組最好永遠索引有語意的情況，如 scores[2]

最大的優點：支持快速查詢

鏈表

鏈表不適合用于索引有語意的情況。

最大的優點：動態存儲。

對比

數組也可以沒有語意，并不是所有的時候索引是有語意的，

也并不是所有有語意的這樣的一個標志就適合做索引，如身份證號，

將一個靜態數組改變為一個動態數組，

就是在應付不方便使用索引的時候有關數據存儲的問題，

對于這樣的存儲數據的需求使用鏈表是更合適的，

因為鏈表最大的優點是動態存儲。

要清楚什么時候使用數組這樣的靜態數據結構，

什么時候使用鏈表這類的動態數據結構。

簡單的代碼示例MyLinkedList

   public class MyLinkedList {

         // 隱藏內部實現，不需要讓用戶知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }
   }

鏈表是通過節點來裝載元素

并且節點和節點之間會進行連接。

如果想訪問這條鏈表中所有的節點，

那么就必須把鏈表的頭給存儲起來，

通常這個鏈表的頭叫做的 head，

應該說在MyLinkedList中

應該有一個變量指向鏈表中的第一個節點。

給自定義數組添加元素是從數組尾部開始添加，

給鏈表添加元素是從數組頭部開始添加，

因為自定義數組有維護一個 size，

這個 size 指向的是下一個待添加元素的位置，

所以你直接將 size 做索引直接賦值即可，

有 size 這個變量在跟蹤數組的尾巴，

而對于鏈表來說 有設置一個鏈表的頭這樣的一個變量，

也就是說有一個變量在跟蹤鏈表的頭，

并沒有一個變量去跟蹤鏈表的尾巴，

所以在鏈表頭部添加元素是非常方便。

添加操作原理

將一個新的元素掛接到鏈表頭部，

同時不破壞現在鏈表的這個結構，

添加一個新元素 666，它的名字叫 node，

就只需要使用 node.next = head，

也就是將新添加的元素的 next 指向鏈表的頭，

這個時候新添加的元素也成為新的鏈表頭，

也就是head = node，

這樣 head 就會指向新的元素 666，也就是 node 這個節點，

如此一來就完成了將 node 這個節點插入了整個鏈表的頭部，

node 這個變量是在一個函數中聲明的，

所以函數結束之后這個變量的作用域也就結束了，

鏈表的 head 也等于 node，

鏈表中就新增了一個新元素。

在鏈表頭部添加元素非常簡單，

只需要創建節點，讓節點的 next 指向 head，

然后讓 head 重新指向這個節點，也就是讓 head 變成新的元素，

因為鏈表是從頭部添加元素的。

在鏈表中間添加元素，

定義一個 prev 的變量指向中間元素的前一個元素，

然后讓新增加的元素這樣，node.next = prev.next，

之后這樣，prev.next = node，

這樣一來就在 prev 這個元素和原本 prev 的下一個元素之間

插入了一個新元素，叫做 node，

整個過程就是將 prev 的 next(下一個元素)的引用

傳遞給新元素的 next(下一個元素)，

然后將 prev 的 next(下一個元素)變更為這個新元素，

最后就將新元素插入到中間了。

這個過程的關鍵是找到待添加的節點的前一個節點，

這個就是 prev 變量要做的事情。

在鏈表的操作中很多時候順序非常重要，

如在鏈表中插入一個元素，在指定的元素后面插入一個元素，

并且不影響整個鏈表結構，和在鏈表中間添加元素一樣，

把原本的node.next = prev.next和prev.next = node

的順序變一下，prev.next = node在前，

node.next = prev.next 在后，這樣一來邏輯就不成立了，

鏈表不僅斷開了，而且新節點的 next 指向的是自己，死循環了，

所以一樣的代碼，順序顛倒了，得到的結果就是錯誤的。

在鏈表的 index(0-based)位置添加元素 e

通過索引來操作鏈表，在鏈表中不是一個常用的操作，

因為在選擇使用鏈表的時候通常就選擇不使用索引了，

但是這個需求在面試等一些考題中出現的概率很大，

所以他的主要作用更多的是一個練習。

如果剛接觸鏈表，對鏈表不熟悉，

然后很多這種操作在腦子里不能非常快的反應出來，

不清楚他的意義是什么，那你可以使用紙筆來稍微畫一下，

每一步程序邏輯的執行意味著當前這個鏈表變成了什么樣子，

這個過程能夠幫助你更加深入的理解程序，

包括在調試的時候來看你的程序到底為什么出了錯誤時，

非常非常有幫助的，不要犯懶，為了更加深入的理解你的程序，

不能只盯著你的代碼去想，一定要寫寫畫畫，

必要的時候甚至根據你的程序進行具體的調試，

這些都是非常重要非常有幫助的。

MyLinkedList

   public class MyLinkedList {

         // 隱藏內部實現，不需要讓用戶知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node head;
         private int size;

         public MyLinkedList () {
               head = null;
               size = 0;
         }

         // ...
         // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

         // 獲取鏈表中元素的個數
         public int getSize () {
               return size;
         }

         // 返回當前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個元素 e
         public void addFirst (E e) {
   //        寫法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫法二
   //        Node node = new Node(e);
   //        node.next = head;
   //        head = node;

   //        寫法三
               head = new Node(e, head);
               size ++;
         }

         // 在鏈表指定索引出插入一個元素
         public void insert (int index, E e) {

               if (index < 0 || index > size) {
                     throw new IllegalArgumentException("add error. index < 0 or index > size");
               }
               if (index == 0) {
                     addFirst(e);
               }else {
                     // 第一個prev就是head
                     Node prev = head;
   //            不斷的搜索 一直通過next來進行檢索
                     for (int i = 0; i < index - 1 ; i++) {
                           prev = prev.next;
                     }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
                     prev.next = new Node(e, prev.next);
                     size ++;

               }
         }

         // 在鏈表尾部添加一個元素
         public void addLast (E e) {

               insert(size, e);
         }
   }

在鏈表中進行指定索引處插入元素時

對鏈表頭插入元素與對鏈表其它位置插入元素的邏輯有區別，

所以就導致每次操作都需要對索引進行判斷，

如果你是在索引 0 的位置插入元素，那么就沒有 prev(前一個元素),

自然就不可以使用node.next = prev.next和prev.next = node了，

那時候你可以直接使用node.next = head和head = node，

不過已經有了向鏈表頭添加元素的方法了，

所以向頭部插入元素時根本就不需要這么做，

這時候可以通過給鏈表設立虛擬頭節點來解決這個問題。

為什么對鏈表頭插入元素那么特殊？

因為插入元素時，必需要找到該索引位置的節點之前的一個節點(prev)，

而鏈表頭(head)之前并沒有任何節點，所以邏輯上就會特殊一些。

不過在鏈表的具體實現中有一個非常常用的技巧，

可以把鏈表頭的這種特殊的操作與其它的操作一起統一起來，

其實這個方法的想法很簡單，既然它沒有鏈表頭之前的節點，

那就自己造一個鏈表頭之前的節點，

這個鏈表頭之前的節點不會用來存儲任何元素，存儲的數據為空，

這個空節點就稱之為整個鏈表頭的 head，也可以叫它 dummyHead，

因為它就是一個假的 head，它也是為鏈表設立的虛擬頭節點，

這樣一來 鏈表的第一個元素就是 dummyHead 的 next 所對應的那個節點，

因為 dummyHead 這個位置的元素是根本不存在的，

對用戶來講也是根本沒有意義的，

這只是為了編寫邏輯方便而出現的一個虛擬的頭節點，

所以一個這樣的內部機制對用戶來說也是不可見的，

用戶不知道鏈表中有沒有虛擬的頭節點，

這和自定義的循環隊列有點像，自定義循環隊列中有一個不可用的空間，

有意識地去浪費一個空間，為了編寫邏輯更加的方便，

從而也讓性能在整體上得到了提升。

有了 dummyHead 之后就不需要處理頭節點這個特殊的操作

因為當你在頭部插入元素時，可以這樣

node.next = dummyHead.next、dummyHead.next = node ，

這樣你就解決了每次插入時都要進行一次邏輯判斷了，

這樣一來就說明了鏈表中所有的節點都有前一個節點了，

在初始的時候 dummyHead 指向的是索引為 0 的元素前一個位置的節點。

鏈表操作的實際原理

在沒有使用虛擬頭節點之前，一直都是在鏈表頭 head 這個地方不停的添加節點，

然后將 head 這個變量不停的指向新添加的節點 node.next = head.next;head = node;。

在使用了虛擬頭節點之后，

一直是在鏈表虛擬頭 dummyHead 這個地方后面一個位置不停的插入新節點，

dummyHead 從未變動過，永遠在鏈表的第一個位置，

node.next = dummyHead.next; dummyHead.next = node;，

但是dummyHead.next才是鏈表中第一個實際記錄的節點，

用戶會不知道虛擬節點的存在，因為 dummyHead 并不算在鏈表的實際節點中，

也就是 size 中不會維護 dummyHead，dummyHead 的存在是為了維護一致的插入操作。

MyLinkedList

   public class MyLinkedList {

         // 隱藏內部實現，不需要讓用戶知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

         // 獲取鏈表中元素的個數
         public int getSize () {
               return size;
         }

         // 返回當前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個元素 e
         public void addFirst (E e) {
   //        寫法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個元素
         public void insert (int index, E e) {

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

               // 第一個prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過next來進行檢索
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個元素
         public void addLast (E e) {

               insert(size, e);
         }
   }

如果要找指定索引元素的前一個節點

那么就要從dummyHead開始遍歷，

如果要找指定索引元素的那個節點，

那么就要從dummyHead.next開始遍歷。

MyLinkedList

   public class MyLinkedList {

         // 隱藏內部實現，不需要讓用戶知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

         // 獲取鏈表中元素的個數
         public int getSize () {
               return size;
         }

         // 返回當前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個元素 e
         public void addFirst (E e) {
   //        寫法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個元素
         public void insert (int index, E e) {

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

               // 第一個prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過next來進行檢索，找指定索引的節點的前一個元素
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個元素
         public void addLast (E e) {

               insert(size, e);
         }

         // get
         public E get (int index) {

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

               Node cur = dummyHead.next;
               for (int i = 0; i < index ; i++) {
                     cur = cur.next;
               }

               return cur.e;
         }

         // getFirst
         public E getFirst () {
               return get(0);
         }

         // getLast
         public E getLast () {
               return get(size - 1);
         }

         // set
         public void set (int index, E e) {

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

               Node node = dummyHead.next;
               for (int i = 0; i < index; i++) {
                     node = node.next;
               }
               node.e = e;
         }

         // contains
         public boolean contains (E e) {

   //        第一種方式
   //        Node node = dummyHead;
   //        for (int i = 0; i < size - 1 ; i++) {
   //            node = node.next;
   //
   //            if (node.e.equals(e)) {
   //                return true;
   //            }
   //        }

   //        第二種方式
               Node node = dummyHead.next;
               while (node != null) {
                     if (node.e.equals(e)) {
                           return true;
                     } else {
                           node = node.next;
                     }
               }
               return  false;
         }

         @Override
         public String toString () {

               StringBuilder sb = new StringBuilder();
               sb.append("鏈表長度：" + size + "，鏈表信息：");
   //        // 寫法一
   //        Node node = dummyHead.next;
   //        while (node != null) {
   //            sb.append(node + "->");
   //            node = node.next;
   //        }
   //        寫法二
               for (Node node = dummyHead.next; node != null ; node = node.next) {
                     sb.append(node + "->");
               }

               sb.append("NULL");
               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
               MyLinkedList mkl = new MyLinkedList();

               for (int i = 1; i <= 5 ; i++) {
                     mkl.addFirst(i);
                     System.out.println(mkl);
               }
               mkl.insert(2, 88888);
               System.out.println(mkl);
         }
   }

鏈表元素的刪除

假設要刪除索引為 2 位置的元素

就是要索引為 2 位置的元素的前一個元素，

還要索引為 2 位置的元素的后一個元素，

讓前一個元素的 next 等于后一個元素，

也就是前一個元素的 next 等于索引為 2 的元素的 next。

也就是讓 prev 指向待刪除的那個節點的前一個節點，

prev 這個節點的 next 就是要刪除的那個節點 delNode，

然后讓prev.next = delNode.next，

這樣就讓待刪除的那個節點的前一個節點的 next，

也就是直接指向了待刪除的那個節點的后一個節點了，

然后讓delNode.next = null 就完成了刪除，

千萬不要這樣delNode = delNode.next，

這個并不是刪除，而是將待刪除節點的引用指向了下一個節點，

通過設置為 null 才是真正的與當前鏈表脫離關系。

MyLinkedList

   public class MyLinkedList {

         // 隱藏內部實現，不需要讓用戶知道
         private class Node {
               public E e;
               public Node next;

               public Node (E e, Node next) {
                     this.e = e;
                     this.next = next;
               }

               public Node (E e) {
                     this(e, null);
               }

               public Node () {
                     this(null, null);
               }

               @Override
               public String toString () {
                     return e.toString();
               }
         }

         private Node dummyHead;
         private int size;

         public MyLinkedList () {
               dummyHead = new Node(null, null);
               size = 0;
         }

         // ...
         // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

         // 獲取鏈表中元素的個數
         public int getSize () {
               return size;
         }

         // 返回當前鏈表是否為空
         public boolean isEmpty () {
               return size == 0;
         }

         // 在鏈表頭部添加一個元素 e
         public void addFirst (E e) {
   //        寫法一
   //        Node node = new Node(e, head);
   //        head = node;

   //        寫法二
   //        Node node = new Node(e);
   //        node.next = dummyHead.next;
   //        dummyHead.next = node;

   //        寫法三
   //        dummyHead.next = new Node(e, dummyHead.next);
   //        size ++;

   //        寫法四
               insert(0, e);
         }

         // 在鏈表指定索引出插入一個元素
         public void insert (int index, E e) {

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

               // 第一個prev就是dummyHead
               Node prev = dummyHead;
   //            不斷的搜索 一直通過next來進行檢索，找指定索引的節點的前一個元素
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
   //            第一種方式
   //            Node node = new Node(e);
   //            node.next = prev.next;
   //            prev.next = node;

   //            第二種方式
               prev.next = new Node(e, prev.next);
               size ++;
         }

         // 在鏈表尾部添加一個元素
         public void addLast (E e) {

               insert(size, e);
         }

         // get
         public E get (int index) {

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

               Node cur = dummyHead.next;
               for (int i = 0; i < index ; i++) {
                     cur = cur.next;
               }

               return cur.e;
         }

         // getFirst
         public E getFirst () {
               return get(0);
         }

         // getLast
         public E getLast () {
               return get(size - 1);
         }

         // set
         public void set (int index, E e) {

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

               Node node = dummyHead.next;
               for (int i = 0; i < index; i++) {
                     node = node.next;
               }
               node.e = e;
         }

         // contains
         public boolean contains (E e) {

   //        第一種方式
   //        Node node = dummyHead;
   //        for (int i = 0; i < size - 1 ; i++) {
   //            node = node.next;
   //
   //            if (node.e.equals(e)) {
   //                return true;
   //            }
   //        }

   //        第二種方式
               Node node = dummyHead.next;
               while (node != null) {
                     if (node.e.equals(e)) {
                           return true;
                     } else {
                           node = node.next;
                     }
               }
               return  false;
         }

         // remove
         public E remove (int index) {

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

               Node prev = dummyHead;
               for (int i = 0; i < index ; i++) {
                     prev = prev.next;
               }
               Node delNode = prev.next;
               prev.next = delNode.next;
               size --;

               E e = delNode.e;
               delNode.next = null;

               return e;
         }

         // removeFirst
         public E removeFirst () {
             return remove(0);
         }

         // removeLast
         public E removeLast () {
               return remove(size - 1);
         }

         @Override
         public String toString () {

               StringBuilder sb = new StringBuilder();
               sb.append("鏈表長度：" + size + "，鏈表信息：");
   //        // 寫法一
   //        Node node = dummyHead.next;
   //        while (node != null) {
   //            sb.append(node + "->");
   //            node = node.next;
   //        }
   //        寫法二
               for (Node node = dummyHead.next; node != null ; node = node.next) {
                     sb.append(node + "->");
               }

               sb.append("NULL");
               return sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {
               MyLinkedList mkl = new MyLinkedList();

               for (int i = 1; i <= 5 ; i++) {
                     mkl.addFirst(i);
                     System.out.println(mkl);
               }
               mkl.insert(2, 88888);
               System.out.println(mkl);

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

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

               mkl.removeLast();
               System.out.println(mkl);
         }
   }

增：O(n)：在只對鏈表頭進行操作時為O(1)

刪：O(n)：在只對鏈表頭進行操作時為O(1)

改：O(n)

查：O(n)：只查鏈表頭的元素時為O(1)

鏈表增刪改查的時間復雜度

整體上要比數組增刪改查的時間復雜度要差，

因為數組有一個優勢，

你有索引的話你就可以快速訪問，

而鏈表沒有這樣的優勢

但是鏈表的優勢是，

如果你只對鏈表頭進行增刪的操作，

那么它的時間復雜度是 O(1)級別的，

而且它整體是動態的，所以不會大量的浪費內存空間。 6.鏈表適合做的事情

不去修改、也不去查任意的元素，

就算查，也只能查鏈表頭的元素，

查的時候，只有那樣才是 O(1)級別的時間復雜度，

并且增加刪除的時候只對鏈表頭進行操作，

只有在這種時候才會和數組整體的時間復雜度是一樣的，

不過鏈表整體是動態的，不會去大量的浪費內存空間，

所以它具有一定的優勢。

鏈表還有諸多的改進的方式

所以應用鏈表在一些情況下仍然是有它的優勢的，

最最重要的是 鏈表本身是一種最最基礎的動態數據結構，

對這種動態數據結構要深刻的理解和掌握，

對于學習更重要的動態數據結構是有巨大的幫助，

比如說二叉樹、平衡二叉樹、AVL、紅黑樹等等。

addLast(e)：O(n)

會從頭遍歷到尾，

找到最后一個節點之后才能添加元素

addFirst(e)：O(1)

直接從頭部添加元素

insert(index, e)：O(n/2) = O(n)

會去遍歷鏈表中每一個節點，

檢索到合適的位置才會添加這個元素。

removeLast()：O(n)

會去遍歷鏈表中每一個節點，

找到最后一個節點后才會刪除

removeFirst()：O(1)

直接從頭部刪除這個節點

remove(index)：O(n/2) = O(n)

會去遍歷鏈表中每一個節點，

檢索到合適的位置才會移除這個元素

set(index, e)：O(n)

會去遍歷鏈表中每一個節點，

找到了合適位置的節點后，

才會修改元素

get(index)：O(n)

會去遍歷鏈表中每一個節點，

找到了合適位置的節點后，

返回這個元素。

contains(e)：O(n)

會去遍歷鏈表中每一個節點，

返回 是否有相同元素的 bool 值。

find(e)：O(n)

這個方法對鏈表來說是沒有用的，

就算你拿到了那個索引你也不能快速訪問。

對鏈表進行添加操作時

時間復雜度為O(n)，

但是在只對鏈表頭進行操作時為O(1)

對鏈表進行刪除操作時

時間復雜度為O(n)，

但是在只對鏈表頭進行操作時為O(1)

對鏈表進行查詢操作時

時間復雜度為O(n)，

但是在只查鏈表頭的元素時為O(1)

這些特性很符合棧的需求

棧是后進先出的，并且棧只查棧頂的元素，

所以可以使用鏈表來實現棧這樣的數據結構。

首先定義接口IMyLinkedListStack，

然后讓MyLinkedListStack來實現這些接口。

IMyLinkedListStack

void push(E e)：添加一個元素

E pop()：移除一個元素

E peek()：查看棧頂的元素

int getSize()：獲取棧中實際的元素個數

boolean isEmpty()：判斷棧是否為空

(Interface: IMyLinkedListStack, class: MyLinkedList,

class: MyLinkedListStack, class: Main)

IMyLinkedListStack

   public interface IMyLinkedListStack {
         /**
          * @param e

         */
        void push (E e);

        /**
         * @return e
         * 出棧
         */
        E pop ();

        /**
         * @return e
         * 查看棧頂的一個元素
         */
        E peek ();

        /**
         * @return size
         * 查看棧中實際元素的個數
         */
        int getSize ();

        /**
         * @return not empty
         * 判斷棧中是否為空
         */
        boolean isEmpty ();
  }

3. `MyLinkedList`

  public class MyLinkedList {

        // 隱藏內部實現，不需要讓用戶知道
        private class Node {
              public E e;
              public Node next;

              public Node (E e, Node next) {
                    this.e = e;
                    this.next = next;
              }

              public Node (E e) {
                    this(e, null);
              }

              public Node () {
                    this(null, null);
              }

              @Override
              public String toString () {
                    return e.toString();
              }
        }

        private Node dummyHead;
        private int size;

        public MyLinkedList () {
              dummyHead = new Node(null, null);
              size = 0;
        }

        // ...
        // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

        // 獲取鏈表中元素的個數
        public int getSize () {
              return size;
        }

        // 返回當前鏈表是否為空
        public boolean isEmpty () {
              return size == 0;
        }

        // 在鏈表頭部添加一個元素 e
        public void addFirst (E e) {
  //        寫法一
  //        Node node = new Node(e, head);
  //        head = node;

  //        寫法二
  //        Node node = new Node(e);
  //        node.next = dummyHead.next;
  //        dummyHead.next = node;

  //        寫法三
  //        dummyHead.next = new Node(e, dummyHead.next);
  //        size ++;

  //        寫法四
              insert(0, e);
        }

        // 在鏈表指定索引出插入一個元素
        public void insert (int index, E e) {

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

              // 第一個prev就是dummyHead
              Node prev = dummyHead;
  //            不斷的搜索 一直通過next來進行檢索，找指定索引的節點的前一個元素
              for (int i = 0; i < index ; i++) {
                    prev = prev.next;
              }
  //            第一種方式
  //            Node node = new Node(e);
  //            node.next = prev.next;
  //            prev.next = node;

  //            第二種方式
              prev.next = new Node(e, prev.next);
              size ++;
        }

        // 在鏈表尾部添加一個元素
        public void addLast (E e) {

              insert(size, e);
        }

        // get
        public E get (int index) {

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

              Node cur = dummyHead.next;
              for (int i = 0; i < index ; i++) {
                    cur = cur.next;
              }

              return cur.e;
        }

        // getFirst
        public E getFirst () {
              return get(0);
        }

        // getLast
        public E getLast () {
              return get(size - 1);
        }

        // set
        public void set (int index, E e) {

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

              Node node = dummyHead.next;
              for (int i = 0; i < index; i++) {
                    node = node.next;
              }
              node.e = e;
        }

        // contains
        public boolean contains (E e) {

  //        第一種方式
  //        Node node = dummyHead;
  //        for (int i = 0; i < size - 1 ; i++) {
  //            node = node.next;
  //
  //            if (node.e.equals(e)) {
  //                return true;
  //            }
  //        }

  //        第二種方式
              Node node = dummyHead.next;
              while (node != null) {
                    if (node.e.equals(e)) {
                          return true;
                    } else {
                          node = node.next;
                    }
              }
              return  false;
        }

        // remove
        public E remove (int index) {

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

              Node prev = dummyHead;
              for (int i = 0; i < index ; i++) {
                    prev = prev.next;
              }
              Node delNode = prev.next;
              prev.next = delNode.next;
              size --;

              E e = delNode.e;
              delNode.next = null;

              return e;
        }

        // removeFirst
        public E removefirst () {
            return remove(0);
        }

        // removeLast
        public E removeLast () {
              return remove(size - 1);
        }

        @Override
        public String toString () {

              StringBuilder sb = new StringBuilder();
              sb.append("鏈表長度：" + size + "，鏈表信息：");
  //        // 寫法一
  //        Node node = dummyHead.next;
  //        while (node != null) {
  //            sb.append(node + "->");
  //            node = node.next;
  //        }
  //        寫法二
              for (Node node = dummyHead.next; node != null ; node = node.next) {
                    sb.append(node + "->");
              }

              sb.append("NULL");
              return sb.toString();
        }
  }

4. `MyLinkedListStack`

  public class MyLinkedListStack implements IMyLinkedListStack {
        private MyLinkedList mkl;

        public MyLinkedListStack () {
              mkl = new MyLinkedList();
        }

        /**
         * @param e 入棧
         */
        @Override
        public void push (E e) {
              mkl.addFirst(e);
        }

        /**
         * @return e
         * 出棧
         */
        @Override
        public E pop () {
              return mkl.removefirst();
        }

        /**
         * @return e
         * 查看棧頂的一個元素
         */
        @Override
        public E peek () {
              return mkl.getFirst();
        }

        /**
         * @return size
         * 查看棧中實際元素的個數
         */
        @Override
        public int getSize () {
              return mkl.getSize();
        }

        /**
         * @return not empty
         * 判斷棧中是否為空
         */
        @Override
        public boolean isEmpty () {
              return mkl.isEmpty();
        }

        @Override
        public String toString () {
              int size = getSize();

              StringBuilder sb = new StringBuilder();
              sb.append("MyLinkedlistStack: 元素個數=" + size);
              sb.append(", stack top=[ ");
              for (int i = 0; i < size ; i++) {
                    sb.append(mkl.get(i));
                    sb.append("->");
              }
              sb.append("NULL ]");

              return sb.toString();
        }
  }

5. `Main`

public class Main {

     public static void main(String[] args) {
           MyLinkedListStack mkls = new MyLinkedListStack();

           for (int i = 1; i <= 5 ; i++) {
                 mkls.push(i);
                 System.out.println(mkls);
           }

           System.out.println(mkls.peek());

           for (int i = 0; i < 5 ; i++) {
                 System.out.println(mkls);
                 mkls.pop();
           }
     }

}

## 自定義數組棧對比自定義鏈表棧

1. 自定義數組棧與自定義鏈表棧的性能相差很少
   1. 但是隨著操作的次數增長，數組棧會慢慢強過鏈表棧，
   2. 自定義鏈表棧中有太多的 new 操作，
   3. new 操作在有一些系統上比較耗費性能的，
   4. 因為它在不停的在內存中尋找可以開辟空間的地方來進行開辟空間，
   5. 自定義數組棧中有比較多的擴容操作，
   6. 所以這個比較是相對比較復雜的，
   7. 和你的語法、操作系統、編譯器、解釋器都有關系，
   8. 不過他們的時間復雜度都是`O(1)`級別的，
   9. 所以他們之間的性能差異無非就 1-2 倍這樣，
   10.   在最極端的情況下 3-5 倍就已經很難了，
   11.   不會有幾百倍的巨大的差異，因為畢竟他們的時間復雜度一樣。

### 代碼示例

1. `(Interface: IStack, class: MyLinkedList,`
   1. `class: MyLinkedListStack, class: MyArray,`
   2. `class: MyStack, class: Main)`
2. `IStack`

  public interface IStack {
        /**
         * @param e
         * 入棧
         */
        void push (E e);

        /**
         * @return e
         * 出棧
         */
        E pop ();

        /**
         * @return e
         * 查看棧頂的一個元素
         */
        E peek ();

        /**
         * @return size
         * 查看棧中實際元素的個數
         */
        int getSize ();

        /**
         * @return not empty
         * 判斷棧中是否為空
         */
        boolean isEmpty ();
  }

3. `MyLinkedList`

  public class MyLinkedList {

        // 隱藏內部實現，不需要讓用戶知道
        private class Node {
              public E e;
              public Node next;

              public Node (E e, Node next) {
                    this.e = e;
                    this.next = next;
              }

              public Node (E e) {
                    this(e, null);
              }

              public Node () {
                    this(null, null);
              }

              @Override
              public String toString () {
                    return e.toString();
              }
        }

        private Node dummyHead;
        private int size;

        public MyLinkedList () {
              dummyHead = new Node(null, null);
              size = 0;
        }

        // ...
        // 其它的構造函數，例如傳進來一個數組，將數組轉換為鏈表

        // 獲取鏈表中元素的個數
        public int getSize () {
              return size;
        }

        // 返回當前鏈表是否為空
        public boolean isEmpty () {
              return size == 0;
        }

        // 在鏈表頭部添加一個元素 e
        public void addFirst (E e) {
  //        寫法一
  //        Node node = new Node(e, head);
  //        head = node;

  //        寫法二
  //        Node node = new Node(e);
  //        node.next = dummyHead.next;
  //        dummyHead.next = node;

  //        寫法三
  //        dummyHead.next = new Node(e, dummyHead.next);
  //        size ++;

  //        寫法四
              insert(0, e);
        }

        // 在鏈表指定索引出插入一個元素
        public void insert (int index, E e) {

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

              // 第一個prev就是dummyHead
              Node prev = dummyHead;
  //            不斷的搜索 一直通過next來進行檢索，找指定索引的節點的前一個元素
              for (int i = 0; i < index ; i++) {
                    prev = prev.next;
              }
  //            第一種方式
  //            Node node = new Node(e);
  //            node.next = prev.next;
  //            prev.next = node;

  //            第二種方式
              prev.next = new Node(e, prev.next);
              size ++;
        }

        // 在鏈表尾部添加一個元素
        public void addLast (E e) {

              insert(size, e);
        }

        // get
        public E get (int index) {

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

              Node cur = dummyHead.next;
              for (int i = 0; i < index ; i++) {
                    cur = cur.next;
              }

              return cur.e;
        }

        // getFirst
        public E getFirst () {
              return get(0);
        }

        // getLast
        public E getLast () {
              return get(size - 1);
        }

        // set
        public void set (int index, E e) {

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

              Node node = dummyHead.next;
              for (int i = 0; i < index; i++) {
                    node = node.next;
              }
              node.e = e;
        }

        // contains
        public boolean contains (E e) {

  //        第一種方式
  //        Node node = dummyHead;
  //        for (int i = 0; i < size - 1 ; i++) {
  //            node = node.next;
  //
  //            if (node.e.equals(e)) {
  //                return true;
  //            }
  //        }

  //        第二種方式
              Node node = dummyHead.next;
              while (node != null) {
                    if (node.e.equals(e)) {
                          return true;
                    } else {
                          node = node.next;
                    }
              }
              return  false;
        }

        // remove
        public E remove (int index) {

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

              Node prev = dummyHead;
              for (int i = 0; i < index ; i++) {
                    prev = prev.next;
              }
              Node delNode = prev.next;
              prev.next = delNode.next;
              size --;

              E e = delNode.e;
              delNode.next = null;

              return e;
        }

        // removeFirst
        public E removefirst () {
            return remove(0);
        }

        // removeLast
        public E removeLast () {
              return remove(size - 1);
        }

        @Override
        public String toString () {

              StringBuilder sb = new StringBuilder();
              sb.append("鏈表長度：" + size + "，鏈表信息：");
  //        // 寫法一
  //        Node node = dummyHead.next;
  //        while (node != null) {
  //            sb.append(node + "->");
  //            node = node.next;
  //        }
  //        寫法二
              for (Node node = dummyHead.next; node != null ; node = node.next) {
                    sb.append(node + "->");
              }

              sb.append("NULL");
              return sb.toString();
        }
  }

4. `MyLinkedListStack`

  public class MyLinkedListStack implements IStack {
        private MyLinkedList mkl;

        public MyLinkedListStack () {
              mkl = new MyLinkedList();
        }

        /**
         * @param e 入棧
         */
        @Override
        public void push (E e) {
              mkl.addFirst(e);
        }

        /**
         * @return e
         * 出棧
         */
        @Override
        public E pop () {
              return mkl.removefirst();
        }

        /**
         * @return e
         * 查看棧頂的一個元素
         */
        @Override
        public E peek () {
              return mkl.getFirst();
        }

        /**
         * @return size
         * 查看棧中實際元素的個數
         */
        @Override
        public int getSize () {
              return mkl.getSize();
        }

        /**
         * @return not empty
         * 判斷棧中是否為空
         */
        @Override
        public boolean isEmpty () {
              return mkl.isEmpty();
        }

        @Override
        public String toString () {
              int size = getSize();

              StringBuilder sb = new StringBuilder();
              sb.append("MyLinkedlistStack: 元素個數=" + size);
              sb.append(", stack top=[ ");
              for (int i = 0; i < size ; i++) {
                    sb.append(mkl.get(i));
                    sb.append("->");
              }
              sb.append("NULL ]");

              return sb.toString();
        }
  }

5. `MyArray`

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

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

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

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

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

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

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

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

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

              data = newData;
        }

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

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

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

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

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

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

              insert(0, e);
        }

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

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

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

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

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

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

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

        // 獲取數組中第一個元素（純查看）
        public E getFirst () {
              return get(0);
        }

        // 獲取數組中最后一個元素（純查看）
        public E getLast () {
              return get(size - 1);
        }

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

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

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

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

                                return true;
                    }
              }
              return false;
        }

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

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

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

              MyArray ma = new MyArray(20);

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

              return  ma;

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

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

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

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

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

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

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

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

              E temp = data[index];

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

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

              // 防止復雜度震蕩 防止容量為4，size為1時，data.length / 2 為 0
              if(size == data.length / 4 && data.length / 2 != 0) {
                    resize(data.length / 2);
              }

              return temp;
        }

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

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

              return sb.toString();
        }
  }

6. `MyStack`

  public class MyStack implements IStack {
        // 借用自定義個動態數組
        private MyArray ma;

        public MyStack () {
            ma = new MyArray();
        }

        public MyStack (int capacity) {
              ma = new MyArray(capacity);
        }

        /**
         * @param e
         * @return 入棧
         */
        @Override
        public void push(E e) {
              ma.addLast(e);
        }

        /**
         * @return 出棧
         */
        @Override
        public E pop() {
              return ma.removeLast();
        }

        /**
         * @return 查看棧頂的元素
         */
        @Override
        public E peek() {
              return ma.getLast();
        }

        /**
         * @return 獲取棧中實際元素的個數
         */
        @Override
        public int getSize() {
              return ma.getSize();
        }

        /**
         * @return 判斷棧是否為空
         */
        @Override
        public boolean isEmpty() {
              return ma.isEmpty();
        }

        // 返回棧的容量
        public int getCapacity () {
              return ma.getCapacity();
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {
              int size = ma.getSize();
  //        int capacity = ma.getCapacity();

              StringBuilder sb = new StringBuilder();
  //        String arrInfo = "Stack: size = %d，capacity = %d
";
  //        sb.append(String.format(arrInfo, size, capacity));
              sb.append("Stack: [");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(ma.get(i));
                    sb.append(",");
              }
              if (!ma.i