引導
????????今天我們進入鏈表的學習，我相信大家對鏈表都很熟悉。鏈表和數組一樣，作為最基礎的數據結構。在我們的工作中常常會使用到。但是我們真的了解到數組和鏈表的區別嗎？什么時候使用數組，什么時候使用鏈表，能夠正確的選取嗎？
????????鏈表需要我們進行一些練習才能更好的掌握。我后面也會結合幾個經典的練習題進行訓練。
鏈表和數組區別
????????數組和鏈表的最大區別就是存儲了。從上一欄，我們了解到數組的存儲結構是連續的。鏈表與之恰恰相反，它可以利用內存中零碎的內存空間。如圖：
????????這樣就存在一個問題；當我們向內存申請100M的數組時，即使內存剩余200M內存，但經常會提示申請失敗“out of memory”。因為內存中存在著很多的內存碎片，導致200M內存中基本不存在100M連續的。但是鏈表就不會存在這種情況，因為它支持動態分配，不需要內存地址上的連續要求。
單鏈表
????????單鏈表，是比較簡單的了，并且也比較常見。結構圖如下：
單鏈表的刪除，新增操作的時間復雜度？
????????我們知道數組的刪除，新增操作，要進行數據的搬移（保證數據的連續性）。導致數組的復雜度為O(n)。但是單鏈表并不需要進行數據的搬移，只要修改節點的指針的指向即可。所以鏈表的復雜度時O(1)。
單鏈表的隨機訪問的時間復雜度？
????????數組的存儲是連續的，當知道下標時，數組復雜度O(1);但是鏈表由于不是連續存儲的，所以在訪問第i個節點時，需要從頭節點，一個接一個遍歷。因此鏈表復雜度O(n)。
循環鏈表
????????循環鏈表其實就是特殊的單鏈表（尾節點指向了頭節點）。因此它也不是很難。不過對于特殊的問題，使用循環鏈表比較方便。比圖經典的約瑟夫問題。結構圖如下：
雙向鏈表
????????雙向鏈表雖然我們接觸的不多，但在項目中，雙向鏈表比單鏈表使用的更加廣泛。 雙向鏈表其實就是多了一個指針變量，指向了前節點。結構圖如下：
????????正如我們上面說的雙向鏈表在工作中使用的往往比單鏈表要廣泛，為什么呢？
從鏈表的刪除舉例，刪除鏈表的中節點，無非就是以下兩種情況：
- 刪除節點中，值等于某個特定值的節點
- 刪除給定指針指向的節點
????????對于第一種情況，無論是單鏈表或雙鏈表都要先找到對應的節點，再進行刪除操作。 根據復雜度的加法原則，O(n)+O(1)=O(n)。兩者的復雜度都是O(n)。
????????對于第二種情況，給定一個需要刪除節點之后，僅需要將該節點的前節點指向該節點的下一個節點即可。
????????但是單向鏈表需要進行遍歷，找到該節點的前節點。需要O(n)。所以單鏈表需要O(n)。但是由于雙向鏈表每個節點有指向前節點的指針。故雙向鏈表僅需O(1)。
????????其實第二種情況，是我們經常會遇到的，比如LinkedHashMap容器，就是使用了雙向鏈表。
????????不僅僅時刪除和插入操作，雙向鏈表比單向鏈表高效。其實查詢也會比單向鏈表高效。比如在一個有序的鏈表中，我們可以保存上一次查詢節點，判斷查詢值的大小，采取向上還是從下查詢的方式。
????????其實這就是一個空間換時間的例子，雙向鏈表雖然比單向鏈表要高效，但是它比單向鏈表多一個指針變量。因此消耗的內存資源也會比較多。
數組和鏈表的選擇
我覺得數組和鏈表的選擇應該要結合以下幾點因素考慮：
1. 時間復雜度
????????數組的隨機訪問時間復雜度是O(1),刪除操作的復雜度O(n);鏈表的隨機訪問的復雜度是O(n),刪除操作的復雜度O(1);結合你的業務邏輯，評價主要是查詢操作居多還是刪除操作居多。
2. 內存要求
????????因為鏈表中每個節點需要一個指向下一個節點的指針變量，所以鏈表比數組消耗更多的內存資源。當你的內存資源比較有限的情況下，我還是建議你使用數組。
3. 性能提高--CPU緩存機制
????????我們知道數組的訪問比鏈表要高效。但是這只是從時間復雜度來分析的。但是不僅僅如此，數組在訪問操作時，因為cache機制的存在，效率會更加高。因此，如果你想更進一步提高訪問的效率，我建議你也選擇數組。
總結：綜上所述，數組有這么多的優勢，我們是不是基本都選擇數組呢？我們工作中基本還是選擇鏈表較多。因為我們基本不會存在性能和內存資源上的擔憂，并且鏈表使用起來還是比較方便的。
什么是CPU緩存機制？
????????上面我們談到了CPU緩存機制，數組對CPU緩存機制比較友好能夠加快訪問效率，但是鏈表對其不友好，不能提高效率。但是何為CPU緩存機制呢？其實它是依據操作系統中局部性原理來實現的。
????????所謂的局部性原理，包括兩個部分：時間局部性和空間局部性。時間局部性指的是最近訪問的存儲位置，很可能在不久的將來還要訪問；空間局部性指存儲訪問有聚集的傾向，當訪問了某一個位置之后，很有可能也要訪問附近的位置。
????????我們知道Cache是高速訪問的緩存，比內存的訪問還要快。CPU從內存中訪問數據并不會僅僅只獲取該地址的內容。而是會將該內容在內的物理塊一起放到Cache緩存中。下次再讀取內容時，首先再Cahce中找，找不到再從內存中重復上面的操作。
????????因為數組的存儲空間是連續的，所以能夠很好的適應CPU緩存機制。但是鏈表是非連續存儲的，所以對CPU緩存機制不友好。
總結
????????了解了數組和鏈表之間的區別，以及如何選擇數組和鏈表數據結構。數組對CPU緩存機制更加友好。
】)
