LRU Cache (Part II- implementation)
Introduction
We have already discussed how LRU cache works internally and its use cases in the previous blog . In this blog we will mainly focus on implementation details for LRU cache. I strongly recommend to read previous article if you need wide explanation about LRU cache internal working mechanism. We will use Java programming language for our implementation.
LRUCache Implementation
We need to implement functionalities in the below.
// Calling this constructor will initialize our cache with given capacity.
public LRUCache(int capacity)
// Returns the value of the key if the key exists, otherwise returns null
// time complexity is O(1)
public Emoji get(int key)
// Updates the value of the key if the key exists. Otherwise, add the key-value pair to the cache.
// If the number of keys exceeds the capacity from this operation, least recently used key will be evicted
// time complexity is O(1)
void put(int key, Emoji value)Create class which we want to cache. You can create and cache any Object, for simplicity I will create Emoji.java file with minimal properties
public class Emoji {
private String unicode;
private String name;
private String category;
public Emoji(String unicode){
this.unicode = unicode;
}
//other constructors ...
//getter, setters ...
}Next step is to create LRUCache class which it will be main class and keep our cache. That class will hold 3 main instance variables. 1st property in type of LinkedList , 2nd property in type of HashMap, 3rd property in type of int to store cache capacity. Principally you can either embed LinkedList(Node logic) implementation to LRU cache class or you can implement separately. In this example I will embed Node class implementation logic inside LRUCache class.
LRUCache class structure looks like this
class LRUCache {
public static class Node {
private Emoji value;
private final int key;
private Node next;
private Node prev;
public Node(int key, Emoji value){
this.key = key;
this.value = value;
}
}
private final Node head;
private final Node tail;
private final Map<Integer, Node> map;
private final int capacity;
public LRUCache(int capacity) {
if (capacity < 1){
throw new IllegalArgumentException("cache capacity can't be less than 1");
}
this.capacity = capacity;
//initialize others with defaults
this.map = new HashMap<>();
//in order not deal with edge cases, it is recommended that
//initialize your head and tail nodes with null values
this.head = new Node(-1, null);
this.tail = new Node(-1, null);
head.next = tail;
tail.prev = head;
}
//implement methods here
}Emoji get(int key) — this method
If the given key exists then - this method
- removes current node from current position
- adds that node to head of LinkedList
- returns value
otherwise returns null.
public Emoji get(int key) {
Node node = map.get(key);
if(node == null) return null;
//remove key
removeNode(node);
//add that node to head of list
addNode(node, head);
return node.value;
}
private void removeNode(Node node){
//remove current node from linked list
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
private void addNode(Node curr, Node before){
Node after = before.next;
before.next = curr;
curr.next = after;
after.prev = curr;
curr.prev = before;
}public void put(int key, Emoji value) — this method
If the given key exists then — this method
- updates value in the node
- removes node from current position
- adds that node to head of LinkedList
- updates value in the map
otherwise
- creates new node and adds that node to head of linked list
- puts key value pair to the map
- checks map’s size if size exceeds capacity deletes tail node from LinkedList
public void put(int key, Emoji value) {
Node node = map.get(key);
if (node != null){
//update value of existing key
update(node, value);
}else {
//add key value
add(key, value);
}
}
private void update(Node node, Emoji newValue){
//update value in the node
node.value = newValue;
//remove node
removeNode(node);
//add node to the head
addNode(node, head);
//update value in the map
map.put(node.key, node);
}
private void add(int key, Emoji value){
Node curr = new Node(key, value);
//add node to the head of list
addNode(curr, head);
//put key-value pair to map
map.put(key, curr);
//check map size exceeds predefined capacity
if(map.size() > capacity){
//evict the least recently used key
evict();
}
}
private void evict(){
//remove tail node(as we keep always tail and head nodes stable,
//therefore we will remove prev node of tailNode)
remove(tail.prev);
}
private void remove(Node node){
//remove current node value from map
map.remove(node.key);
//remove current node from linked list
removeNode(node);
}
private void removeNode(Node node){
//remove current node from linked list
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}Thank you for taking the time to read my articles! If you’d like to access the complete code you can checkout out this repository . Happy coding! 📚👩💻 .
If you find this article helpful for you , your support such as like, comment, sharing like rocket fuel for my technology passion. It motivates me to dive deeper into the tech world and deliver more content that matters to you.
If you’re looking to offer more support, consider buying me a coffee ☕ and I’ll transform that caffeine boost into lines of code and tech insights. Your coffee becomes the code that powers our tech journey. 💻🚀 https://www.buymeacoffee.com/mayilb95
Let’s connect in Linkedin Mayil-Bayramov
