LRU Cache : Java Implementation

LRU Cache (Page Replacement Scheme)

LRU Cache is designed for finding the location of desired page on disk. It maintains a cache of page number and its location on disk.

Whenever there is a request for new page number, Following operation will be performed.

– If it is present in cache, it is moved to front of the list and location is returned.

– If it is not present , a new page mapping is done. If cache is not full, a new entry is added to front otherwise least recently used entry is removed and then a new entry to front is added..

It should support two main operation.

set(int key, int value) -To add page number and disk location entry in cache. If cache is full, it should discard least recently used entry and add new one.

get(int key)– Return location on disk for given page number else return -1. If entry is present, reorder it to front.

Data Structures Used for LRU Cache Implementation

DoublyLinkedList 

We will use DoublyLinkedList for maintaining LRU Cache queue. Least recently used item will be present at end of list and latest used item will be present in front of list. Size of list will be equal to capacity of cache.

HashMap

We will use HashMap for efficient reordering and removal of least recently used items. Key will be pageNumber and Value will be DoublyLinkedList node.

LRUCache

 Complete Java Source Code

Driver program to check working of LRU Cache Implementation
Output for above driver program
LRU Cache after creation
key 10 value 20 key 9 value 18 key 8 value 16 key 7 value 14 key 6 value 12
LRU Cache after retrieving 7
key 7 value 14 key 10 value 20 key 9 value 18 key 8 value 16 key 6 value 12
LRU cache on adding one more item. It will replace last one
key 11 value 22 key 7 value 14 key 10 value 20 key 9 value 18 key 8 value 16

You may also like...