數組 & 鏈表
數組
是一種線性表數據結構，它用一組連續的記憶體空間，來存儲一組具有相同類型的數據。
使用了連續的記憶體空間和相同類型的數據，使得它可以「隨機訪問」，但同時也讓數組的刪除，插入等操作變得非常低效，
為了保證連續性，就需要做大量的數據搬移工作。 數組是從0開始編號的，目的是為了減少一次減法運算。
設計思想
空間換時間 & 時間換空間
空間換時間 ：當記憶體空間充足的時候，為了追求程式碼更快的執行速度，
就可以捨棄對存儲空間的要求，從而追求效率。
時間換空間 ：記憶體空間比較緊缺時，為了讓程式穩定運行，
就需要捨棄時間，極大滿足對存儲空間的要求。
快取
實際上 就是利用了空間換時間的設計思想。如果我們把 數據存儲在硬碟上，會比較節省記憶體，
但每次查找數據都要詢問一次硬碟，會比較慢。
但如果我們通過快取，提前將數據載入在記憶體中，雖然會比較消耗記憶體，但是查數據的速度就提高了。
對於執行較慢的程式，可以通過消耗更多記憶體（空 換 時）來優化
對於記憶體消耗過多的程式，可以通過消耗更多的時間（時 換 空）來降低記憶體的消耗
二維數組記憶體定址公式
對於 m * n 的數組，a[i][j] (i<m,j<n)的地址為：
address = base_address + (i*n+j)*type_size
鏈表的存儲結構
數組需要一塊連續的記憶體空間來存儲，需要事先申請需要申請記憶體空間；
而鏈表通過「指針」將一組零散的記憶體塊串聯起來使用，不會佔用還未使用的記憶體空間。
單鏈表
鏈表通過指針將一組零散的記憶體塊串聯在一起，記憶體塊稱為鏈表的「結點」。
每個鏈表的結點除了存儲數據之外，還需要記錄鏈上的下一個結點的地址，叫作後繼指針 next。
循環鏈表
循環鏈表跟單鏈表的區在尾結點指針是指向鏈表的頭結點。
雙向鏈表
雙向鏈表支援兩個方向，每個結點同時有後繼指針 next 指向後面的結點，
還有一個前驅指針 prev 指向前面的結點。
LRU-快取
快取是一種提高數據讀取性能的技術，在硬體設計、軟體開發中都有著非常廣泛的應用，
比如常見的CPU快取、資料庫快取、瀏覽器快取。
常見的快取淘汰策略
先進先出策略 FIFO
最少使用策略 LFU
最近最少使用策略 LRU
思路：
維護一個有序單列表，越靠近鏈表尾部的節點越早之前訪問的。
當有一個新的數據被訪問時，從鏈表頭開始順序遍歷鏈表：
1 如果此數據之前已經被快取進鏈表中了，遍歷得到這個數據對應的節點，
並將其從原來的位置刪除，然後再插入到鏈表的頭部
2 如果此數據沒有在快取鏈表中，則將此節點插入到鏈表的頭部：
如果此時快取超過容量，則鏈表尾節點刪除。
迴文字元串： 是一個正讀和反讀都一樣的字元串
判斷思路 ：
1使用快慢兩個指針找到鏈表中點，慢指針每次前進一步，快指針每次前進2步，這樣當快指針指向末尾時，
慢指針指向了中點。
2 在慢指針前進的過程中，同時修改其next指針指向上一個元素prev，使得鏈表前半部分反序
3 最後比較重點兩側的鏈表是否相等。
鏈表 VS 數組 （對比）
數組簡單易用，在是線上使用的是連續的記憶體空間，可以藉助CPU的快取機制，
預都數組中的數據，所以訪問效率更高
鏈表在記憶體中並不是連續存儲，所以對CPU快取不友好，沒辦法有效預讀
缺點
數組的缺點是大小固定，一經聲明就要佔用整塊連續記憶體空間。如果聲明的數組過大，
系統可能沒有足夠的連續記憶體空間分配給它，導致「記憶體不足」。
如果聲明的數組過小，則可能出現不夠用的情況。
這時只能再申請一個更大的記憶體空間，把原數組拷貝進去，非常費時。
鏈表本身沒有大小的限制，天然地支援動態擴容
如果 對 記憶體的使用非常苛刻數組就更合適，因為鏈表中的每個結點都需要消耗額外的存儲空間去存儲一份指向下一個節點的指針
所以記憶體消耗會翻倍
對鏈表進行頻繁的插入、刪除操作，會導致頻繁的記憶體申請和釋放，容易造成記憶體碎片，對於Python程式語言，
就有可能頻繁的GC（Garbage Collection，垃圾回收）。
