题解 | #设计LRU缓存结构#

class Node:
    def __init__(self,key ,value):
        self.pre = None
        self.next = None
        self.key = key
        self.val = value

class Solution:
    def __init__(self, capacity: int):
        # 构建双向链表
        self.size = 0
        self.maxsize = capacity
        self.head = None
        # 记录key
        self.mp =dict()
    # 定义一个遍历 链表的函数
    def broad_node(self,head :Node):
        cur = head
        while cur is not None:
            print(f'key:{cur.key},value:{cur.val}')
            cur = cur.next

    # 指定节点移到表头的操作
    def move_head(self,node):
        cur = self.head
        while cur is not None :
            if cur.key == node.key :
                #找到此节点，断开,需要注意特殊情况，如果是表头不用动
                if cur == self.head :
                    return
                cur.pre.next = cur.next
                if cur.next :
                    cur.next.pre = cur.pre
                # 把该节点加到表头
                node.next = self.head
                self.head.pre = node
                self.head = node
            cur = cur.next
        return

    # 定义一个删除尾节点 函数 ,这个函数相对于删除指定节点要简单很多
    def del_tail(self):
        #找到尾节点
        cur = self.head
        while cur.next is not None :
            cur = cur.next
        # 如果这个限制长度是1 ，那直接初始化头结点即可
        if cur == self.head :
            self.head = None
        else :
            cur.pre.next = None
        # 哈希表 里面也别忘了删除键值对
        self.mp.pop(cur.key)

    # 定义一个插入节点函数
    def insert_node(self ,node):
        if self.head is None:
            self.head = node
        else:
            #插入表头 这个项目只需要插入表头即可
            node.next = self.head
            self.head.pre = node
            self.head = node
        # 哈市表也别忘了添加
        self.mp[node.key] = node.val

    def get(self, key: int) -> int:
        if key in self.mp.keys() :
            node_tem =Node(key,self.mp[key])
            self.move_head(node_tem)
            return self.mp[key]
        else:
            return -1

    def set(self, key: int, value: int) -> None:
        if key in self.mp.keys() :
            self.mp[key] = value
            node_tem = Node(key ,value)
            self.move_head(node_tem)
        else:
            #这种情况要判断长度是否超过了
            if self.size >= self.maxsize :
                self.del_tail()
                self.size -= 1
            node = Node(key, value)
            self.insert_node(node)
            self.size += 1