題目目錄LRU Cache

字典負責一步找到節點，雙向串列負責排順序：左邊最久沒用，右邊最近使用。

GET / PUT O(1)空間 O(capacity)

01 / 字典與雙向串列INITIALIZE

操作—

len(cache) / capacity0

回傳—

記憶體 nxt prev cache[key]

輸出

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：為什麼要字典加雙向串列？

字典找得快，串列搬得快。

cache 把 key 對到節點本身，所以 get 不用從頭走訪，一步就拿到節點。

拿到節點後，因為它有 prev 和 nxt，remove 只要改兩根指標就能把它摘下；insert 再改四根指標把它接到 right 前面。整個搬移不需要移動其他節點。

left、right 是兩個不存資料的哨兵，讓「串列是空的」或「節點在最邊邊」都不用特別處理。 left.nxt 永遠是最久沒用的節點，容量超過時就淘汰它，並從字典刪掉它的 key。

節點方塊上的 N1、N2 是節點本身的身分，key、val 是它存的資料。put 同一個 key 時，這份程式會建立新節點，舊節點就沒有人再指向它。