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


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.


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


 Complete Java Source Code

[su_button url=”” target=”blank” style=”soft” background=”#51d461" color=”#ffffff” size=”6" center=”yes” icon=”icon: arrow-circle-o-down”]Download Complete Source Code[/su[/su_button]

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *