Designing and implementing a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return-1.set(key, value)- Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.
The LRUCache will be initialised with an integer corresponding to its capacity. Capacity indicates the maximum number of unique keys it can hold at a time.
Definition of “least recently used” : An access to an item is defined as a get or a set operation of the item. “Least recently used” item is the one with the oldest access time.
Design:
doubleListNode:DoublyLinkedList
size:keeps track of current size
doubleListNode head:keeps track of last used cache.
doubleListNode tail:keeps track of latest/most recently used cache.
HashMap<key,doubleListNode>:to get the key value in O(1) time.
In constructor, clearing all the global variables.
Get function:If key is present in hashMap, returning the value. But before that changing the current key to most recently used cache, i.e tail pointer. We are doing this with the help of removeNode and addNode methods.
Set Method:
RemoveMethod:
AddMethod:
