class Node:
    key = None
    value = None
    pre = None
    next = None
    
    def __init__(self, key, value):
        self.key = key
        self.value = value
    
class LRUCache:
    capacity = 0
    mapping = {}
    head = None
    end = None
    
    def __init__(self, capacity):
        self.capacity = capacity

    def set(self, key, value):
        if key in self.mapping:
            oldNode = self.mapping[key]
            oldNode.value = value
            self.remove(oldNode)
            self.set_head(oldNode)
        else:
            node = Node(key, value)
            if len(self.mapping) >= self.capacity:
                self.mapping.pop(self.end.key)
                self.remove(self.end)
                self.set_head(node)
            else:
                self.set_head(node)
            self.mapping[key] = node
            
    def set_head(self, n):
        n.next = self.head
        n.pre = None
        if self.head:
            self.head.pre = n
        self.head = n
        if not self.end:
            self.end = self.head
            
    def remove(self, n):
        if n.pre:
            n.pre.next = n.next
        else:
            self.head = n.next
        
        if n.next:
            n.next.pre = n.pre
        else:
            self.end = n.pre
            
    def get_all_keys(self):
        tmp_node = None
        if self.head:
            tmp_node = self.head
            temp = "<{0},{1}>"
            result = ""
            while tmp_node:
                tmp = temp.format(tmp_node.key, tmp_node.value)
                result += tmp
                result += " -> "
                tmp_node = tmp_node.next
            tmp = temp.format(None, None)
            result += tmp
            print(result)
                    
    def get(self, key):
        if key in self.mapping:
            node = self.mapping[key]
            self.remove(node)
            self.set_head(node)
            return node.value
        else:
            return -1
            
        
if __name__ == '__main__':
    cache = LRUCache(100)
    
    cache.set('a', '1')
    cache.set('b', '2')
    cache.set('c', 3)
    cache.set('d', 4)
    
    cache.get_all_keys()
    
    cache.set('a', 5)   
    cache.get_all_keys()
    
    cache.get('c')
    cache.get_all_keys()
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