class Node:
    """双向链表节点类
    
    用于在双向链表中存储键值对，并维护节点间的前后关系
    包含前驱和后继指针，方便在O(1)时间内删除和移动节点
    """
    def __init__(self, key=0, value=0):
        self.key = key            # 存储键，在删除最久未使用节点时需要用到
        self.value = value        # 存储值
        self.prev = None          # 前驱节点指针
        self.next = None          # 后继节点指针


class LRUCache:
    """LRU（最近最少使用）缓存实现类
    
    使用哈希表和双向链表的组合实现LRU缓存
    - 哈希表：实现O(1)时间的数据查找
    - 双向链表：实现O(1)时间的节点移动和删除
    """
    
    def __init__(self, capacity: int):
        """初始化LRU缓存
        
        Args:
            capacity: 缓存的最大容量
        
        创建：
        1. 头尾虚拟节点
        2. 哈希表
        3. 设置容量限制和当前大小
        """
        self.capacity = capacity              # 缓存容量
        self.size = 0                         # 当前缓存中的元素个数
        self.cache = {}                       # 哈希表，存储key到节点的映射
        
        # 创建虚拟的头尾节点，简化边界情况的处理
        self.head = Node()                    # 虚拟头节点，最近使用的节点之前
        self.tail = Node()                    # 虚拟尾节点，最久未使用的节点之后
        # 初始化时头尾节点相连
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove_node(self, node: Node) -> None:
        """从双向链表中删除一个节点
        
        Args:
            node: 要删除的节点
            
        原理：修改节点前后的指针指向，跳过当前节点
        [prev] <-> [node] <-> [next] 变成 [prev] <-> [next]
        """
        # 修改前后节点的指针，跳过当前节点
        node.prev.next = node.next            # 前一个节点的后继指向当前节点的后继
        node.next.prev = node.prev            # 后一个节点的前驱指向当前节点的前驱
    
    def _add_to_head(self, node: Node) -> None:
        """将节点添加到双向链表的头部
        
        Args:
            node: 要添加到头部的节点
            
        原理：在虚拟头节点后插入新节点
        [head] <-> [next] 变成 [head] <-> [node] <-> [next]
        """
        # 设置node的前后指针
        node.prev = self.head                 # node的前驱指向虚拟头节点
        node.next = self.head.next            # node的后继指向原来的第一个节点
        
        # 更新原来的节点指针
        self.head.next.prev = node            # 原来的第一个节点的前驱指向node
        self.head.next = node                 # 虚拟头节点的后继指向node
    
    def get(self, key: int) -> int:
        """获取缓存中key对应的值，并将节点移到链表头部
        
        Args:
            key: 要查找的键
            
        Returns:
            如果key存在，返回对应的值，并将节点移到头部（最近使用）
            如果key不存在，返回-1
        """
        # 如果key不在缓存中，返回-1
        if key not in self.cache:
            return -1
        
        # 如果key存在：
        node = self.cache[key]                # 1. 从哈希表中获取节点
        self._remove_node(node)               # 2. 从当前位置删除节点
        self._add_to_head(node)               # 3. 将节点添加到头部
        return node.value                     # 4. 返回节点的值
    
    def put(self, key: int, value: int) -> None:
        """向缓存中插入或更新值
        
        Args:
            key: 键
            value: 值
            
        如果key已存在：
            1. 更新值
            2. 将节点移到头部
        如果key不存在：
            1. 创建新节点
            2. 如果缓存满了，删除最久未使用的节点
            3. 将新节点添加到头部
        """
        # 如果key已经存在，更新值并移到头部
        if key in self.cache:
            node = self.cache[key]            # 1. 获取已存在的节点
            node.value = value                # 2. 更新节点的值
            self._remove_node(node)           # 3. 从当前位置删除节点
            self._add_to_head(node)           # 4. 将节点添加到头部
        else:
            # 如果key不存在，创建新节点
            node = Node(key, value)           # 1. 创建新节点
            self.cache[key] = node            # 2. 将节点添加到哈希表
            self._add_to_head(node)           # 3. 将节点添加到链表头部
            self.size += 1                    # 4. 增加缓存大小计数
            
            # 如果超出容量，删除最久未使用的节点（链表尾部的节点）
            if self.size > self.capacity:
                lru = self.tail.prev          # 1. 获取最久未使用的节点（尾部节点）
                self._remove_node(lru)        # 2. 从链表中删除该节点
                del self.cache[lru.key]       # 3. 从哈希表中删除该节点
                self.size -= 1                # 4. 减少缓存大小计数

# 使用示例
def example_usage():
    """LRU缓存使用示例"""
    # 创建容量为2的缓存
    cache = LRUCache(2)
    
    # 添加元素
    cache.put(1, 1)    # 缓存：[(1,1)]
    cache.put(2, 2)    # 缓存：[(2,2), (1,1)]
    
    # 访问元素
    print(cache.get(1))    # 返回1，缓存：[(1,1), (2,2)]
    
    # 添加新元素，导致淘汰最久未使用的元素
    cache.put(3, 3)    # 缓存：[(3,3), (1,1)]，2被淘汰
    
    # 尝试访问被淘汰的元素
    print(cache.get(2))    # 返回-1，因为2已被淘汰
    
    # 再次添加新元素
    cache.put(4, 4)    # 缓存：[(4,4), (3,3)]，1被淘汰
    
    # 验证最终状态
    print(cache.get(1))    # 返回-1，因为1已被淘汰
    print(cache.get(3))    # 返回3
    print(cache.get(4))    # 返回4

1. put(1,1)
哈希表：{1: Node(1,1)}
链表：head <-> [1,1] <-> tail

2. put(2,2)
哈希表：{1: Node(1,1), 2: Node(2,2)}
链表：head <-> [2,2] <-> [1,1] <-> tail

3. get(1)
哈希表：{1: Node(1,1), 2: Node(2,2)}
链表：head <-> [1,1] <-> [2,2] <-> tail

4. put(3,3)
删除最久未使用的2
哈希表：{1: Node(1,1), 3: Node(3,3)}
链表：head <-> [3,3] <-> [1,1] <-> tail

# 假设我们的书架最多能放2本书
cache = LRUCache(2)    # 创建一个容量为2的书架

# 放入新书
cache.put(1, 1)        # 放入第1本书
cache.put(2, 2)        # 放入第2本书
# 现在书架是：[最近] 2, 1 [最旧]

# 查找并使用某本书
cache.get(1)           # 查找并使用第1本书
# 因为使用了1，所以现在书架是：[最近] 1, 2 [最旧]

# 书架满了要放新书
cache.put(3, 3)        # 要放入第3本书
# 书架满了，需要移除最旧的2
# 现在书架是：[最近] 3, 1 [最旧]

# 用数组存储，但性能不好
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = []  # [(key, value), ...]
    
    def get(self, key):
        # 遍历数组找key，找到后移到最前面
        for i, (k, v) in enumerate(self.items):
            if k == key:
                self.items.pop(i)  # 删除当前位置
                self.items.insert(0, (k, v))  # 插入到最前面
                return v
        return -1

# 用哈希表提高查找速度，但仍需要记录顺序
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # {key: value}
        self.usage = []  # 记录使用顺序

# 组合使用两种数据结构
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}          # 快速查找
        self.head = Node()       # 双向链表头（最近）
        self.tail = Node()       # 双向链表尾（最久）
        self.head.next = self.tail
        self.tail.prev = self.head