Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List | Set 1

Objective: Design and Implement a data structure Least Recently Used (LRU) Cache.

Least Recently Used (LRU) Cache: You have given a cache (or memory) capacity. The cache will be filled with items you will access or look for it. The most recently accessed item will be at the top of the cache whereas least recently used cache will be at the end of the cache. As you will access the items, the cache will be filled as per the conditions below

  1. If item is not present in the cache and cache capacity is NOT REACHED then item will be added at top of the cache.
  2. If item is not present in the cache and cache capacity is REACHED then least recently item from cache will be removed (the last element in cache) and new item will be added at top of the cache.
  3. If item is already present in the cache then it will moved to the top of the cache.

Implementations:

LRU can be implemented in various ways, We will discuss the followings-

  1. Using HashMap and Doubly Linked List ( this article)
  2. Using LinkedHashSet and Deque.

Using HashMap and Doubly Linked List:

Doubly Linked List: For each item, we will create a Node for doubly linked list. The Node will have item value and next and previous node references. The list will represent the cache and order. So each time item will be referred or looked or accessed the nodes in the list will change the orders accordingly. Click here to read about Doubly Linked List.

HashMap: Map will be used to check if item is present in the cache in O(1) time. In key-value pair, the item will be the key and Node (doubly linked list node) will be its value. Every time item becomes the part of cache, we will put that item in map as well and vice versa, when item is deleted from the cache, we will delete it from the map.

Please see the image below for more understanding.

Complete Code:

Output:

Item accessed: 1
Cache : 1 
Item accessed: 2
Cache : 2 1 
Item accessed: 1
Cache : 1 2 
Item accessed: 3
Cache : 3 1 2 
Item accessed: 4
Cache : 4 3 1 2 
Item accessed: 3
Cache : 3 4 1 2 
Item accessed: 5
Cache : 5 3 4 1 
Item accessed: 4
Cache : 4 5 3 1 
Item accessed: 6
Cache : 6 4 5 3

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: