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

class Node:  
    def __init__(self, key, value):  
        self.key = key  # 节点的键  
        self.value = value  # 节点的值  
        self.prev = None  # 指向前一个节点的指针  
        self.next = None  # 指向后一个节点的指针  
  
  
class Solution:  
    def __init__(self, capacity: int):  
        self.capacity = capacity  # 缓存的最大容量  
        self.cache = {}  # 哈希表，用于存储键到节点的映射  
        # 初始化双向链表的头尾节点，它们不存储实际数据  
        self.head = Node(0, 0)  
        self.tail = Node(0, 0)  
        self.head.next = self.tail  # 头节点指向尾节点  
        self.tail.prev = self.head  # 尾节点指回头节点  
  
    def get(self, key: int) -> int:  
        if key in self.cache:  
            node = self.cache[key]  # 从哈希表中获取节点  
            self._move_to_head(node)  # 将节点移动到双向链表的头部  
            return node.value  # 返回节点的值  
        return -1  # 如果键不存在，则返回-1  
  
    def set(self, key: int, value: int) -> None:  
        if key in self.cache:  
            node = self.cache[key]  # 从哈希表中获取节点  
            node.value = value  # 更新节点的值  
            self._move_to_head(node)  # 将节点移动到双向链表的头部  
        else:  
            if len(self.cache) == self.capacity:  
                self._remove_tail()  # 如果缓存已满，则移除双向链表的尾部节点  
            node = Node(key, value)  # 创建一个新的节点  
            self.cache[key] = node  # 将节点添加到哈希表中  
            self._add_to_head(node)  # 将节点添加到双向链表的头部  
  
    def _move_to_head(self, node):  
        self._remove_node(node)  # 从双向链表中移除节点  
        self._add_to_head(node)  # 将节点添加到双向链表的头部  
  
    def _remove_node(self, node):  
        prev = node.prev  # 获取节点的前一个节点  
        next = node.next  # 获取节点的后一个节点  
        prev.next = next  # 将前一个节点的next指针指向后一个节点  
        next.prev = prev  # 将后一个节点的prev指针指向前一个节点  
  
    def _add_to_head(self, node):  
        node.prev = self.head  # 将节点的prev指针指向头节点  
        node.next = self.head.next  # 将节点的next指针指向头节点的下一个节点  
        self.head.next.prev = node  # 将头节点的下一个节点的prev指针指向新节点  
        self.head.next = node  # 将头节点的next指针指向新节点  
  
    def _remove_tail(self):  
        tail = self.tail.prev  # 获取尾节点的前一个节点，即要移除的节点  
        self._remove_node(tail)  # 从双向链表中移除该节点  
        del self.cache[tail.key]  # 从哈希表中删除该节点的键