Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return-1.
put(key, value)- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
思路
双向链表(Doubly Linked List) + HashMap
HashMap： key，value（ListNode）
LinkedList: 存的是按照访问节点的时间顺序排列的ListNode
- LRU的实质是按照节点访问时间顺序排列的双向链表。每个双向链表节点有prev和next指向其一前一后的节点。
- 最近被访问的节点放置在链表头部。一旦链表达到容量，需要剔除元素的时候，踢出链表尾部的最老时间被访问过的元素。
- HashMap则是用来根据key来找对应的链表节点。
Note：
- set时，如果该key存在，那么也说明它也是被最近访问过，也需要将其移动到链表最头上。
- get时，变到最前端的方法是先删除这个最后的节点，再将其放到最前端。分两步操作
class LRUCache {
private class ListNode {
int key;
int value;
ListNode prev;
ListNode next;
public ListNode(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, ListNode> mapping;
private ListNode head;
private ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.mapping = new HashMap<Integer, ListNode>();
this.head = new ListNode(-1, -1);
this.tail = new ListNode(-1, -1);
head.next = tail;
tail.next = head;
}
public int get(int key) {
//get说明最新访问了它，那么需要将这个节点移动到链表最前端，保证是最新访问过的
if (!mapping.containsKey(key)){
return -1;
}
ListNode cur = mapping.get(key);
//变到最前端的方法是先删除这个最后的节点，再将其放到最前端。分两步操作
removeNodeAtEnd(cur);
moveToHead(cur);
return cur.value;
}
public void put(int key, int value) {
//如果在put的时候发现是有这个node，1. 表示最新访问了，那么在get（）中已经将其移动到了最前端
// 同时，需要更新其value
if (get(key) != -1) {
mapping.get(key).value = value;
return;
}
//如果put的时候发现cache已满，那么则需要删除链表中最后的那个节点，同时删除掉hashmap中对应的那个NODE
if (mapping.size() == capacity) {
//顺序不能错，如果先删除了节点，那么在mapping中找tail.prev就会找错
mapping.remove(tail.prev.key);
removeNodeAtEnd(tail.prev);
}
//上面操作保证了put的时候，不会出现超过容量的现象
ListNode newNode = new ListNode(key, value);
moveToHead(newNode);
mapping.put(key, newNode);
}
public void moveToHead(ListNode cur) {
cur.next = head.next;
head.next.prev = cur;
head.next = cur;
cur.prev = head;
}
public void removeNodeAtEnd(ListNode cur) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
