什麼是鏈表？

• 2020 年 2 月 15 日
• 筆記

在了解完什麼是數據結構之後，讓我們一起來探索下數據結構中常見的一種—鏈表。

鏈表

鏈表是數據結構之一，其中的數據呈線性排列。在鏈表中，數據的添加和刪除都較為方便，就是訪問比較耗費時間。

如上圖所示就是鏈表的概念圖，Blue、Yellow、Red 這 3 個字元串作為數據被存儲於鏈表中，也就是數據域，每個數據都有 1 個指針，即指針域，它指向下一個數據的記憶體地址，其中 Red 是最後 1 個數據，Red 的指針不指向任何位置，也就是為 NULL，指向 NULL 的指針通常被稱為空指針。

在鏈表中，數據一般都是分散存儲於記憶體中的，無須存儲在連續空間內。

因為數據都是分散存儲的，所以如果想要訪問數據，只能從第 1 個數據開始，順著指針的指向一一往下訪問（這便是順序訪問）。比如，想要找到 Red 這一數據，就得從 Blue 開始訪問，這之後，還要經過 Yellow，我們才能找到 Red。

如果想要添加數據，只需要改變添加位置前後的指針指向就可以，非常簡單。比如，在 Blue 和 Yellow 之間添加 Green。

首先將 Blue 的指針指向的位置變成 Green，然後再把 Green 的指針指向 Yellow，數據的添加就大功告成了。

數據的刪除也一樣，只要改變指針的指向就可以，比如刪除 Yellow。

這時，只需要把 Green 指針指向的位置從 Yellow 變成 Red，刪除就完成了。雖然 Yellow 本身還存儲在記憶體中，但是不管從哪裡都無法訪問這個數據，所以也就沒有特意去刪除它的必要了。今後需要用到 Yellow 所在的存儲空間時，只要用新數據覆蓋掉就可以了。

那麼對鏈表的操作所需的運行時間到底是多少呢？在這裡，我們把鏈表中的數據量記成 n。訪問數據時，我們需要從鏈表頭部開始查找（線性查找），如果目標數據在鏈表最後的話，需要的時間就是 O（n）。

另外，添加數據只需要更改兩個指針的指向，所以耗費的時間與 n 無關。如果已經到達了添加數據的位置，那麼添加操作只需花費 O（1）的時間，刪除數據同樣也只需 O（1）的時間。

鏈表的實現

在對鏈表有了大概的認識以後，我們用 Java 去實現屬於自己的鏈表：

public class ListNode {      int val;      ListNode next;        ListNode(int x) {          val = x;      }  }    class MyLinkedList {      int size;      /**       * 哨兵節點作為偽頭       */      ListNode head;        public MyLinkedList() {          size = 0;          head = new ListNode(0);      }        /**       * 獲取鏈表第 index 個節點的值。如果索引是無效的，返回-1       *       * @param index       * @return       */      public int get(int index) {          // 若索引無效          if (index < 0 || index >= size) {              return -1;          }            ListNode curr = head;          // 從偽頭節點開始，向前走 index+1 步          for (int i = 0; i < index + 1; ++i) {              curr = curr.next;          }          return curr.val;      }        /**       * 在頭部插入節點       *       * @param val       */      public void addAtHead(int val) {          addAtIndex(0, val);      }        /**       * 在尾部插入節點       *       * @param val       */      public void addAtTail(int val) {          addAtIndex(size, val);      }        /**       * 在鏈表中的第 index 個節點前添加值為 val 的一個節點。如果 index 等於鏈表的長度時，節點將被添加到鏈表的末尾。如果 index 大於鏈表長度，節點將無法插入       *       * @param index       * @param val       */      public void addAtIndex(int index, int val) {          // 如果index大於長度，則不會插入該節點。          if (index > size) {              return;          }            // 如果 index 為負，則該節點將插入列表的開頭。          if (index < 0) {              index = 0;          }            ++size;          // 查找要添加的節點的前驅節點          ListNode pred = head;          for (int i = 0; i < index; ++i) {              pred = pred.next;          }            // 要添加的節點          ListNode toAdd = new ListNode(val);          // 通過改變 next 來插入節點          toAdd.next = pred.next;          pred.next = toAdd;      }        /**       * 如果 index 是有效的，刪除鏈表中的第 index 個節點       *       * @param index       */      public void deleteAtIndex(int index) {          // 如果 index 無效，則不執行任何操作          if (index < 0 || index >= size) {              return;          }            size--;          // 找到要刪除節點的前驅節點          ListNode pred = head;          for (int i = 0; i < index; ++i) {              pred = pred.next;          }            // 通過改變 next 來刪除節點          pred.next = pred.next.next;      }  }

到這裡，我相信大家應該對鏈表有了進一步的理解，大家可以用不同的語言去設計實現下。

鏈表擴展

以上講述的鏈表是最基本的一種鏈表，除此之外，還存在幾種擴展方便的鏈表。

雖然上文中提到的鏈表在尾部沒有指針，但我們也可以在鏈表尾部使用指針，並且讓它指向鏈表頭部的數據，將鏈表變成環形，這便是循環鏈表，也叫環形鏈表。循環鏈表沒有頭和尾的概念，想要保存數量固定的最新數據時通常會使用這種鏈表。

另外，以上提到的鏈表裡的每個數據都只有一個指針，但我們可以把指針設定為兩個，並且讓它們分別指向前後數據，這就是雙向鏈表。使用這種鏈表，不僅可以從前往後，還可以從後往前遍曆數據，十分方便。

但是，雙向鏈表存在兩個缺點：一是指針數的增加會導致存儲空間需求增加；二是添加和刪除數據時需要改變更多指針的指向。

總結

看完之後，相信大家都對鏈表和鏈表的基本操作有了一定的了解，還對循環鏈表和雙向鏈表有了初步的認識，大家可以使用自己喜歡的語言去設計實現下單向鏈表，有能力的話可以把循環鏈表和雙向鏈表也實現下。

說完鏈表，當然不能忘記經常和鏈表同時出現在面試官口中的—數組，將在接下來的文章對其進行展開介紹。

參考 《我的第一本演算法書》