0146. LRU Cache¶
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
Follow up:
Could you do get and put in O(1) time complexity?
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- At most
3 * 104calls will be made togetandput.
double linked list with map (java)¶
import java.util.Hashtable;
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode post;
}
/**
* Always add the new node right after head;
*/
/* before:
node.pre - node - node.post
head - head.post (tail)
after:
head - node - head.post (tail)
*/
private void addNode(DLinkedNode node) {
node.pre = head;
node.post = head.post;
head.post.pre = node;
head.post = node;
}
/**
* Remove an existing node from the linked list.
*/
// pre - node - post -> pre - post
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;
pre.post = post;
post.pre = pre;
}
/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node){
this.removeNode(node);
this.addNode(node); // head->post now point to node
}
// pop the current tail.
private DLinkedNode popTail(){
DLinkedNode res = tail.pre;
this.removeNode(res); //
return res;
}
private Hashtable<Integer, DLinkedNode> cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;
// head.pre (null) - head - head.post (tail)
// tail.pre (head) - tail - tail.post (null)
// -> head.pre (null) - head - tail - tail.post (null)
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if(node == null){
return -1; // should raise exception here.
}
// move the accessed node to the head;
this.moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null){ // need to insert new key-value pair into the list
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++count; // same as the size of cache.size()
if(count > capacity){
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
}else{ // just swap to the head and update value
node.value = value;
this.moveToHead(node);
}
}
}
why bother doubly linked list¶
Fast removal. Doubly linked lists let us remove and insert in constant time if we have access to a node directly. The hashtable gives us access to a node directly.
If we use a singly linked list we will need to spend O(n) time to remove a node even if we have direct reference to the node that needs to get removed. (This is because to remove in a singly linked list we need to point nodeToDelete's previous node to nodeToDelete's next node. Finding nodeToDelete's previous is expensive if nodeToDelete is the last node in the list.)
why cannot be converted to a singly linked list in Java¶
People who are wondering why we have a double-linked list here instead of a single-linked linked list :
Yes, the purpose can be achieved with a single-linked LL with some hacks but NOT in java. Let's say I've to remove node n and its previous node is p. If n is the last node in the list, I've to modify the next field of p to point to null. This can't be done if I don't have access to p.next since in java, method parameters are actually references of the objects and they are passed by value. So, let's say right now, n and p.next point to the same object (i.e. n of course). If I do n=null, that doesn't make the object null. The object is still there and p.next points to that object. The only diff is that now n doesn't point to that object. In fact, it doesn't point to anything.
n=null doesn't remove n, but just send what it points-to to null
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
if tail.pre is always pointing to head, and head.post always points to tail
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;
pre.post = post;
post.pre = pre;
}
cpp¶
class LRUCache {
struct Node {
int key, val;
Node *next, *pre;
Node(int key, int val)
: key(key)
, val(val)
{
}
};
private:
unordered_map<int, Node*> map;
int cap;
Node *head, *tail;
public:
LRUCache(int capacity)
{
cap = capacity;
head = NULL, tail = NULL;
}
int get(int key)
{
if (!map.count(key))
return -1;
Node* node = map[key];
if (node != tail) {
if (node == head) {
head = head->next; // leave space for head to move node to the back
} else { // pre <-> node <-> next => pre <-> next
node->pre->next = node->next;
node->next->pre = node->pre;
}
tail->next = node; // now tail points to the latest node
node->pre = tail;
node->next = NULL;
tail = node;
}
return node->val;
}
void put(int key, int value)
{
// exist
if (map.count(key)) {
Node* node = map[key];
node->val = value; // update value
if (node != tail) { // here are the same logic as in get()
if (node == head) { // head now points to the second recent used node
head = head->next;
} else {// split out node, now node.pre - node.next
node->pre->next = node->next;
node->next->pre = node->pre;
}
tail->next = node;
node->pre = tail;
node->next = NULL;
tail = node;
}
} else { // not exit
Node* newNode = new Node(key, value);
if (cap == 0) { // cap == capacity - map.size()
Node* temp = head;
head = head->next; // always remove the least recent used node
map.erase(temp->key);
cap++;
}
// what could happen after removal?
if (head == NULL && tail == NULL) {
head = newNode;
} else { // let tail point to the newly inserted node
tail->next = newNode;
newNode->pre = tail;
newNode->next = NULL;
}
tail = newNode;
map[key] = newNode;
cap--;
}
}
};
/**
* 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);
*/
- head: least recent used node
- tail: most recent used node