How to Design a simple LRU cache in Java

How to Design a simple LRU cache in Java

LRU  

Design and implement a data structure for Least Recently Used (LRU) cache by supporting set() and get() operations with O(1) complexity. 

Least Recently Used (LRU) Cache?

Its a caching mechanism where we evicts least recently used items from the cache to accommodate new entries at top. So in that case in cache we maintain only the recently used data and least used entries will be evicted once we need to set new value in cache. 

How to implement simple LRU Cache?

We can implement by using multiple data structure like stack, Queue, LinkedList etc., 
Now in this tutorial lets see how to implement by using Doubly LinkedList and map to hold the LinkedList nodes which makes O(1) complexity for our read / get() operation.

Steps:

• NodeLRU class which holds the data, next and previous node values.
• In LRUCache setting cache size as 5 to make it simple 
• set() method will check already value present in map or not. If its present remove the existing value from map and LinkedList and add the new value in LinkedList and map.
• get() method will fetch node if present in map and return the values or else return -1 if not present. 
• Once we get the value the node will be shifted to the head of LinkedList to make it as recently used. 

By this way we can implement the LRU cache with simple logic by using LinkedList and map. Lets see the java implementation for the same

import java.util.HashMap;
import java.util.Map.Entry;

/*
 * LinkedList node to hold the cached data
 */
class NodeLRU {
 int data;
 NodeLRU next;
 NodeLRU previous;

 public NodeLRU(int data) {
  this.data = data;
  this.next = null;
  this.previous = null;
 }
}

/**
 * Implementing LRU Cache using LinkedList and HashMap to get() value with O(1) 
 * time complexity.
 */
class LRUCache {

 // Total cache size 
 private final static int CACHE_SIZE = 5;

 // Map to hold the cached nodes
 private HashMap<Integer, NodeLRU> map = new HashMap<Integer, NodeLRU>(CACHE_SIZE);
 
 // Doubly LinkedList head and tail node pointer
 private NodeLRU head = null;
 private NodeLRU tail = null;

 /*
  * Set method which will add data into LinkedList
  * and if already key present then remove and ADD as new element.
  */
 public void set(int key, int val) {
  if (map.containsKey(key)) {
   removeExistingNode(key, val);
   set(key, val);
  } else {
   addNode(key, val);
  }
 }

 /*
  * Get method which will return node data if present
  * else returns -1. Once if data node present in map then
  * Fetch the node and place it @ head location. 
  */
 public int get(int key) {
  if (map.containsKey(key)) {
   NodeLRU node = map.get(key);
   makeAsRecentUsed(node);
   return node.data;
  }
  return -1;
 }
 
 /*
  * One if node present via get() method then 
  * pick out the node and stitch with head location as first node.
  * 
  */
 private void makeAsRecentUsed(NodeLRU node) {
  if (node.equals(head)) {
   return;
  } else if (node.equals(tail)) {
   tail.previous.next = null;
   tail = tail.previous;
  } else {
   node.previous.next = node.next;
   node.next.previous = node.previous;
  }
  node.previous = null;
  node.next = head;
  head.previous = node;
  head = node;
 }

 /*
  * Delete the least used node frm LinkedList and map
  */
 private void removeExistingNode(int key, int val) {
  NodeLRU tmp = map.get(key);
  if (tmp.next != null && tmp.previous != null) {
   tmp.previous.next = tmp.next;
   tmp.next.previous = tmp.previous;
  } else if (tmp.equals(tail)) {
   removeLeastUsed();
  } else if (tmp.equals(head)) {
   removeHeadNode();
  }
 }

 /*
  * Removing 1st node
  */
 private void removeHeadNode() {
  NodeLRU firstNode = head;
  tail = tail.next;
  tail.previous = null;
  removeFromMap(firstNode);
 }
 
 /*
  * Adding new node to LinkedList
  */
 private void addNode(int key, int val) {
  if (map.size() < CACHE_SIZE) {
   NodeLRU tmp = new NodeLRU(val);
   if (head == null && tail == null) {
    head = tail = tmp;
   } else {
    head.previous = tmp;
    tmp.next = head;
    head = tmp;
   }
   map.put(key, tmp);
  } else {
   removeLeastUsed();
   addNode(key, val);
  }
 }

 /*
  * Removing least/ last node from LinkedList
  */
 private void removeLeastUsed() {
  NodeLRU leastUsed = tail;
  tail = tail.previous;
  tail.next = null;
  removeFromMap(leastUsed);
 }

 /*
  * Removing from map also based on value node
  */
 private void removeFromMap(NodeLRU node) {
  for (Entry<Integer, NodeLRU> entry : map.entrySet()) {
   if (entry.getValue().equals(node)) {
    map.remove(entry.getKey());
    return;
   }
  }
 }

 /*
  * Method to print all LinkedList nodes data
  */
 public void printValueFromCache() {
  NodeLRU tmp = head;
  System.out.print("CACHE VALUES : ");
  while (tmp != null) {
   System.out.print(tmp.data + ", ");
   tmp = tmp.next;
  }
  System.out.println();
 }

 public static void main(String[] args) {

  LRUCache obj = new LRUCache();
  
  // Adding 1 to 5 values to cache
  obj.set(1, 11);
  obj.set(2, 12);
  obj.set(3, 13);
  obj.set(4, 14);
  obj.set(5, 15);

  obj.printValueFromCache();
  
  /*
   *  Reading value with key (1) which we adding 1st and
   *  placed last in LL. Once we read same value (Node) should 
   *  be placed as recent and moved to top of linked List.
   */
  
  int val = obj.get(1);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();
  
  /*
   * Adding some more values to Cache. Since we set cache size as 5
   * least used 3 nodes like (2,3,4) need to removed and (6,7,8)
   * values need to added to linked list 
   */
  obj.set(6, 66);
  obj.set(7, 77);
  obj.set(8, 88);

  obj.printValueFromCache();
  
  /*
   * Reading again with key (5) which makes node to shift to head
   * which will be recently used
   */
  val = obj.get(5);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();

 }
}

OUTPUT:

CACHE VALUES : 15, 14, 13, 12, 11, 
READ VALUE : 11
CACHE VALUES : 11, 15, 14, 13, 12, 
CACHE VALUES : 88, 77, 66, 11, 15, 
READ VALUE : 15
CACHE VALUES : 15, 88, 77, 66, 11,