純數據結構Java實現(3/11)(鏈表)

• 2019 年 10 月 3 日
• 筆記

題外話: 篇幅停了一下，特意去看看其他人寫的類似的內容；然後發現類似部落客喜歡畫圖，喜歡講解原理。

(於是我就在想了，理解數據結構的確需要畫圖，但我的文章寫給懂得人看，只配少量圖即可，省事兒)

下面正題開始。

一般性的，都能想到 dummy head 的技巧以及Java中LinkedList(底層是雙向(循環)鏈表)。

Leetcode 返回一個頭結點對象，就算返回整個鏈表了，而我們自己實現一般會 new 一個鏈表對象實例，然後調用該實例的各類方法來操作整個鏈表。

單鏈表

基本認識

之前寫的動態數組並非真正動態，因為其內部封裝的是一個容量不可變的靜態數組。

而這裡的鏈表則是真正的動態數據結構(不需要處理固定容量問題，即增刪效率高，但由於不知道實際地址/索引，所以也喪失了隨機訪能力)。

輔助其他數據結構：二分搜索樹，AVL/紅黑樹，它們基於鏈表實現。

基本構成: 節點 + 指針。

class Node {      E e;      Node next;  }

• 最後一個節點一般指向 null

為了方便或者統一操作，一般會有 Node head，頭結點。

• 頭結點的存在一般是為了在頭部操作 (就像動態數組的新元素索引始終是 size 位置)
• 一般直接用頭結點指向首個節點(第一個節點即 head，但它不存儲元素) dummy head

之所以用 dummy head 的原因，其實是為了操作簡便。(不用也可以，但實現上的寫法就…)

• 打個比方，你要刪除/增加某個節點時，一般情況而言，一定要知道刪除節點的前一個節點(在頭部則沒有必要)；一般都是通過循環遍歷往後先找到特定節點，但是如果沒有 dummy head，那麼就要區分是在頭結點還是中間節點操作(在腦海中想一下就知道了)。

有了 dummy head，頭結點前面也有節點了，所以整個操作行為是統一的，一致的，不需要再做情況區分。

(下面有案例)

實現框架

先把實現的框架列一下，大致如下:

package linkedlist;    public class LinkedList<E> {        //定義一個內部類，作為節點類      private class Node {          public E e;          public Node next; //便於 LinkedList 訪問            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 int size;      private Node head; //頭結點        //構造函數      public LinkedList() {          head = null;          size = 0;      }          public int getSize() {          return size;      }        public boolean isEmpty() {          return size == 0;      }      }

然後再來實現其中的增刪改查，此時先不設置虛擬頭節點。

添加操作

這裡實現的頭部添加 (後續再擴展其他添加):

    public void addFirst(E e) {          /*          Node node = new Node(e);          node.next = head;          head = node;          */            //簡寫          head.next = new Node(e, head);            //維護鏈表長度          size++;      }

在某個位置插入元素:

• 情況1: 鏈表中間的節點，先找到相應位置前一個節點，然後創建新節點，插入

• 情況2: 如果是第一個節點，那麼是不存在前一個節點的。直接用 addFirst 的方式

      //指定的 index 位置添加元素 (先要找到 index 前一個位置)      // index 從 0 ~ size-1      public void add(int index, E e) {          // 索引有問題          if (index < 0 || index > size) { //當 index == size 時，表示在末尾添加              throw new IllegalArgumentException("Add Failed, Illegal index");          }          if (index == 0) {              addFirst(e);          } else {              Node prev = head;              //找到指定位置前一個節點              for (int i = 0; i < index - 1; i++) {                  prev = prev.next;              }              //創建一個新節點              /*Node node = new Node(e);              node.next = prev.next;              prev.next = node;*/                //簡寫              prev = new Node(e, prev.next);              size++;          }      }

(可以看到上面確實是區分不同的情況了的)

此時在末尾添加元素，即 index = size 的位置添加，直接調用 addLast 即可:

    //在末尾添加元素      public void addLast(E e){          add(size, e);      }

頭結點優化

不著急往後探索，這裡先把頭節點優化一下，即加入 dummy head，統一整個操作流程。

上面的操作 add ，由於鏈表頭結點 head 並沒有前面一個節點，所以插入的時候確實要特殊一些。(如果第一個節點之前有節點，那麼整個操作就統一了)

優化方法，在頭結點前面添加一個 虛擬節點，即不存儲任意元素的節點。

內部機制，用戶(client) 不知道虛擬節點的存在。(只是為了方便邏輯操作)。

相關修改:

構造函數需要修改，初始化 LinkedList 的時候就要創建一個節點

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

添加元素可以統一用 add，然後讓 addFirst 和 addLast 調用 add 方法即可。

    //指定的 index 位置添加元素 (先要找到 index 前一個位置)      // index 從 0 ~ size-1      public void add(int index, E e) {          // 索引有問題          if (index < 0 || index > size) { //當 index == size 時，表示在末尾添加              throw new IllegalArgumentException("Add Failed, Illegal index");          }            //因為在實際 index 取值範圍內，總能找到相關節點的前一個節點          Node prev = dummyHead;          //找 index 之前的節點          for(int i = 0; i < index; i++){              prev = prev.next;          }          prev = new Node(e, prev.next);          size++;      }        //頭部插入      public void addFirst(E e) {          add(0, e);      }        //在末尾添加元素      public void addLast(E e){          add(size, e);      }

虛擬頭結點的引入，方便了其他許多鏈表的操作(只要涉及類似的遍歷查找)。

獲取操作

    //獲取某元素      public E get(int index) {          //先檢查索引的合法性          if(index<0 || index > size-1) {              throw new IllegalArgumentException("Get Failed, Illegal index");          }            // 和前面找 index 節點前一個節點不同(那裡是從第一個節點前面的虛擬節點開始)          // 這裡就要找 index 節點，索引從 dummyHead.next 開始，即真正的第一個節點開始          Node ret = dummyHead.next;          for(int i =0; i < index; i++) {              ret = ret.next;          }          return ret.e;      }

獲取第一個元素，最後一個:

    //獲取第一個      public E getFirst() {          return get(0);      }        //獲取最後一個      public E getLast() {          return get(size -1);      }

修改元素

把 index 位置的元素修改為 E。

(找到節點，然後替換裡面的元素 e)

    public void set(int index, E e) {          //先檢查索引的合法性          if (index < 0 || index > size - 1) {              throw new IllegalArgumentException("Get Failed, Illegal index");          }          //找到節點，然後替換裡面的元素          Node curr = dummyHead.next;          for (int i = 0; i < index; i++) {              curr = curr.next;          }          curr.e = e;      }  

查找元素

一直遍歷到元素末尾，然後尋找尾巴。

    //查找元素      public boolean contains(E e) {          Boolean ret = false;          //在 size 範圍內遍歷查找          Node curr = dummyHead.next;          /*for(int i=0; i<size; i++){              if(curr.e.equals(e)){                  ret = true;                  break;              }              curr = curr.next;          }*/            //其實可以用 while 循環 (多判斷一次 size 位置)          while(curr != null) {              //當前節點是有效節點              if(curr.e.equals(e)){                  ret = true;                  break;              }              curr = curr.next;          }          return ret;      }

遍歷列印

多種循環的寫法:

    //列印方法      @Override      public String toString() {          StringBuilder res = new StringBuilder();            //從頭遍歷到尾巴          /*Node curr = dummyHead.next;          while(curr != null) {              res.append(curr + "->");              curr = curr.next;          }*/          //簡寫          for(Node curr = dummyHead.next; curr != null; curr = curr.next) {              res.append(curr + "->");          }          res.append("null");          return res.toString();      }

簡單測試一下:

    //測試元素      public static void main(String[] args) {          LinkedList1<Integer> linkedlist = new LinkedList1<>();          //放入元素 0, 1, 2, 3, 4          for(int i =0; i < 5; i++) {              linkedlist.addFirst(i); //O(1)              System.out.println(linkedlist);          }            System.out.println(linkedlist);            //嘗試插入一個元素          linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null          System.out.println(linkedlist);        }

列印結果:

0->null  1->0->null  2->1->0->null  3->2->1->0->null  4->3->2->1->0->null  4->3->2->1->0->null  4->100->3->2->1->0->null

刪除元素

還是要 先找到前一個節點 。(也就是說還是藉助虛擬頭結點)

簡單一句話，然 delNode 和原來的鏈表脫離。(delNode 置空非必須)

編碼實現:

    //刪除元素      public E remove(int index){          if (index < 0 || index > size - 1) {              throw new IllegalArgumentException("Delete Failed, Illegal index");          }            //找到相關節點的前一個節點          Node curr = dummyHead;          for(int i = 0; i < index; i++) {              curr = curr.next;          }          Node delNode = curr.next;          //刪除          curr.next = delNode.next;          delNode.next = null;            //必須維護 size          size--;            return delNode.e;      }        //刪除第一個節點      public E removeFirst() {          return remove(0);      }        //刪除最後一個節點      public E removeLast() {          return remove(size-1);      }        //刪除指定元素      public void removeElem(E e) {          //從 dummyHead 開始找，找到就刪除，否則就不刪除          Node curr = dummyHead;          boolean found = false;          while (curr.next != null) {              if (curr.next.e.equals(e)) {                  found = true;                  //刪除操作                  Node delNode = curr.next;                  curr.next = delNode.next;                  delNode.next = null;                  size--;                  break;              }              curr = curr.next;          }            if (!found) {              throw new RuntimeException("要刪除的元素不存在");          }      }

測試一下:

    //測試元素      public static void main(String[] args) {          LinkedList1<Integer> linkedlist = new LinkedList1<>();          //放入元素 0, 1, 2, 3, 4          for(int i =0; i < 5; i++) {              linkedlist.addFirst(i); //O(1)              System.out.println(linkedlist);          }            System.out.println(linkedlist);            //嘗試插入一個元素          linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null          System.out.println(linkedlist);              //嘗試刪除 index = 1 位置的 100          linkedlist.remove(1);          System.out.println(linkedlist); //4->3->2->1->0->null            //刪除最後一個元素 0          linkedlist.removeLast();          System.out.println(linkedlist); //4->3->2->1->null            //刪除第一個元素          linkedlist.removeFirst();          System.out.println(linkedlist); //3->2->1->null            //刪除指定元素          linkedlist.removeElem(3);          linkedlist.removeElem(1);          //linkedlist.removeElem(null);          System.out.println(linkedlist);      }

時間複雜度

鏈表雖然不移動元素，但是涉及到從前往後找到(檢查)相應的位置/元素。

添加操作:

• addFirst(), O(1) 因為採用的是頭插法
• addLast(), O(n) 涉及循環遍歷到尾部，然後插入
• add(), O(n) 其實是 O(n/2) 即 O(n)

刪除操作:

同上。

修改操作: O(n)。

查找操作:

get(), contains(), find() 一律 O(n)，因為並不支援隨機訪問呀。

單鏈表應用

鏈棧

上面也說了，如果只在鏈表頭增刪時，它的整體複雜度是 O(1)，這不正好用於棧么？

• 簡單記憶一下，同側操作
• 棧的底層實現是鏈表，而不是動態數組了

package stack;    import linkedlist.LinkedList1;  //這是有 dummy head優化的鏈表實現    public class LinkedListStack<E> implements Stack<E>{        //鏈棧內部實際採用鏈表存儲      private LinkedList1<E> list;          public LinkedListStack(){          list = new LinkedList1<>();      }        @Override      public boolean isEmpty() {          return list.isEmpty();      }        @Override      public int getSize() {          return list.getSize();      }        @Override      public E pop() {          return list.removeFirst();      }        @Override      public E peek() {          return list.getFirst();      }        @Override      public void push(E e) {          list.addFirst(e);      }        @Override      public String toString() {          StringBuilder res = new StringBuilder();          res.append("Stack: top [");          res.append(list);          res.append("]");          return res.toString();      }        public static void main(String[] args) {          LinkedListStack<Integer> stack = new LinkedListStack<>();          //放入元素 0, 1, 2, 3, 4          for(int i =0; i < 5; i++) {              stack.push(i); //O(1)              System.out.println(stack);          }            System.out.println(stack);          System.out.println(stack.peek());            //彈出一個元素          stack.pop();          System.out.println(stack);      }  }

測試結果:

Stack: top [0->null]  Stack: top [1->0->null]  Stack: top [2->1->0->null]  Stack: top [3->2->1->0->null]  Stack: top [4->3->2->1->0->null]  Stack: top [4->3->2->1->0->null]  4  Stack: top [3->2->1->0->null]

和數組實現的棧的不同，數組是在尾巴上插入，可能涉及動態擴容，均攤複雜度是 O(1)，而鏈棧始終就是O(1)。

• 但是 linkedlist 的 new 操作時非常耗時的 (特別是大量對象創建)
• 真實運行結果是不確定的 (ArrayStack VS LinkedListStack)，因為數量級一致

鏈隊列

因為隊列涉及頭和尾的操作，所以如果用鏈表，那一般要添加一個尾指針。

因為 head 和 tail 都是指針，所以入隊和出隊相當於改變指向那麼簡單，但誰做頭誰做尾巴？（相當於 head, tail 指針往哪個方向移動）

如果要刪除 tail 元素並不容易(無法做到O(1))，因為刪除元素要知道 tail 前面一個元素。但是 tail 增加，則可以直接添加。(head不用管， 它的增刪都比較容易)

所以結論顯而易見:

• tail 用作隊尾 (即用於增加元素, tail 指針右移)
• head 用作隊首 (刪除元素，出隊)

此時還需要 dummy head 么，分析上面的 tail， head，顯然不需要操作統一了，所以不需要啞結點。

這裡就不復用 LinkedList 了，而是專門再在內部實現鏈式存儲。(Node 內部類還是需要的)

特別注意:

• 鏈表為空的情況
• 只有一個元素的情況，此時即便是出隊，也要 head = tail = null;

//內部採用鏈式存儲的隊列  public class LinkedQueue<E> implements Queue<E> {        //定義一個內部類，作為節點類      private class Node {          public E e;          public Node next; //便於 LinkedList 訪問            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, tail;      private int size;        //構造器      public LinkedQueue() {          head = tail = null;          size = 0;      }        @Override      public boolean isEmpty() {          return size == 0;      }        @Override      public int getSize() {          return size;      }        @Override      public E dequeue() {          //出隊操作，在隊首          //沒有元素肯定就不能出隊          if (isEmpty()) {              //或者 head = null              throw new IllegalArgumentException("Cannot dequeue from an empty queue");          }          //正常出隊，提取 head          Node retNode = head; //tail，考慮只有一個元素的隊列          head = retNode.next;          retNode.next = null;//遊離對象            //僅在只有一個元素的隊列，需要維護 tail          if (head == null) {              tail = null;          }            size--;          return retNode.e;      }        @Override      public E getFront() {          if (isEmpty()) {              //或者 head = null              throw new IllegalArgumentException("Cannot dequeue from an empty queue");          }          return head.e; // 返回隊首即可      }        @Override      public void enqueue(E e) {          //入隊操作，在尾部操作          if (tail == null) { //說明此時隊列是空的，即 tail 和 head 都為空              tail = new Node(e);              head = tail;          } else {              tail.next = new Node(e);              tail = tail.next;          }          size++;      }        @Override      public String toString() {          StringBuilder res = new StringBuilder();          res.append("Queue: front[ ");          for(Node curr = head; curr != null; curr = curr.next){              res.append(curr.e + "->");          }          res.append("null ] tail");          return res.toString();      }        public static void main(String[] args) {          LinkedQueue<Integer> queue = new LinkedQueue<>();            //存儲  11 個元素看看          for(int i=0; i<11; i++){              queue.enqueue(i);              System.out.println(queue); // 在 10 個元素滿的時候回擴容          }          //出隊試試          System.out.println("------出隊");          queue.dequeue();          System.out.println(queue);      }  }

運行結果如下:

Queue: front[ 0->null ] tail  Queue: front[ 0->1->null ] tail  Queue: front[ 0->1->2->null ] tail  Queue: front[ 0->1->2->3->null ] tail  Queue: front[ 0->1->2->3->4->null ] tail  Queue: front[ 0->1->2->3->4->5->null ] tail  Queue: front[ 0->1->2->3->4->5->6->null ] tail  Queue: front[ 0->1->2->3->4->5->6->7->null ] tail  Queue: front[ 0->1->2->3->4->5->6->7->8->null ] tail  Queue: front[ 0->1->2->3->4->5->6->7->8->9->null ] tail  Queue: front[ 0->1->2->3->4->5->6->7->8->9->10->null ] tail  ------出隊  Queue: front[ 1->2->3->4->5->6->7->8->9->10->null ] tail

到這裡，單鏈表基本探究完畢了。

其他鏈表

下面說的這些鏈表其實也很常用，但是個人要去實現的話，就費事兒啊

(除非你是大學教師，或者學生，或者自由作家，有的是時間耐得住寂寞，磨啊)

雙向鏈表

這個維護代價其實有點大，有點就是節點之間的聯繫更加方便了。(單鏈表時也會維護尾指針)

• 比如尾端刪除，不用從頭開始找尾端前一個元素了，避免了 O(n) 複雜度

沒有對比就沒有傷害，要找我前一個節點是吧，直接給你(不要循環了)。其他操作則沒有太多變化(需要頭結點優化)。由於有額外的變數需要維護，所以並不見得簡單。

class Node {      E e;      Node prev, next;  }

循環鏈表

jdk 中 linkedlist 貌似經過一陣子去環優化，可能，因為不要環效率也不差。

循環鏈表一般都是基於雙向鏈表的。

不用畫圖了，直接認為尾部元素直接指向 dummy head 即可。

此時不需要 tail，因為在 dummyHead 的前面添加一個元素，就相當於在結尾添加元素了。

(引入的環會導致操作有些許變化，比如遍歷)

數組鏈表

• 數組中除了存儲值，還存儲了下一個節點的索引，那麼就相當於數組鏈表了。
• 不依賴數組本身的 index，而依賴於自身存儲的數字索引。

有點兒類似於資料庫存儲設計中的無限級欄位，即某個元素要存儲其父元素位置(parentId)。

畢竟還是基礎數據結構，沒有太複雜；這種 link 的思想用於樹(二叉樹，多叉樹)很平常。

老規矩，程式碼參考的話，我放在了 gayhub, FYI。