對于不少開發者而言，連結清單(linked list)這種資料結構既熟悉又陌生，熟悉是因為它确實是非常基礎的資料結構，陌生的原因是我們在業務開發中用到它的幾率的确不大。
在很多情況下，我們用數組就能很好的完成工作，而且不會産生太多的差異，那麼連結清單存在的意義是什麼？連結清單相比于數組有什麼優勢或者不足嗎？
什麼是連結清單
連結清單是一種常見的基礎資料結構，是一種線性表，但是并不會按線性的順序存儲資料，而是在每一個節點裡存到下一個節點的指針(Pointer)。
從本質上來講,連結清單與數組的确有相似之處，他們的相同點是都是線性資料結構，這與樹和圖不同，而它們的不同之處在于數組是一塊連續的記憶體，而連結清單可以不是連續記憶體，連結清單的節點與節點之間通過指針來聯系。
當然,連結清單也有不同的形态，主要分為三種：單向連結清單、雙向連結清單、循環連結清單。
單向連結清單
單向連結清單的節點通常由兩個部分構成，一個是節點儲存的值val，另一個就是節點的指針next。
連結清單與數組類似,也可以進行查找、插入、删除、讀取等操作，但是由于連結清單與數組的特性不同，導緻不同操作的複雜度也不同。
查找性能
單向連結清單的查找操作通常是這樣的：
（1）從頭節點進入，開始比對節點的值，如果不同則通過指針進入下一個節點
（2）重複上面的動作，直到找到相同的值，或者節點的指針指向null
連結清單的查找性能與數組一樣，都是時間複雜度為O(n)。
插入删除性能
連結清單與數組最大的不同就在于删除、插入的性能優勢，由于連結清單是非連續的記憶體，是以不用像數組一樣在插入、删除操作的時候需要進行大面積的成員位移，比如在a、b節點之間插入一個新節點c，連結清單隻需要：
a斷開指向b的指針，将指針指向c
c節點将指針指向b，完畢
這個插入操作僅僅需要移動一下指針即可，插入、删除的時間複雜度隻有O(1).
連結清單的插入操作如下：
連結清單的删除操作如下：
讀取性能
連結清單相比之下也有劣勢，那就是讀取操作遠不如數組，數組的讀取操作之是以高效，是因為它是一塊連續記憶體，數組的讀取可以通過尋址公式快速定位，而連結清單由于非連續記憶體，是以必須通過指針一個一個節點周遊。
比如,對于一個數組，我們要讀取第三個成員，我們僅需要arr[2]就能快速擷取成員，而連結清單則需要從頭部節點進入，在通過指針進入後續節點才能讀取。
應用場景
由于雙向連結清單的存在，單向連結清單的應用場景比較少，因為很多場景雙向連結清單可以更出色地完成。
但是單向連結清單并非無用武之地，在以下場景中依然會有單向連結清單的身影：
（1）撤銷功能，這種操作最多見于各種文本、圖形編輯器中，撤銷重做在編輯器場景下屬于家常便飯，單向連結清單由于良好的删除特性在這個場景很适用。
（2）實作圖、hashMap等一些進階資料結構
雙向連結清單
我們上文已經提到，單向連結清單的應用場景并不多，而真正在生産環境中被廣泛運用的正是雙向連結清單。
雙向連結清單與單向連結清單相比有何特殊之處？
我們看到雙向連結清單多了一個新的指針prev指向節點的前一個節點,當然由于多了一個指針，是以雙向連結清單要更占記憶體。
别小看雙向連結清單多了一個前置指針，在很多場景裡由于多了這個指針，它的效率更高，也更加實用。
比如編輯器的「undo/redo」操作，雙向連結清單就更加适用，由于擁有前後指針，使用者可以自由得進行前後操作，如果這個是一個單向連結清單，那麼使用者需要周遊連結清單這時的時間複雜度是O(n)。
真正生産級應用中的編輯器采用的資料結構和設計模式更加複雜，比如Word就是采用Piece Table資料結構加上Command queue模式實作「undo/redo」的，不過這是後話了。
循環連結清單
循環連結清單,顧名思義，他就是将單向連結清單的尾部指針指向了連結清單頭節點：
循環連結清單一個應用場景就是作業系統的分時問題，比如有一台計算機，但是有多個使用者使用，CPU要處理多個使用者的請求很可能會出現搶占資源的情況，這個時候計算機會采取分時政策來保證每個使用者的使用體驗。
每個使用者都可以看成循環連結清單上的節點，CPU會給每個節點配置設定一定的處理時間，在一定的處理時間後進入下一個節點,然後無限循環，這樣可以保證每個使用者的體驗，不會出現一個使用者搶占CPU而導緻其他使用者無法響應的情況。
當然，約瑟夫環的問題是單向循環連結清單的代表性應用，感興趣的可以深入了解下。
當然如果是雙向連結清單首尾相接呢？這就是雙向循環連結清單。
在Node中有一類場景，沒有查詢，但是卻有大量的插入和删除，這就是Timer子產品。
幾乎所有的網絡I/O請求，都會提供timeout操作控制socket的逾時狀況，這裡就會大量使用到setTimeout，并且這些timeout定時器，絕大部分都是用不到的（資料按時正常響應），那麼又會有響應的大量clearTimeout操作，是以node采用了雙向循環連結清單來提高Timer子產品的性能,至于其中的細節就不再贅述了。
插入！
TimersList <-----> timer1 <-----> timer2 <-----> timer4 <-----> timer3 <-----> ......
1000ms後執行 1050ms後執行 1100ms後執行 1200ms後執行 小結
至此,我們對連結清單這個資料結構有了一定的認知,由于其非連續記憶體的特性導緻連結清單非常适用于頻繁插入、删除的場景，而不見長于讀取場景，這跟數組的特性恰好形成互補，是以現在也可以回到題目中的問題了，連結清單的特性與數組互補，各有所長，而且連結清單由于指針的存在可以形成環形連結清單，在特定場景也非常有用，是以連結清單的存在是很有必要的。
作者：尋找海藍96
另外的話為了幫助大家，輕松，高效學習C語言/C++，我給大家分享我收集的資源，從最零基礎開始的教程到C語言項目案例，幫助大家在學習C語言的道路上披荊斬棘！可以來我粉絲群領取哦~
程式設計學習書籍分享：
程式設計學習視訊分享：
整理分享（多年學習的源碼、項目實戰視訊、項目筆記，基礎入門教程）最重要的是你可以在群裡面交流提問程式設計問題哦！
對于C/C++感興趣可以關注小編在背景私信我：【程式設計交流】一起來學習哦！可以領取一些C/C++的項目學習視訊資料哦！已經設定好了關鍵詞自動回複，自動領取就好了！