起因：我的同事需要一個固定大小的cache，如果記錄在cache中，直接從cache中讀取，否則從數據庫中讀取。python的dict 是一個非常簡單的cache,但是由于數據量很大，內存很可能增長的過大，因此需要限定記錄數，并用LRU算法丟棄舊記錄。key 是整型，value是10KB左右的python對象

分析：

1）可以想到，在對于cache，我們需要維護 key -> value 的關系

2）而為了實現LRU，我們又需要一個基于時間的優先級隊列，來維護   timestamp  -> (key, value) 的關系

3）當cache 中的記錄數達到一個上界maxsize時，需要將timestamp 最小的(key,value) 出隊列

4) 當一個（key, value) 被命中時，實際上我們需要將它從隊列中，移除并插入到隊列的尾部。

從分析可以看出我們的cache 要達到性能最優需要滿足上面的四項功能，對于隊表的快速移除和插入，鏈表顯然是最優的選擇，為了快速移除，最好使用雙向鏈表，為了插入尾部，需要有指向尾部的指針。

下面用python 來實現：

代碼如下:
#encoding=utf-8

class LRUCache(object):
    def __init__(self, maxsize):
        # cache 的最大記錄數
        self.maxsize = maxsize
        # 用于真實的存儲數據
        self.inner_dd = {}
        # 鏈表-頭指針
        self.head = None
        # 鏈表-尾指針
        self.tail = None

    def set(self, key, value):
        # 達到指定大小     
        if len(self.inner_dd) >= self.maxsize:
            self.remove_head_node()

        node = Node()
        node.data = (key, value)
        self.insert_to_tail(node)
        self.inner_dd[key] = node

    def insert_to_tail(self, node):
        if self.tail is None:
            self.tail = node
            self.head = node
        else:
            self.tail.next = node
            node.pre = self.tail
            self.tail = node