LRU Cache

Introduction

In this article, we will go over LRU in depth. These topics will be covered in the post.

  • Useful scenarios
  • Problems and how LRU could be used
  • How does LRU work?
  • Implementation of LRU

Useful scenarios

When you visit a domain you are essentially making a request to the server to send you the resources such as Html file, CSS file, Javascript file, images, videos, etc. To speed up the process the server maintains the most used resources into the cache. Another example of optimization could be your cell phone. Most of the popular mobile OS such as android saves the state of the application you are using into the ram after exiting. If the user decides to relaunch the application it’s much faster.

Problem and how LRU could be used

The problem with using cache or ram is that the memory is limited and we need to remove/evict the resources that are not frequently used by the user. We need some set of rules for the eviction of these unused resources. This is where the LRU comes into play. LRU stands for the least recently used. It’s an eviction policy to remove unused programs/files from memory to save space. If you like the following article I would suggest you to subscribe to my blogs.

How does LRU work?

LRU has a fixed capacity and supports two operations get(key) and put(key, value). The get operation checks whether the value is already present in the cache. If the value is present in the cache it accesses the element and puts it in front since it was the most recently accessed. The put operation checks the capacity of the LRU and if it’s already full then evicts the least recently used value and puts the new node in front.

The first step would be to define a node representation of doubly linked list.
The second step is to create an LRUCache class. Initialize it with a fixed capacity provided by the user. Create an empty hashmap and two nodes head and tail. Head should be pointing to tail and tail should be pointing to head.
The third step would be to create some helper functions. Removing a node from the doubly linked list and Inserting the node in front of the list.
The fourth step would be to support get operation. We check for the key in the hashmap. If the key is present call our helper methods remove node and add it to the front of the list. If the key is not present in the hashmap then we simply return -1.

The fifth step would be to support the put operation. We check if the key we are trying to insert is already present in the hashmap.

  • If yes then remove the node, update the node and insert it to the front.
  • If the key is not already present then check the capacity. If the capacity is 0 then we need to evict the least recently used node. Then simply insert the key to the front.

Entire implementation

The entire implementation of LRU cache could be found here

If you like the content please subscribe, like and share the post. Also don’t forget to connect with me online! Happy Coding:)