LRU缓存

Idea

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

理解：用Hash字典、双链表构造LRU（Least Recently Used）最近最少使用

class DLinkedNode:
    def __init__(self,key=0,value=0):
        self.key=key
        self.value=value
        self.prev=None
        self.next=None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache=dict() #哈希字典
        self.capacity=capacity #容量
        self.size=0 #已用大小
        self.head=DLinkedNode() #哑巴头节点
        self.tail=DLinkedNode() #哑巴尾节点
        self.head.next=self.tail
        self.tail.prev=self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node=self.cache[key]
        self.moveToHead(node) #删除,移至头节点
        return node.value

    def put(self, key: int, value: int) -> None: #放置
        if key not in self.cache:
            node=DLinkedNode(key,value)
            self.cache[key]=node
            self.addToHead(node)
            self.size+=1
            if self.size>self.capacity:
                removedNode=self.removeTail()
                self.cache.pop(removedNode.key)
                self.size-=1
        else:
            node=self.cache[key]
            node.value=value
            self.moveToHead(node)

    def addToHead(self,node): #加到头节点
        node.prev=self.head
        node.next=self.head.next
        self.head.next.prev=node
        self.head.next=node

    def removeNode(self,node): #删除节点
        node.prev.next=node.next #node的前个节点的下一个节点指针，指向node的下一个节点 
        node.next.prev=node.prev #node的下节点的前一个节点指针，指向node的前一个节点

    def removeTail(self): #删除尾节点前的节点
        node=self.tail.prev
        self.removeNode(node)
        return node

    def moveToHead(self,node): #移到头节点
        self.removeNode(node) #先删除
        self.addToHead(node) #后台添加



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

LRU缓存

Idea​

Idea