# 思路1 利用链表

把最近一次用过的放到链表头部

保持把新鲜数据往链表头移动。新鲜的定义：刚被修改(put)，或者访问过(get)，就算新鲜，就需要 splice 到链表头。 过期键直接 pop\_back()，链表节点越往后，越陈旧。

代码要领： map 中保存的是 ，这样查找的时候就不用需要去遍历链表了，使用 unordered\_map 就能很快找到链表节点指针。 判断容量的时候，最好不使用 std::list::size() 方法，在 c++ 里，这个方法可能不是 O(1) 的。

python中手动实现一个链表

python中list 的pop(0) and insert(0, v)都是O(n)时间复杂度 deque则是双向链表，首尾删插都是O(1)时间复杂度
