In this post, we will discuss some of the ways by which we can implement LRU cache. This post assumes that you have the basic knowledge of an LRU cache. So, we would focus on the implementation side. We will navigate from the laziest to the ideal approach to solve the problem in the context of an interview.

Using LinkedHashMap

We know that LRU requires ordering the elements in access order. So, we need a data structure that will enable us to maintain the access order. A cache demands get and put operations to be executed in constant time. We know that LinkedHashMap follows insertion order, but how to achieve access order ?

Fortunately, LinkedHashMap gives us the option to specify the access order in place of insertion order . So, the implementation would look like below:

class LRUCache<K,V>{
    int capacity;
    LinkedHashMap<K,V> data;

    public LRUCacheExamples(int capacity){
        this.capacity = capacity;
        this.data = new LinkedHashMap<>(capacity,0.8f,true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
}

The third argument in the LinkedHashMap constructor denotes the access order .
true indicates that we want to follow access order . It will follow the insertion order unless we specify it to true.

Note that, the elements will be ordered from least recently accessed to most recently accessed. For example, if we insert some dummy values to LinkedHashMap as below:

cache.put("abc", "abc");
cache.put("cde", "cde");
cache.put("efg", "efg");

Now, it will be in this order ->

abc -> abc, cde -> cde, efg -> efg

If we do cache.get("cde") or cache.put("cde", "someOtherValue")

then, the order will be (least recently to most recently used)->

abc -> abc, efg -> efg , cde -> someOtherValue

Also, note that we have overridden the method removeEldestEntry so that the cache automatically removes the eldest element (least recently used).

As you might guess, this is a pretty quick and laziest way to achieve LRU functionality. Do not mention this solution upfront in an actual interview unless the interviewer explicitly asks for a simple solution. In most cases, the interviewer would want you to design the data structure on your own.

Designing an LRU cache from scratch

Before we jump into the solution, let's re-iterate the requirements once:

-> get()/put() operations are expected to have constant runtime.
-> Space complexity should not exceed O(n) where n is the total number of elements in the cache. A cache has to be fast and space efficient as well.
-> Should be able to remove elements from the cache in constant time.

Both get() and put() operations would need to push the data to the front & cache should not evict the least recently used elements when the maximum capacity is exceeded.

We need to perform remove()/put() operations to ensure the access order. So, what is the data structure that can do insertion/removal in constant time? Yes, it is linked list:) Below is a simple class that can act as a data node in the linked list.

class Node<K,V>{
    K key;
    V data;
    Node<K,V> next;
    Node<K,V> prev;

    public Node(K key, V data){
        this.key = key;
        this.data = data;
    }
}

Now, there are multiple ways to store the node: for example, using a LinkedList or Deque from Java. The advantage is that we can make use of their readymade methods. That's up to the interviewer if he/she wants to do it that way. It is always better to expect the worst and prepare accordingly. So, be prepared to implement it from scratch.

Given the above Node class, we can go ahead and create the actual implementation for the cache. So, the implementation class would look like below:

public class LRUCache<K,V> {

    Node<K,V> head;
    Node<K,V> tail;
    Map<K,Node<K,V>> dataMap;
    int size;
    int max;

    public LRUCache(int max){
        dataMap = new HashMap<>();
        this.max = max;
    }
}

We use a Map to store the data and achieve constant runtime for get() operation. Other member variables are self-explanatory.

We need to add some helper functions first.

public int size() {
  return size;
}

public boolean isEmpty() {
  return size == 0;
}

public boolean canEvict() {
  return size == max;
}

private void moveToHead(Node < K, V > node) {
  node.prev = null;
  node.next = head;
  head.prev = node;
  head = head.prev;
}

The method moveToHead() will place the node in the head position (Note: node is not null).

Let's discuss the implementation of remove() first. Because we will be re-using it on multiple occasions to maintain access order. Take a look at the below code for remove() method:

public V remove(K key){

        if(head==null || tail==null){
            throw new RuntimeException("Cache is empty!");
        }

        Node<K,V> node = dataMap.remove(key);

        if(node == null){
            throw new RuntimeException("No mappings found!");
        }

        V value = node.data;


        if(node.prev != null){
            node.prev.next = node.next;
        }else{
            head = head.next;
        }


        if(node.next != null){
            node.next.prev = node.prev;
        }else{
            tail = tail.prev;
        }

        size--;
        return value;
}

If we need to remove a node which is head, then it means that node.prev is null.
So, we update the head -> head = head.next.

Similarly, if the node is tail, then it means that node.next is null. So, we update the tail -> tail = tail.prev.

Otherwise, we are sure that the node is an intermediate node. So, we made the adjustments accordingly. In the above implementation of remove(), we are making pointer adjustments only and thereby constant runtime.

Let's implement the evict functionality next. It is a requirement before we implement the put() method. Take a look at the below code for LRU eviction policy:

private void evict() {
  if (head == null || tail == null) {
    throw new RuntimeException("Cache is empty!");
  }
  remove(tail.key);
}

evict() is a private method since it is an internal decision to evict a cache. We just have to re-use the earlier discussed remove functionality. We remove the tail , because tail is the least recently used node among others.

Now that we implemented all the required methods, let's discuss the implementation of the put() method. Take a look at the below code:

public K put(K key, V value) {
  Node < K, V > current = dataMap.get(key);
  if (current != null) {
    current.data = value;
    if (current.prev != null) {
      current.prev.next = current.next;
      moveToHead(current);
    }
  } else {
    if (canEvict()) {
      evict();
    }
    current = new Node < K, V > (key, value);
    if (head == null || tail == null) {
      head = tail = current;
    } else {
      moveToHead(current);
    }
    size++;
  }
  dataMap.put(key, current);
  return key;
}

Let's dissect the code for more understanding. Consider the below block of code:

if (current != null) {
  current.data = value;
  if (current.prev != null) {
    current.prev.next = current.next;
    moveToHead(current);
  }
}

In the case of an existing key, we just need to move the data to the head position.
If the element is head itself, then we just have to update the value :)
In any other case, we make the adjustment current.prev.next = current.next; and move it to the head position.

Now onto the other case, where we add brand new data into the cache:

else {
  if (canEvict()) {
    evict();
  }
  current = new Node < K, V > (key, value);
  if (head == null || tail == null) {
    head = tail = current;
  } else {
    moveToHead(current);
  }
  size++;
}
dataMap.put(key,current);

Before we add data to the cache, we need to see if we exceed the maximum cache capacity. If yes, we need to evict first and then proceed. We move the data to the head position as well. Finally, we insert the data and increment size.

Finally, let's discuss the get() method implementation from the below code:

public V get(K key) {
  Node < K, V > node = dataMap.get(key);
  if (node == null) {
    throw new RuntimeException("No mappings found!");
  } else {
    if (node.prev != null) {
      node.prev.next = node.next;
      if (node.next != null) {
        node.next.prev = node.prev;
      } else {
        tail = tail.prev;
      }
      moveToHead(node);
    }
  }
  return node.data;
}

The node can be either head, tail or an intermediate node. If the key is corresponding to head node, then we don't have to adjust the pointers as the data is already at the head position. Note that node.prev is always null for a head node.
If the node is tail node, then we also need to update tail value. Finally, we move the node to the head position.

Further improvements to explore

• Supporting multi-thread environment: Making it thread-safe and concurrent data structure.

Hope this post is helpful and the full source code can be viewed here.