🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will design and implement a data structure for a Least Recently Used (LRU) cache in Java. An LRU cache is a popular caching algorithm that removes the least recently used item when the cache reaches its capacity.
Problem
Design an LRU Cache that supports two operations: get(key) to retrieve a value and put(key, value) to set or insert a value. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.
2. Solution Steps
1. Use a HashMap for constant-time lookups and a Doubly Linked List to maintain insertion order.
2. For get(key), if the key is present in the cache, move the corresponding node to the front of the list (most recently used).
3. For put(key, value), insert the new node at the front of the list. If the cache is at capacity, remove the node at the end of the list (least recently used) before inserting a new one.
4. Ensure constant time operations for both get and put.
3. Code Program
import java.util.HashMap;
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
// Always add the new node right after head
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node){
// Remove an existing node from the linked list
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node){
// Move certain node in between to the head
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
// Pop the current tail
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
// Move the accessed node to the head
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
size++;
if(size > capacity) {
// Pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
size--;
}
} else {
// Update the value
node.value = value;
moveToHead(node);
}
}
}
// Main method for testing
public class Main {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(5, 7);
cache.put(8, 20);
System.out.println("Get 5: " + cache.get(5)); // returns 7
cache.put(3, 6); // evicts key 8
System.out.println("Get 8: " + cache.get(8)); // returns -1 (not found)
cache.put(4, 12); // evicts key 5
System.out.println("Get 5: " + cache.get(5)); // returns -1 (not found)
System.out.println("Get 3: " + cache.get(3)); // returns 6
System.out.println("Get 4: " + cache.get(4)); // returns 12
}
}
Output:
Get 5: 7 Get 8: -1 Get 5: -1 Get 3: 6 Get 4: 12
Explanation:
The LRU cache is designed with a capacity of 2.
When we put keys 5 and 8, they are stored in the cache.
A get(5) returns 7. Then, putting key 3 causes key 8 to be evicted (as it's the least recently used), making a get(8) return -1.
Similarly, putting key 4 evicts key 5, making a get(5) return -1.
Finally, get(3) and get(4) return 6 and 12, respectively, as they are present in the cache.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment