This post is completed by 1 user

  • 1
 Add to List
Hard

351. 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 the 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 the item is not present in the cache and cache capacity is NOT REACHED then the item will be added at top of the cache.
  2. If the 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 a new item will be added at top of the cache.
  3. If the item is already present in the cache then it will be 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 a 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 the item is present in the cache in O(1) time. In key-value pairs, the item will be the key and Node (doubly linked list node) will be its value. Every time item becomes the part of a cache, we will put that item in the map as well and vice versa, when the item is deleted from the cache, we will delete it from the map.

Please see the image below for more understanding.

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

Related Problems: