Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

LRU Cache Implementation (C++, Java, Python)

Jatin Chanana by Jatin Chanana
December 17, 2023
Reading Time: 9 mins read
LRU Cache Implementation
Follow us on Google News   Subscribe to our newsletter

In the domain of computer science and data management, efficient caching mechanisms play an important role in enhancing system performance. One of the cache replacement policies is the least recently used algorithm. In this article, we will discuss the fundamentals of the LRU cache problem from leetcode, exploring its concept, and the queue hashing approach with solution.

What is LRU Cache Implementation?

LRU, or Least Recently Used, is a caching strategy where the system keeps track of the usage history of cached elements and discards the least recently used item when the cache reaches its capacity. This strategy ensures that the most recently used items are retained, optimizing cache utilization and improving overall performance. 

Let’s discuss how we can implement LRU Cache!

Using Queue and Hashing Approach

The Queue Hashing Approach is a common method for implementing LRU cache. It combines the efficiency of a queue for tracking usage history and a hashmap for quick lookups. The queue maintains the order of element access, and the hash map facilitates fast retrieval of elements.

The Data Structures used in this approach:

  • Queue: We will maintain a queue to represent the order of access. When an element is accessed or inserted, it is moved to the front of the queue.
  • Hash Map: Utilize a hashmap to store the elements along with their corresponding positions in the queue.

The functions to be implemented in this problem:

  • Firstly we will declare a member variable in a private class
    • capacity: This indicates the maximum number of elements the cache can hold.
    • cacheMap: An unordered map that stores the key-value pairs along with iterators pointing to their positions in the cacheList.
    • cacheList: A doubly-linked list that maintains the order of element access.
  • LRUCache(int capacity): Initialize the LRU cache with positive size capacity.
  • int get(int key): Return the value of the key if the key exists, otherwise, return -1.
    • The get function checks if the key is present in the cache. If it’s not found, it returns -1. If the key is found, it moves the corresponding element to the front of the cache list using the splice function and returns the value associated with the key.
  • void put(int key, int value): Update 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, evict the least recently used key.
    • The put function handles inserting a new element or updating an existing one. If the key is already present, it updates the value and moves the element to the front of the cache list. 
    • If the key is not present, it inserts the new element at the front. If the cache is at full capacity, it removes the least recently used element from both the cacheList and cacheMap.

Let’s consider an example:

Input = [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]

Output = [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Here is an explanation for the example:

  • In this firstly we are declaring LRU of size 2 
declaring lru of size 2 
  • lRUCache.put(1, 1); we will put value one with key 1
put value one with key 1
  • lRUCache.put(2, 2); we will put value 2 with key 2
put value 2 with key 2
  • Now if we do LRUCache.get(1) we will get 1 because 1 is present in the queue
  • lRUCache.put(3, 3); we will put the value 3 with key 3 now key 2 is evicted because 1 was recently used.
put the value 3 with key 3
  • lRUCache.put(4, 4); we will put value 4 with key 4
put value 4 with key 4
  • lRUCache.get(1);  return -1 because 1 is not present.
  • Now if we do LRUCache.get(3) we will get 3 because 3 is present in the queue
  • LRUCache.get(4) we will get 4 because 4 is present in the queue

C++ Code

Here is the C++ program to implement LRU cache using Queue and Hashing:

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
    list<pair<int, int>> cacheList;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }

        // Move the accessed element to the front of the list
        cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);

        return cacheMap[key]->second;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            // Update the value and move the element to the front
            cacheMap[key]->second = value;
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        } else {
            // Insert the new element
            if (cacheList.size() == capacity) {
                int lastKey = cacheList.back().first;
                cacheMap.erase(lastKey);
                cacheList.pop_back();
            }

            cacheList.emplace_front(key, value);
            cacheMap[key] = cacheList.begin();
        }
    }
};

int main() {
    // Example Usage
    LRUCache lruCache(2);

    lruCache.put(1, 1);
    lruCache.put(2, 2);
    cout << lruCache.get(1) << endl;  // Output: 1

    lruCache.put(3, 3);
    cout << lruCache.get(2) << endl;  // Output: -1 (not found)

    lruCache.put(4, 4);
    cout << lruCache.get(1) << endl;  // Output: -1 (not found)
    cout << lruCache.get(3) << endl;  // Output: 3
    cout << lruCache.get(4) << endl;  // Output: 4

    return 0;
}

Java Code

Here is the Java program to implement LRU cache:

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }

    public static void main(String[] args) {
        // Example Usage
        LRUCache lruCache = new LRUCache(2);

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));  // Output: 1

        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));  // Output: -1 (not found)

        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));  // Output: -1 (not found)
        System.out.println(lruCache.get(3));  // Output: 3
        System.out.println(lruCache.get(4));  // Output: 4
    }
}

Python Code

You can implement it in Python as well:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            del self.cache[key]
        elif len(self.cache) >= self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value

# Example Usage
lru_cache = LRUCache(2)

lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1))  # Output: 1

lru_cache.put(3, 3)
print(lru_cache.get(2))  # Output: -1 (not found)

lru_cache.put(4, 4)
print(lru_cache.get(1))  # Output: -1 (not found)
print(lru_cache.get(3))  # Output: 3
print(lru_cache.get(4))  # Output: 4

Output:

1
-1
-1
3
4

Complexity Analysis

Let’s try to understand the time and space complexity of the same.

Time Complexity:

get(key):

  • Searching for the key in the unordered_map takes O(1) time.
  • Moving the accessed element to the front of the list using splice also takes O(1) time. Therefore, the overall time complexity of get is O(1).

put(key, value):

  • If the key already exists, updating the value and moving the element to the front both take O(1) time.
  • If the key is not present: Inserting a new element into the list takes O(1) time.
  • If the cache is at full capacity, removing the least recently used element from both the list and the map takes O(1) time.

Therefore, the overall time complexity of put is O(1).

Space Complexity:

  • The space complexity is determined by the capacity of the cache.
  • The unordered_map (cacheMap) stores at most ‘capacity’ entries, each taking O(1) space.
  • The doubly-linked list (cacheList) also stores at most ‘capacity’ entries, each taking O(1) space.

Therefore, the overall space complexity is O(capacity).

Conclusion

In conclusion, understanding and implementing LRU cache is crucial for optimizing data retrieval in systems with limited resources, and the Queue Hashing Approach provides an efficient solution to this need. The provided code examples demonstrate the versatility of LRU cache implementation across different programming languages. Learn about Hashing in Data Structures to know how it works as well.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.