leetcode刷题_PYTHON(16):链表(16) LRU 缓存机制

class double_linked_list_node:
    def __init__(self, key = 0, val = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
    
class double_linked_list:
    def __init__(self):
        self.head = double_linked_list_node()
        self.tail = double_linked_list_node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_end(self, p: double_linked_list_node) -> None:
        #----先把p点摘下来
        p.prev.next = p.next
        p.next.prev = p.prev
        #----放到最后
        p.next = self.tail
        p.prev = self.tail.prev
        self.tail.prev.next = p
        self.tail.prev = p

    def append_to_end(self, key: int, value: int) -> None:
        p = double_linked_list_node(key, value)
        p.next = self.tail
        p.prev = self.tail.prev
        self.tail.prev.next = p
        self.tail.prev = p

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dl = double_linked_list()
        self.key_dl_node = dict()

    def get(self, key: int) -> int:
        if key not in self.key_dl_node:
            return -1
        node = self.key_dl_node[key]
        self.dl.move_to_end(node)
        return node.val       

    def put(self, key: int, value: int) -> None:
        if key in self.key_dl_node:
            node = self.key_dl_node[key]
            node.val = value
            self.dl.move_to_end(node)
            return 

        self.dl.append_to_end(key, value)
        self.key_dl_node[key] = self.dl.tail.prev

        if len(self.key_dl_node) > self.capacity:
            p = self.dl.head.next
            self.dl.head.next = p.next
            p.next.prev = self.dl.head
            del self.key_dl_node[p.key]


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

作者：Hanxin_Hanxin
链接：https://leetcode-cn.com/problems/lru-cache/solution/cpython3java-1ordereddictlistlinkedhashm-3ij8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。