360. Least Recently Used (LRU) Cache – Using LinkedHashSet and Deque | Set 2

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

Earlier we had seen Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List. In this article, we will see the implementation using LinkedHashSet and Deque.

Lets first brief about LRU-

Given a cache (or memory) with 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.

Using LinkedHashSet and Deque:

Deque:  The Deque list will represent the cache and order. So each time item will be referred or looked or accessed, the item will be inserted into deque, if it is not already present. If the cache is reached to its limit, means full then the last item from the cache will be removed before the new item is inserted.  If the item is already present then it will be moved to the top of the cache (remove and add it again). Click here to read about Deque .

LinkedHashSet: Linked Hash Set will be used to check if the item is present in the cache in O(1) time. Deque operations take O(N) time.

See the image below for more understanding.

Output:

Looking for key: 1
Cache: 1
Looking for key: 2
Cache: 2 1
Looking for key: 1
Cache: 1 2
Looking for key: 3
Cache: 3 1 2
Looking for key: 4
Cache: 4 3 1 2
Looking for key: 3
Cache: 3 4 1 2
Looking for key: 5
Cache: 5 3 4 1
Looking for key: 4
Cache: 4 5 3 1
Looking for key: 6
Cache: 6 4 5 3