前言
除了一些算法之外，我們還要掌握一些常見的資料結構，比如數組、連結清單、棧、隊列、樹等結構。 在之前的文章中，已經帶着大家學習了Java裡的一維數組和多元數組，是以對此我就不再細述了。接下來我會給大家講解一下線性結構中的連結清單，希望你能喜歡哦。
全文大約【3200】 字，不說廢話，隻講可以讓你學到技術、明白原理的純幹貨！本文帶有豐富的案例及配圖視訊，讓你更好地了解和運用文中的技術概念，并可以給你帶來具有足夠啟迪的思考...
一. 連結清單簡介
1. 概念
線性表可以說是一種最基礎最簡單的資料結構，它表示的是一種線性結構，比較常見的線性結構包括數組和連結清單等。
所謂的連結清單，顧名思義，就是鍊式的線性表，即連結清單也是一種線性表。與數組不同的是，連結清單采用的是鍊式存儲，這種鍊式結構是非連續、非順序的記憶體空間。連結清單中的每一個獨立的元素被稱為結點，故連結清單由一系列的結點組成。
其中鍊式存儲的含義如下：
假如我們需要存放一堆物品，但沒有足夠大的空間将所有的物品一次性放下，此時該如何既放下所有的物品，又能簡單的找到所有的物品位置呢？我們可以嘗試采用如下解決方案：存放物品時，每放置一件物品就在該物品上貼一個小紙條，标明下一件物品放在哪裡。這樣，我們隻需要記住第一件物品的位置，從第一件物品上的小紙條，就可以找到第二件物品，再根據第二件物品紙條的内容就找到第三件物品。按照這個方法依次類推，我們便可以找到所有的物品，這就是所謂的鍊式存儲。
2. 表示方式
連結清單中的每個結點都由兩部分組成：資料域、指針域。資料域用來存放目前結點需要存儲的資料内容，指針域用于存放目前結點的下一個結點的位址。如下圖所示：
圖1-連結清單的結構示意圖
上圖所示的節點細節如下：
首個結點中next1存放的是第二結點的記憶體位址，是以用一個箭頭指向第二個結點，就可以表示兩個結點之間的關系。
最後一個結點的後面不再有其他結點，是以最後結點的next5指針域中沒有位址内容，程式設計中可以用null表示。
3. 特點
通過上文所述，就可以給大家總結對外連結表的主要特點：
(1). 從記憶體結構來看，連結清單的記憶體結構是不連續的記憶體空間，是将一組零散的記憶體塊串聯起來，進而進行資料存儲的資料結構；
(2). 連結清單由一系列結點組成，每個結點包括兩個部分，一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。連結清單中資料元素的邏輯順序就是通過位址指針實作的；
(3). 連結清單和數組相比，記憶體空間消耗更大，因為每個存儲資料的結點都需要額外的空間存儲位址指針。
二. 連結清單分類
在工作實踐中，開發者接觸到的連結清單主要有三種：單向連結清單、雙向連結清單、循環連結清單。下面給大家逐一進行介紹一下。
1. 單向連結清單
單向連結清單的每一個結點包含兩部分，一部分是存放資料的變量data，另一部分是指向下一個結點的指針next。 單連結清單隻能單向讀取，其結構如下所示：
圖2-單向連結清單結構示意圖
們以Java為例，給出單向連結清單的結構定義：
2. 雙向連結清單
雙向連結清單，表示連結清單結點由三部分組成：資料域、下一結點指針域、前一結點指針域。
在雙向連結清單結構中，既可以從首個結點出發，根據下一結點指針域依次找到所有結點；同理，也可以從指定的某個結點，根據結點中的前一結點指針位址，向前依次得到前面的結點。具體地，雙向連結清單的結構示意圖如下所示：
圖3-雙向連結清單結構示意圖
如上圖所示：
第1個結點作為整個連結清單的首結點，該結點的prev1指針内容為null，表示沒有前一個結點。
第5個結點作為整個連結清單的最後結點，next5指針内容為null，表示後續沒有下一個結點。
除此之外，中間三個結點，next指針和prev指針分别指向下一個結點和前一個結點，可以實作雙向查找。
使用Java進行雙向連結清單的結點結構定義如下：
3. 循環連結清單
如果，我們将連結清單的最後結點的next指針域做下修改，由原來的指向null修改為指向第1個結點，則整個連結清單就變成了一個環路。以單向連結清單進行操作，如下圖所示：
圖4-單向循環連結清單示意圖
如上圖，每個結點有資料域和指針域兩個部分，這種循環連結清單被稱之為單向循環連結清單。在計算機領域中，單向循環連結清單又稱約瑟夫環（Josephu Loop），這一點僅做了解即可。當然，雙向連結清單也可以調整為循環的連結清單，被稱之為雙向循環連結清單，如下圖所示：
圖5-雙向循環連結清單示意圖
三. 存儲原理
數組在記憶體中的存儲方式是順序存儲（連續存儲），連結清單在記憶體中的存儲方式則是随機存儲，如下圖所示：
圖6-連結清單的記憶體存儲示意圖
連結清單的每一個結點分布在記憶體的不同位置，依靠next指針關聯起來。這樣可以靈活有效地利用零散的碎片空間。連結清單的第一個結點被稱為頭結點，沒有任何結點的next指針指向它，它的前置結點為空null。頭結點用來記錄連結清單的基位址。有了它，就可以周遊得到整條連結清單的資料。連結清單的最後一個結點被稱為尾結點，它的next指向為空null。
四. 連結清單常見操作
本篇文章内容，我們以單向連結清單為例，介紹連結清單的常見操作，主要包括：查找結點、更新結點、插入結點和删除結點等操作。
1. 查找結點
在查找元素時，連結清單隻能從頭結點開始向後，一個結點一個結點逐一查找，如下圖所示：
圖7-單向連結清單查找結點示意圖
時間複雜度分析，分兩種情況：
查找頭結點：頭結點是連結清單的第一個結點，直接就能得到結果，是以查找頭結點時間複雜度是O(1)。
查找非頭結點：如果查找非頭結點，則需要從頭結點向後依次查找，知道整個連結清單的末尾，是以查找非頭結點的其他結點時，時間複雜度是O(n)，最壞情況下時間複雜度也是O(n)。
2. 更新結點
更新結點操作需要兩個步驟：
找到要更新的結點；
将舊資料替換成新資料。
如下圖所示：
圖8-單向連結清單更新結點資料操作示意圖
與查找結點操作時間複雜度情況類似，更新時間複雜度分兩種情況：
更新頭結點：單向連結清單更新頭結點的時間複雜度是O(1)；
更新非頭結點：更新其他結點的最壞情況時間複雜度是O(n)。
3. 插入結點
3.1 尾部插入
尾部插入即把最後一個結點的next指針指向新插入的結點即可，如下圖所示：
圖9-單向連結清單尾部插入結點示意圖
時間複雜度分析：如上圖所示，若尾部插入結點，則需要從頭開始周遊，是以單向連結清單添加尾結點的時間複雜度是O(n)。
3.2 頭部插入
頭部插入新結點需要兩個步驟：
(1). 把新結點的next指針指向原先的頭結點；
(2). 把新結點變為連結清單的頭結點。
如下圖所示：
圖10-單連結清單頭部插入結點示意圖
時間複雜度分析：因為直接将新節點的指針域指向頭結點即可完成操作，是以添加頭結點的時間複雜度是O(1)。
3.3 中間插入
在連結清單的中間位置插入結點同樣需要三步：
(1). 從頭結點開始向後查找，找到要插入的結點的位置；
(2). 新結點的next指針指向插入位置的結點；
(3). 插入位置前置結點的next指針指向新結點；
示意圖如下：
圖11-單向連結清單中間位置插入結點
時間複雜度分析： 若執行插入結點操作，首先需要從頭結點向後查找，找到要插入的位置。很明顯，與連結清單的規模有關，是以中間插入結點操作的時間複雜度是O(n)。
4. 删除結點
4.1 尾部删除
若希望删除連結清單的最後一個結點，隻需要将倒數第二個結點的指針域指向null即可，如下圖所示：
圖12-單向連結清單尾部删除結點示意圖
時間複雜度分析： 因為要從頭開始周遊，是以單向連結清單删除尾結點的時間複雜度是O(n)。
4.2 頭部删除
頭部删除與頭部插入操作類似，隻需要把連結清單的頭結點設為原先頭結點的next指針即可如圖：
圖13-單向連結清單頭部删除結點示意圖
時間複雜度分析： 删除頭結點的時間複雜度也是O(1)。
4.3 中間删除
中間位置删除結點操作類似于中間插入操作，需要三步：
(1). 從頭結點開始向後，找到要删除結點的位置；
(2). 找到删除結點的前一個結點和後一個結點；
(3). 将要删除結點的前置結點的next指針，指向要删除元素的下一個結點；
如下所示：
圖14-單向連結清單中間删除結點示意圖
時間複雜度分析： 因為需要從頭結點開始進行查找，是以時間複雜度與連結清單的規模有關，故單向連結清單删除中間位置結點的時間複雜度是O(n)。
五. 結語
本篇文章，我們一起學習了連結清單的概念，認識了單向連結清單、雙向連結清單、循環連結清單等不同的連結清單類型。并以單向連結清單為例，分析了連結清單中的結點炒作及對應的時間複雜度分析，不知道你現在對連結清單了解了嗎？
深入淺出Spring原理及實戰「緩存Cache開發系列」
從零開始學Java之查找算法有哪些？
排序算法中快排和希爾排序的差別
Lambda表達式怎麼用，一篇講清
更多技術幹貨/IT程式員資訊，關注@千鋒教育