For implementing an LRU cache, we can use a doubly linked list and a hash map.
Doubly Linked List - List of pages with most recently used page at the start of the list. So, as more pages are added to the list, least recently used pages are moved to the end of the list with page at tail being the least recently used page in the list.
Hash Map (key: page number, value: page) - For O(1) access to pages in cache
When a page is accessed, there can be 2 cases:
1. Page is present in the cache - If the page is already present in the cache, we move the page to the start of the list.
2. Page is not present in the cache - If the page is not present in the cache, we add the page to the list.
How to add a page to the list:
a. If the cache is not full, add the new page to the start of the list.
b. If the cache is full, remove the last node of the linked list and move the new page to the start of the list.
Java code is provided in code snippet section.
Please refer to Algorithm Visualization section for understanding how the algorithm works for different test cases.