原文鏈接
一個(gè)更好的實(shí)現(xiàn)
作為演示代碼狗热，做了以下的簡(jiǎn)化處理：

• 緩存結(jié)果是網(wǎng)絡(luò)查詢結(jié)果
• 不對(duì)輸入進(jìn)行校驗(yàn)
• 假設(shè)內(nèi)存能夠存放所有內(nèi)容

class Node(object):

    def __init__(self, results):
        self.results = results
        self.prev = None
        self.next = None


class LinkedList(object):

    def __init__(self):
        self.head = None
        self.tail = None

    def move_to_front(self, node):  # ...
    def append_to_front(self, node):  # ...
    def remove_from_tail(self):  # ...


class Cache(object):

    def __init__(self, MAX_SIZE):
        self.MAX_SIZE = MAX_SIZE
        self.size = 0
        self.lookup = {}  # key: query, value: node
        self.linked_list = LinkedList()

    def get(self, query)
        """Get the stored query result from the cache.
        
        Accessing a node updates its position to the front of the LRU list.
        """
        node = self.lookup.get(query)
        if node is None:
            return None
        self.linked_list.move_to_front(node)
        return node.results

    def set(self, results, query):
        """Set the result for the given query key in the cache.
        
        When updating an entry, updates its position to the front of the LRU list.
        If the entry is new and the cache is at capacity, removes the oldest entry
        before the new entry is added.
        """
        node = self.lookup.get(query)
        if node is not None:
            # Key exists in cache, update the value
            node.results = results
            self.linked_list.move_to_front(node)
        else:
            # Key does not exist in cache
            if self.size == self.MAX_SIZE:
                # Remove the oldest entry from the linked list and lookup
                self.lookup.pop(self.linked_list.tail.query, None)
                self.linked_list.remove_from_tail()
            else:
                self.size += 1
            # Add the new key and value
            new_node = Node(results)
            self.linked_list.append_to_front(new_node)
            self.lookup[query] = new_node

從數(shù)據(jù)結(jié)構(gòu)上來講，主要用到的是鏈表（比較好的方式其實(shí)是雙鏈表事期，有時(shí)會(huì)配合哈希表來提升查詢效率）。
下面是Leetcode上的題目參考解法：

class List(object):
    @staticmethod
    def delete(elem):
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
        return elem
    
    @staticmethod   
    def move(elem, newPrev, newNext):
        elem.prev = newPrev
        elem.next = newNext
        newPrev.next = elem
        newNext.prev = elem
        
    @staticmethod
    def append(head, elem):
        List.move(elem, head.prev, head)
    
    @staticmethod
    def isEmpty(head):
        return head.next == head.prev == head
        
    @staticmethod
    def initHead(head):
        head.prev = head.next = head

class Node(object):
    def __init__(self, key, value, head):
        self.key = key
        self.value = value
        self.head = head
        self.prev = self.next = None
        
    def hit(self):
        List.delete(self)
        List.append(self.head, self)

class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.d = {}
        self.cap = capacity
        self.head = Node(-1, -1, None)
        List.initHead(self.head)

    def get(self, key):
        """
        :rtype: int
        """
        if key not in self.d:
            return -1
        self.d[key].hit()
        return self.d[key].value
        

    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if self.cap == 0:
            return
        
        if key in self.d:
            self.d[key].hit()
            self.d[key].value = value
        else:
            if len(self.d) >= self.cap:
                oldNode = List.delete(self.head.next)
                del self.d[oldNode.key]
                
            newNode = Node(key, value, self.head)
            List.append(self.head, newNode)
            self.d[key] = newNode