答案：结合哈希表和双向链表实现LRU缓存，哈希表支持O(1)查找，双向链表维护访问顺序，头结点为最近使用，尾结点为最久未使用；get操作查找不到返回-1，找到则移到头部并返回值；put操作若键存在则更新并移至头部，否则创建新节点插入头部，超容量时删除尾部节点；通过add_to_head、remove_node、move_to_head和pop_tail等辅助方法实现O(1)时间复杂度的插入、删除与移动操作，适用于页面置换、Redis及浏览器缓存等场景。
要实现一个支持LRU（Least Recently Used）缓存算法的数据结构，核心是结合哈希表和双向链表，以达到快速查找、插入、删除和维护访问顺序的目的。关键点在于：当缓存满时，淘汰最久未使用的数据；每次访问（get 或 put）某个键时，该键对应的数据要被移到最近使用的位置。
数据结构设计
使用以下两个组件组合：
哈希表（dict / map）：用于存储键到节点的映射，实现 O(1) 的查找时间。 双向链表：维护元素的访问顺序，头部为最近使用，尾部为最久未使用。
每个链表节点包含 key、value、prev 和 next 指针。
核心操作实现
需要支持 get 和 put 两个主要操作，并保证时间复杂度为 O(1)：
get(key)： 如果 key 不存在，返回 -1。 如果存在，将对应节点移到链表头部（表示最近使用），并返回 value。 put(key, value)： 如果 key 已存在，更新其 value 并移到头部。 如果 key 不存在，创建新节点插入头部。 插入后若超出容量，删除尾部节点（最久未使用）。
辅助方法：移动到头部与删除尾部
为了简化逻辑，可以封装几个工具函数：
add_to_head(node)：将节点插入双向链表头部。 remove_node(node)：从链表中移除指定节点。 move_to_head(node)：先删除再添加到头部。 pop_tail()：移除并返回尾部节点，用于淘汰。
这些操作通过调整 prev 和 next 指针完成，不涉及遍历，因此是 O(1)。
Python 示例代码
class ListNode: def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = Noneclass LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = ListNode() self.tail = ListNode() self.head.next = self.tail self.tail.prev = self.head def _add_to_head(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node): prev = node.prev nxt = node.next prev.next = nxt nxt.prev = prev def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _pop_tail(self): node = self.tail.prev self._remove_node(node) return node def get(self, key: int) -> int: node = self.cache.get(key) if not node: return -1 self._move_to_head(node) return node.val def put(self, key: int, value: int) -> None: node = self.cache.get(key) if node: node.val = value self._move_to_head(node) else: new_node = ListNode(key, value) self.cache[key] = new_node self._add_to_head(new_node) if len(self.cache) > self.capacity: tail = self._pop_tail() del self.cache[tail.key]
基本上就这些。这套实现确保了 get 和 put 都在常数时间内完成，符合 LRU 缓存的基本要求。实际应用中可用于页面置换、Redis 近似策略或浏览器缓存等场景。
以上就是如何实现一个支持LRU缓存算法的数据结构？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1524902.html
微信扫一扫 
支付宝扫一扫 
