對於不少開發者而言，連結串列（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++的專案學習影片資料哦！已經設定好了關鍵詞自動回覆，自動領取就好了！
