Thursday, July 26, 2018

Least Recently Used (LRU) cache

Below java code is a simple implementation of Least Recently Used (LRU) cache using HashMap and LinkedList.

For simplicity i am taking [Integer, String] as a key value pair for the cache, you can use any other structure as per your requirement.

LRU cache requirement -

get(key) will return the value if  present otherwise will return 'NA'

set(key,value) will insert the value if it is not already present else update the value. Also when cache reaches its MAX capacity it should remove least recently used value before inserting a new value.

Logic -
HashMap will contain the key,value pair of the cache and LinkedList will be used to track the usage. As you know LinkedList is a Doubly-linked list implementation of the List which maked insertion and deletion faster. Here first item will be the oldest item whereas last item will be the most recent item.