部分摘自專欄評(píng)論

1.關(guān)于緩存和緩存淘汰策略

1. 什么是緩存？
   緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計(jì)、軟件開發(fā)中都有著非廣泛的應(yīng)用，比如常見的CPU緩存、數(shù)據(jù)庫緩存、瀏覽器緩存等等。
2. 什么是緩存淘汰策略
   指的是當(dāng)緩存被用滿時(shí)清理數(shù)據(jù)的優(yōu)先順序。
3. 為什么使用緩存淘汰策略？
   緩存的大小是有限的，當(dāng)緩存被用滿時(shí)，哪些數(shù)據(jù)需要被清理出去，哪些數(shù)據(jù)應(yīng)該被保留下來？需要用到緩存淘汰策略。
4. 有哪些緩存淘汰策略
   常見的3種包括先進(jìn)先出策略FIFO（First In，F(xiàn)irst Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。
5. 鏈表實(shí)現(xiàn)LRU緩存淘汰策略
   當(dāng)訪問的數(shù)據(jù)沒有存儲(chǔ)在緩存的鏈表中時(shí)，直接將數(shù)據(jù)插入鏈表表頭，時(shí)間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于存儲(chǔ)的鏈表中時(shí)，將該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)，插入到鏈表表頭,時(shí)間復(fù)雜度為O(n)。如果緩存被占滿，則從鏈表尾部的數(shù)據(jù)開始清理，時(shí)間復(fù)雜度為O(1)
6. 數(shù)組實(shí)現(xiàn)LRU緩存淘汰策略
   方式一：首位置保存最新訪問數(shù)據(jù)，末尾位置優(yōu)先清理
   當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時(shí)，直接將數(shù)據(jù)插入數(shù)組第一個(gè)元素位置，此時(shí)數(shù)組所有元素需要向后移動(dòng)1個(gè)位置，時(shí)間復(fù)雜度為O(n)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時(shí)，查找到數(shù)據(jù)并將其插入數(shù)組的第一個(gè)位置，此時(shí)亦需移動(dòng)數(shù)組元素，時(shí)間復(fù)雜度為O(n)。緩存用滿時(shí)，則清理掉末尾的數(shù)據(jù)，時(shí)間復(fù)雜度為O(1)。
   方式二：首位置優(yōu)先清理，末尾位置保存最新訪問數(shù)據(jù)
   當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時(shí)，直接將數(shù)據(jù)添加進(jìn)數(shù)組作為當(dāng)前最有一個(gè)元素時(shí)間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時(shí)，查找到數(shù)據(jù)并將其插入當(dāng)前數(shù)組最后一個(gè)元素的位置，此時(shí)亦需移動(dòng)數(shù)組元素，時(shí)間復(fù)雜度為O(n)。緩存用滿時(shí)，則清理掉數(shù)組首位置的元素，且剩余數(shù)組元素需整體前移一位，時(shí)間復(fù)雜度為O(n)。（優(yōu)化：清理的時(shí)候可以考慮一次性清理一定數(shù)量，從而降低清理次數(shù)，提高性能。）
7. 如何通過單鏈表實(shí)現(xiàn)“判斷某個(gè)字符串是否為水仙花字符串”？（比如 上海自來水來自海上）
   1）前提：字符串以單個(gè)字符的形式存儲(chǔ)在單鏈表中。
   2）遍歷鏈表，判斷字符個(gè)數(shù)是否為奇數(shù)，若為偶數(shù)，則不是。
   3）將鏈表中的字符倒序存儲(chǔ)一份在另一個(gè)鏈表中。
   4）同步遍歷2個(gè)鏈表，比較對(duì)應(yīng)的字符是否相等，若相等，則是水仙花字串，否則，不是。
8. 設(shè)計(jì)思想
   時(shí)空替換思想：“用空間換時(shí)間” 與 “用時(shí)間換空間”
   當(dāng)內(nèi)存空間充足的時(shí)候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對(duì)較高，時(shí)間復(fù)雜度小相對(duì)較低的算法和數(shù)據(jù)結(jié)構(gòu)，緩存就是空間換時(shí)間的例子。如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，這時(shí)，就要反過來用時(shí)間換空間的思路。

2.關(guān)于鏈表

1. 什么是鏈表

• 鏈表是一種通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來的線性的數(shù)據(jù)結(jié)構(gòu)。

• 鏈表中的每一個(gè)內(nèi)存塊成為鏈表的“結(jié)點(diǎn)”，每個(gè)鏈表的結(jié)點(diǎn)除了儲(chǔ)存數(shù)據(jù)之外，還需要記錄鏈表上的下一個(gè)結(jié)點(diǎn)的地址。如果所示，這個(gè)記錄寫個(gè)結(jié)點(diǎn)地址的指針叫做“后繼指針next”

  
  
  image.png
