数据结构与算法：手写 LRU 缓存
本文由一缘原创整理，系统梳理 LRU 缓存的原理与手写实现，适合所有算法/后端/前端进阶开发者。
数据结构与算法：手写 LRU 缓存 LRU（Least Recently Used）缓存是高频面试题，也是高性能系统常用的数据结构。
1. LRU 缓存原理 最近最少使用，淘汰最久未访问的数据 需支持 O(1) 的 get/set 操作 常用双向链表 + 哈希表实现 2. 设计思路 哈希表存 key 到节点的映射，O(1) 查找 双向链表维护访问顺序，头部是最新，尾部是最旧 get 时把节点移到头部，set 时插入头部，超容量时移除尾部 3. 手写 LRU 缓存（Python 版） class Node: def __init__(self, key, val): self.key = key self.val = val self.prev = self.next = None class LRUCache: def __init__(self, capacity): self.cap = capacity self.map = {} self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def get(self, key): if key not in self.map: return -1 node = self.map[key] self._remove(node) self._add(node) return node.val def put(self, key, val): if key in self.map: self._remove(self.map[key]) node = Node(key, val) self._add(node) self.map[key] = node if len(self.map) > self.cap: n = self.tail.prev self._remove(n) del self.map[n.key] def _remove(self, node): p, n = node.prev, node.next p.next = n n.prev = p def _add(self, node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node # 测试 lru = LRUCache(2) lru.put(1, 1) lru.put(2, 2) print(lru.get(1)) # 1 lru.put(3, 3) print(lru.get(2)) # -1 lru.put(4, 4) print(lru.get(1)) # -1 print(lru.get(3)) # 3 print(lru.get(4)) # 4 输出：
