前段時間我們聊了最基礎的數據結構：數組，今天我們再來聊一個非常基礎的數據結構：鍊表。
鍊表與數組的區別在於，鍊表可以不需要一塊連續的內存空間，它可以通過指針將一組零散的內存塊串聯起來使用。這樣的好處在於，當內存空間連續空間不足時，也能正常使用鍊表。我們用數組和鍊表在內存中的對比圖來方便理解（假設每個節點占4個字節），如下：
其中鍊表中的每一個內存塊我們叫做節點(node)，第一個節點我們稱為頭節點，最後一個節點我們稱為尾節點。節點與節點之間使用指針連結，根據指針連結方式的不同，鍊表可分為單鍊表、雙向鍊表、循環鍊表。下面我們將挨個介紹。
單鍊表
單鍊表中節點存儲的數據分為兩部分，一部分為業務數據，另一部分為下一個節點的地址如下圖所示：
其中存儲下一個節點地址的部分我們稱為後繼指針,而尾節點的後繼指針指向的是一個空地址。
雙向鍊表
雙向鍊表與單鍊表的區別在於，雙向鍊表節點存儲的數據分為三部分，一部分為業務數據，一部分為上一個節點的地址，一部分為下一個節點的地址。如下圖所示：
其中存儲上一個節點地址的部分我們稱為前驅指針。
循環鍊表
循環鍊表其實是特殊的鍊表，即尾節點指向頭節點，讓整個鍊表變成一個環狀，以雙向循環鍊表為例，如下：
三種常見的鍊表介紹完了，我們再來看下鍊表的查詢、插入、刪除操作，我們以最常用的雙向鍊表為例。
鍊表的查找
我們知道，數組由於使用的是連續的內存空間，因此可以通過尋址計算來實現隨機訪問，因此數組的查找很高效。但是鍊表使用的是非連續性的內存空間，因此鍊表無法通過尋址計算直接得出內存地址，只能根據指針一個節點一個節點的依次進行遍歷，直到找到對應的節點為止。因此鍊表查找的時間複雜度為O（n）。
鍊表的插入和刪除
當然不使用連續的存儲空間有弊也有利，鍊表和數組完全相反，鍊表能實現高效的插入和刪除。
如下圖，我們如果想把一個node5插入到node2後面，我們只需要修改node2的後繼指針、node5 的前驅/後繼指針、node3的前驅指針即可：
同理，如下圖，如果我們想把node3刪除，那我們只需要修改node2的後繼指針、node3的前驅/後繼指針、node4的前驅指針即可：
我們可以看出，鍊表的插入和刪除時間複雜度均為O（1）。
單鍊表和雙向鍊表的區別
單鍊表和雙向鍊表的區別就是雙向鍊表插入和刪除更高效。是不是覺得很奇怪？按照我們上面的分析，鍊表的插入和刪除操作時間複雜度均為O(1)，難道有比O(1)更高效的方式？
其實如果我們單純的只看鍊表的插入、刪除操作，確實時間複雜度為O（1）。但是我們如果把鍊表代入實際的業務場景中去，那單鍊表的插入、刪除操作，時間複雜度就不為O（1）了。
以單鍊表的實際插入操作為例，現在鍊表上有node1、node2、node3、node4四個節點，我們要把node5插入到node3前面，我們知道node3的兩部分信息，需要做兩步操作：
1、修改node2後繼指針，讓node2指向node5。
2、修改node5的後繼指針，讓node5指向node3。
修改 node5 的後繼指針很簡單，但是困難的是修改 node2 的後繼指針。我們要修改node2 的後繼指針首先得找到 node2，而由於單鍊表的特性，node3 中沒有存儲 node2的相關信息，因此我們還是得從頭節點開始遍歷鍊表，直到找到node2為止。
修改指針的操作時間複雜為 O(1)，但是尋找 node2 的時間複雜度為 O(n)，因此在單鍊表中node3節點前插入node5節點的整個操作的時間複雜度為O(n) +O(1)=O(n)。
而雙向鍊表則不會如此，因為雙向鍊表中 node3節點已經存儲了 node2 節點的地址信息，可以直接找到node2 節點，因此雙向鍊表整個操作的時間複雜度才為O(1)。
刪除操作則與插入操作類似，因此我們在實際日常開發工作中，雙向鍊表比單鍊表使用的次數更多。
今天我們聊了另外一個基礎的數據架構：鍊表。數組和鍊表在存儲、查找、插入、刪除中各有優缺點，在實際的軟體開發中，我們可以根據具體的業務場景選擇合適的數據結構使用。