• 鏈表中有兩個(gè)特殊的結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)，用來記錄鏈表的基地址，通過頭結(jié)點(diǎn)可以遍歷得到整條鏈表。最后一個(gè)結(jié)點(diǎn)叫尾結(jié)點(diǎn)，指向一個(gè)空地址NULL。
• 鏈表的隨機(jī)訪問，

2. 鏈表的特點(diǎn)

1. 插入、刪除數(shù)據(jù)效率高O(1)級(jí)別（只需更改指針指向即可），隨機(jī)訪問效率低O(n)級(jí)別，因?yàn)殒湵碇蓄~數(shù)據(jù)并非連續(xù)存儲(chǔ)的，無法向數(shù)組一樣根據(jù)首地址和下標(biāo)，通過尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址，需要從鏈頭至鏈尾進(jìn)行遍歷
2. 對(duì)鏈表來說，因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)都需要消耗額外的存儲(chǔ)空間去存儲(chǔ)一份指向下一結(jié)點(diǎn)的指針，內(nèi)存消耗會(huì)翻倍，對(duì)鏈表進(jìn)行頻繁的插入、刪除操作，還會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放，容易造成內(nèi)存碎片，對(duì)某些語言，會(huì)導(dǎo)致頻繁的GC

3. 常用鏈表：單鏈表、循環(huán)鏈表和雙向鏈表

• 單鏈表
  1）每個(gè)節(jié)點(diǎn)只包含一個(gè)指針，即后繼指針。
  2）單鏈表有兩個(gè)特殊的節(jié)點(diǎn)，即首節(jié)點(diǎn)和尾節(jié)點(diǎn)。為什么特殊？用首節(jié)點(diǎn)地址表示整條鏈表，尾節(jié)點(diǎn)的后繼指針指向空地址null。
  3）性能特點(diǎn)：插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（1），查找的時(shí)間復(fù)雜度為O(n)。
• 雙鏈表
  1）節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還有兩個(gè)指針分別指向前一個(gè)節(jié)點(diǎn)地址（前驅(qū)指針prev）和下一個(gè)節(jié)點(diǎn)地址（后繼指針next）。
  2）首節(jié)點(diǎn)的前驅(qū)指針prev和尾節(jié)點(diǎn)的后繼指針均指向空地址。
  3）性能特點(diǎn)：
  和單鏈表相比，存儲(chǔ)相同的數(shù)據(jù)，需要消耗更多的存儲(chǔ)空間。
  插入、刪除操作比單鏈表效率更高O(1)級(jí)別。以刪除操作為例，刪除操作分為2種情況：給定數(shù)據(jù)值刪除對(duì)應(yīng)節(jié)點(diǎn)和給定節(jié)點(diǎn)地址刪除節(jié)點(diǎn)。對(duì)于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行刪除，時(shí)間復(fù)雜度為O(n)。對(duì)于第二種情況，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點(diǎn)，單鏈表需要從頭到尾進(jìn)行遍歷直到p->next = q，時(shí)間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)。
  對(duì)于一個(gè)有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢胮，每一次查詢時(shí)，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。
• 循環(huán)鏈表
  1）除了尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)的地址外均與單鏈表一致。
  2）適用于存儲(chǔ)有循環(huán)特點(diǎn)的數(shù)據(jù)，比如約瑟夫問題。
• 雙向循環(huán)鏈表
  首節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)。

4.鏈表和數(shù)組性能大比拼

1. 插入、刪除、隨機(jī)訪問操作的時(shí)間復(fù)雜度

   
   
   image.png
2. 數(shù)組簡單易用，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助CPU的緩存機(jī)制，預(yù)讀數(shù)組中的數(shù)據(jù)，訪問效率更高。鏈表不是連續(xù)存在于內(nèi)存中的，對(duì)CPU緩存不友好，沒有辦法有效預(yù)讀。
   CPU在從內(nèi)存讀取數(shù)據(jù)的時(shí)候，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中。而CPU每次從內(nèi)存讀取數(shù)據(jù)并不是只讀取那個(gè)特定要訪問的地址，而是讀取一個(gè)數(shù)據(jù)塊(這個(gè)大小我不太確定。。)并保存到CPU緩存中，然后下次訪問內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)先從CPU緩存開始查找，如果找到就不需要再從內(nèi)存中取。這樣就實(shí)現(xiàn)了比內(nèi)存訪問速度更快的機(jī)制，也就是CPU緩存存在的意義:為了彌補(bǔ)內(nèi)存訪問速度過慢與CPU執(zhí)行速度快之間的差異而引入。
3. 大小固定，若存儲(chǔ)空間不足，需進(jìn)行擴(kuò)容，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)拷貝制，而這是非常費(fèi)時(shí)的