LeetCode——LRU Cache

design and implement a data structure for least recently used (lru) cache. it should support the following operations: <code>get</code> and <code>set</code>.

<code>get(key)</code> - get the value

(will always be positive) of the key if the key exists in the cache, otherwise return -1.

<code>set(key, value)</code> - set or insert the value if the key is not already

present. when the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

思路：

最常用的資料結構實作方式是map和double-linked list，map隻是為了實作鍵值key-value對應，這樣就避免了每次尋找特定值都要在雙線連結清單裡面順序查找，伺服器是沒辦法負擔這種低效率的查找方法的。

set流程講解：

在map中查找key，如果找到，說明這個節點已經存在，那麼将該節點的的位置排在連結清單頭部；

如果沒找到，要進行第二個判斷“是否已經達到了max_size”，如果已經達到了，将原來連結清單最後一個節點删除，然後将對應的map中的key-value删除，然後再加入新節點，并在map中加入對應的key-value，如果沒有達到max-size，那麼配置設定新位址給這個節點，同時加入到list和對應的map中。

get比較簡單

代碼：

附：splice是移動連結清單元素的方法

splice執行個體代碼：