LRU Cache

Problem Statement

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

Approach

To design Cache, we need 2 data structures:

  • HashMap or HashTable acts as a cache that can perform a quick lookup. It contains the mapping of <Integer, Node> where the integer is the key and the Node is a linked list node. Remember that we are maintaining the node in the cache so that we could eliminate linear search in a linked list and the node could be accessed in O(1) .
  • A Queue/linked list to maintain the ordering in which elements are accessed . Each node has a key,value,next & previous.New nodes will be added to the end and as capacity reaches its threshold, the first node from this queue is removed to make space for new entry. We shall be doing so because, the first node in this queue is Least Recently Used and is unlikely to be used in the near future.

How get(key) works?

  • If the cache contains this key
  • Get the node from the cache.
  • Now this node is recently accessed, we will delete the existing node from the queue and add it to the end.
  • Return the value of this key from the cache.
  • If cache does not contain this key, then return -1

How set(key,value) works?

There are 3 cases to consider in this:

Case1:

  • If cache already contains this key:
  • Create a new node using the key and value;
  • Get the old node from the cache for this key.
  • Delete it from the queue.
  • Add new node to the end of the queue. This is because it is recently accessed.
  • Update the cache with the new node (value for the existing key).

Case2:

  • If the capacity of the cache is > 0 i.e (cache is still not full)
  • Create a new node using the key and value
  • Store in the cache.
  • Add the new node to the end of the queue.

Case3:

  • If the capacity is full
  • Get the first element in the queue. This is the least recently used element
  • Remove this element from the cache.
  • Create a new node using the given key and value.
  • Add to cache the key and the new node.
  • Add the new node to the end of the queue.

Runtime Complexity

get(key): This is an O(1) operation because the cache is HashMap and the lookup is fast

set(key): This is also O(1). We have access to the node directly and we are only manipulating the pointers.

Code

public class LRUCache {
private Map<Integer,Node> cache = new HashMap<Integer,Node>();
private LinkedList queue = new LinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key){
if(cache.containsKey(key)){
Node node = cache.get(key);
queue.deleteNode(node);
queue.add(node);
return cache.get(key).value;
}return -1;
}
public void set(int key, int value){
Node node = new Node(key,value);
if(cache.containsKey(key)){
queue.deleteNode(cache.get(key));
cache.put(key,node);
queue.add(node);
}
else if(capacity > 0){
cache.put(key, node);
queue.add(node);
capacity--;
}else{
cacheReSize();
cache.put(key,node);
queue.add(node);
}
}
private void cacheReSize(){
cache.remove(queue.getHead().key);
queue.removeFromHead();
}
private class Node{
Node next;
Node previous;
int value;
int key;

public Node(int key,int val){
this.key = key;
this.value = val;
}}
private class LinkedList{
private Node head;
private Node tail;

public void add(Node node){
if (head == null){
head = node;
tail = node;
}else{
tail.next = node;
node.previous = tail;
tail = node;
}}



public void deleteNode(Node node){
if(node == head){
removeFromHead();
return;
}
if(node == tail){
Node previous = tail.previous;
previous.next = null;
tail = previous;
return;
}
Node nextNode = node.next;
Node previousNode = node.previous;
previousNode.next = nextNode;
nextNode.previous = previousNode;
}

public void removeFromHead(){
if(head.next != null){
head = head.next;
head.previous = null;
}else{
head = null;}

}

public Node getHead(){return this.head;}
}
}