原文連結
什麼是連結清單
前言
如果說資料結構是算法的基礎，那麼數組和連結清單就是資料結構的基礎。因為像堆，棧，樹，圖等比較複雜的數組結基本上都可以由數組和連結清單來表示，是以掌握數組和連結清單的基本操作十分重要。
今天就來看看連結清單的基本操作及其在面試中的常見解題思路,本文将從以下幾個點來講解連結清單的核心知識
1.什麼是連結清單，連結清單的優缺點
2.連結清單的表示及基本操作
3.面試中連結清單的常見解題思路—翻轉
相信大家已經開始迫不及待地想用連結清單解題了，不過在開始之前我們還是要先來溫習下連結清單的定義，以及它的優勢與劣勢，磨刀不誤砍柴功！
連結清單的定義
連結清單是實體存儲單元上非連續的、非順序的存儲結構，它是由一個個結點，通過指針來聯系起來的，其中每個結點包括資料和指針。
連結清單的非連續，非順序，對應數組的連續，順序，我們來看看整型數組 1，2，3，4 在記憶體中是如何表示的
可以看到數組的每個元素都是連續緊鄰配置設定的，這叫連續性，同時由于數組的元素占用的大小是一樣的，在 Java 中 int 型大小固定為 4 個位元組,是以如果數組的起始位址是 100， 由于這些元素在記憶體中都是連續緊鄰配置設定的，大小也一樣，可以很容易地找出數組中任意一個元素的位置，比如數組中的第三個元素起始位址為 100 + 2 * 4 = 108,這就叫順序性。查找的時間複雜度是O(1),效率很高！
那連結清單在記憶體中是怎麼表示的呢
可以看到每個結點都配置設定在非連續的位置，結點與結點之間通過指針連在了一起，是以如果我們要找比如值為 3 的結點時，隻能通過結點 1 從頭到尾周遊尋找，如果元素少還好，如果元素太多（比如超過一萬個），每個元素的查找都要從頭開始查找，時間複雜度是O(n)，比起數組的 O(1)，差距不小。
除了查找性能連結清單不如數組外，還有一個優勢讓數組的性能高于連結清單,這裡引入程式局部性原理，啥叫程式局部性原理。
我們知道 CPU 運作速度是非常快的，如果 CPU 每次運算都要到記憶體裡去取資料無疑是很耗時的，是以在 CPU 與記憶體之間往往內建了挺多層級的緩存，這些緩存越接近CPU，速度越快，是以如果能提前把記憶體中的資料加載到如下圖中的 L1, L2, L3 緩存中，那麼下一次 CPU 取數的話直接從這些緩存裡取即可，能讓CPU執行速度加快，那什麼情況下記憶體中的資料會被提前加載到 L1,L2,L3 緩存中呢，答案是當某個元素被用到的時候，那麼這個元素位址附近的的元素會被提前加載到緩存中
以上文整型數組 1，2，3，4為例，當程式用到了數組中的第一個元素（即 1）時，由于 CPU 認為既然 1 被用到了，那麼緊鄰它的元素 2，3，4 被用到的機率會很大，是以會提前把 2，3，4 加到 L1,L2,L3 緩存中去，這樣 CPU 再次執行的時候如果用到 2，3，4，直接從 L1,L2,L3 緩存裡取就行了，能提升不少性能
畫外音：如果把 CPU 的一個時種看成一秒，則從 L1 讀取資料需要 3 秒，從 L2 讀取需要 11 秒，L3讀取需要 25秒，而從記憶體讀取呢，需要 1 分 40 秒，是以程式局部性原理能對 CPU 執行性能有很大的提升
而連結清單呢，由于連結清單的每個結點在記憶體裡都是随機分布的，隻是通過指針聯系在一起，是以這些結點的位址并不相鄰，自然無法利用 程式局部性原理 來提前加載到 L1,L2,L3 緩存中來提升程式性能。
畫外音：程式局部性原理是計算機中非常重要的原理，這裡不做展開，建議大家查閱相關資料詳細了解一下
如上所述，相比數組，連結清單的非連續，非順序确實讓它在性能上處于劣勢，那什麼情況下該使用連結清單呢？考慮以下情況
- 大記憶體空間配置設定
由于數組空間的連續性，如果要為數組配置設定 500M 的空間，這 500M 的空間必須是連續的，未使用的，是以在記憶體空間的配置設定上數組的要求會比較嚴格，如果記憶體碎片太多，配置設定連續的大空間很可能導緻失敗。而連結清單由于是非連續的，是以這種情況下選擇連結清單更合适。
- 元素頻繁删除和插入
如果涉及到元素的頻繁删除和插入，用連結清單就會高效很多，對于數組來說，如果要在元素間插入一個元素，需要把其餘元素一個個往後移（如圖示），以為新元素騰空間（同理，如果是删除則需要把被删除元素之後的元素一個個往前移），效率上無疑是比較低的。
(在 1，2 間插入 5，需要把2，3，4 同時往後移一位)
後移：
插入5：
完成！
而連結清單的插入删除相對來說就比較簡單了，修改指針位置即可，其他元素無需做任何移動操作（如圖示：以插入為例）
完成：
綜上所述：如果資料以查為主，很少涉及到增和删，選擇數組，如果資料涉及到頻繁的插入和删除，或元素所需配置設定空間過大，傾向于選擇連結清單。
說了這麼多理論，相信讀者對數組和連結清單的差別應該有了更深刻地認識了，尤其是程式局部性原理，是不是開了不少眼界^_^，如果面試中問到數組和連結清單的差別能回答到程式局部性原理，會是一個非常大的亮點！
了解更多算法内容，請持續關注：
阿裡雲開發者社群算法程式設計官方技術圈!
下一節：連結清單的表示來源 | 五分鐘學算法
作者 | 程式員小吳