數(shù)組和鏈表

數(shù)據(jù)是使用連續(xù)的內(nèi)存空間存儲數(shù)據(jù)。

鏈表是使用不連續(xù)的內(nèi)存空間存儲數(shù)據(jù)。

常見鏈表鏈表結(jié)構(gòu)

• 單鏈表

• 循環(huán)鏈表

• 雙向鏈表

基本概念

結(jié)點

分配用來存儲數(shù)據(jù)的每個不連續(xù)的內(nèi)存塊就是結(jié)點。

后繼指針

既然內(nèi)存塊不是連續(xù)的，那么這些值是如何關(guān)聯(lián)起來的。這時候就會通過后繼指針來串聯(lián)這些結(jié)點。每個結(jié)點除了存儲數(shù)據(jù)外，還要存儲下一個結(jié)點的內(nèi)存地址，就是通過后繼指針next指向的。

頭結(jié)點

頭結(jié)點就是鏈表起始結(jié)點，用于存儲鏈表的基地址。

頭結(jié)點一般不存儲數(shù)據(jù)。

指向頭結(jié)點的指針成為頭指針。

尾結(jié)點

就是最后一個結(jié)點，該結(jié)點指針區(qū)域不指向任何結(jié)點，而是指向一個空地址NULL。

單鏈表

單鏈表從頭結(jié)點開始到尾結(jié)點結(jié)束的鏈表。

其插入和刪除的時間復(fù)雜度為O(1)，查找的時間復(fù)雜度為O(n)

對應(yīng)的，數(shù)據(jù)插入和刪除的時間復(fù)雜度為O(n)，查找的時間復(fù)雜度為O(1)

循環(huán)鏈表

區(qū)別于單鏈表，循環(huán)鏈表就是將尾結(jié)點的指針指向了頭結(jié)點，形成一個閉環(huán)，即為循環(huán)鏈表。

循環(huán)鏈表的優(yōu)點就是從鏈尾到鏈頭比較方便。

雙向鏈表

顧名思義，每個結(jié)點不僅有指向下一個結(jié)點，同時還有了指向上一個結(jié)點。

顯然，相比之前的鏈表結(jié)構(gòu)，該鏈表結(jié)構(gòu)增加了空間消耗，那么必然，在時間上會得到補償，典型的空間換時間。

下面我們來看看雙向鏈表是如何實現(xiàn)空間換時間的。

我們還是說回普通鏈表的插入和刪除操作。

刪除操作

更加準(zhǔn)確的說刪除操作會有兩種情況

• 刪除結(jié)點中“值等于某個給定值”的結(jié)點

• 刪除給定指針指向的結(jié)點

對于第一種情況，如果只是刪除，那么時間復(fù)雜度就是O(1)。但是在此之前，我們需要找到這個節(jié)點，鑒于鏈表內(nèi)存結(jié)構(gòu)的不連續(xù)性，需要一一遍歷才能找到這個結(jié)點，所以時間復(fù)雜度是O(n)，最終時間復(fù)雜度也是O(n)。

對于第二種情況，和第一種情況類似，遍歷找到這個接口并刪除，時間復(fù)雜度也是O(n)。

上面說的是單鏈表，如果這時候是雙鏈表結(jié)構(gòu)，情況就會不太一樣。

第一種情況，依然無法避免，因為鏈表內(nèi)存結(jié)構(gòu)不連續(xù)的事實無法改變。

第二種情況，具體的操作是找到指定的結(jié)點，然后將該結(jié)點的上一個結(jié)點的后繼指針指向該結(jié)點的下一個結(jié)點。但是在雙線鏈表就不一樣了，找到當(dāng)前節(jié)點就可以無縫平滑的找到其上一個結(jié)點，而不需要傻乎乎的從頭結(jié)點開始遍歷一直找。所以這時候的時間復(fù)雜度從O(n)變?yōu)榱薕(1)。這就是典型的空間換時間。

空間換時間和時間換空間

針對不同的場景，我們需要在時間和空間之前做一個權(quán)衡。

比如緩存就是一個典型的空間換時間，我們希望接口的響應(yīng)速度更快更及時，所以我們一次性將數(shù)據(jù)加載到緩存即內(nèi)存，這樣訪問的速度變快了，但是在空間層面上，我們占用了更多的內(nèi)存資源。

分頁請求等這些就是時間換空間，我們每次只使用有限的空間存儲返回結(jié)果，但是需要分多次請求返回（可能不是十分恰當(dāng)，意在表明，當(dāng)空間資源稀缺貨有限時，可以通過延長時間來彌補）

數(shù)組和鏈表的比較

數(shù)組是固定大小的，如果要擴容，需要重新申請一個更大的內(nèi)存空間并拷貝原來的數(shù)組內(nèi)容。

鏈表是天然支持動態(tài)擴容的，能夠很好的利用碎片的內(nèi)存空間。

如果你的代碼對內(nèi)存使用非?？量?，建議使用數(shù)組。因為鏈表除了保存數(shù)據(jù)的內(nèi)存空間，還需要內(nèi)存空間用來存儲下一個結(jié)點的內(nèi)存地址，所以空間占用會翻倍。

鏈表的插入和刪除會帶來內(nèi)存的申請和釋放，容易造成內(nèi)存碎片，對于Java語言來說，會導(dǎo)致頻繁的GC（垃圾回收）。

如何基于鏈表實現(xiàn)LRU緩存淘汰算法

LRU（Least Recently used）最近最少使用算法是緩存淘汰的算法之一。

意思就是最近時間內(nèi)，使用次數(shù)最少的緩存內(nèi)容就優(yōu)先刪除。

實現(xiàn)思路

使用一個鏈表存儲緩存的數(shù)據(jù)，從頭至尾，越靠近頭結(jié)點表示越是最近訪問的數(shù)據(jù)，越靠近尾結(jié)點表示越是久遠(yuǎn)訪問過的數(shù)據(jù)。

如果訪問的某個數(shù)據(jù)已經(jīng)被緩存在這個鏈表中，我們通過遍歷找到這個結(jié)點后就刪除，然后將這個結(jié)點插入到頭結(jié)點。

如果這個數(shù)據(jù)沒有在鏈表中，這時候繼續(xù)判斷，如果緩存沒有滿，則將此結(jié)點插入到頭結(jié)點。如果緩存已滿，則刪除尾結(jié)點，并將新數(shù)據(jù)插入頭結(jié)點。

使用鏈表實現(xiàn)這個問題，正是利用鏈表插入和刪除方便的特性，同時頭尾指針的順序也正好可能映射緩存被訪問的熱度。