JavaScript实现LeetCode第146题:LRU缓存机制[1]
题目描述
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制[2]。...当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。...解题步骤:
使用Map记录缓存值,使用链表记录缓存操作顺序,最后操作的缓存放在链表头部,链表尾部就是最少操作的缓存
读取缓存时,更新缓存操作顺序,将缓存节点从链表中移除, 再将其添加到链表头部, 移除节点时要保证链表的连续性...,为了在 O(1)时间完成该操作,需要使用双向链表
设置缓存时
如果是已存在的缓存,则直接更新缓存值即可,并更新缓存操作的顺序;
如果是不存在的缓存,则将缓存加到链表头部, 添加后如果缓存超出上限, 则将链表尾部的缓存清掉...参考资料
[1]LRU缓存机制: https://leetcode-cn.com/problems/lru-cache/
[2]LRU (最近最少使用) 缓存机制: https://baike.baidu.com