Which data structures are used for implementing LRU cache?

Web Development
,
#1
  • LRU cache or Least Recently Used cache allows quick identification of an element that hasn’t been put to use for the longest time by organizing items in order of use. In order to achieve this, two data structures are used:
    • Queue – This is implemented using a doubly-linked list. The maximum size of the queue is determined by the cache size, i.e by the total number of available frames. The least recently used pages will be near the front end of the queue whereas the most recently used pages will be towards the rear end of the queue.
    • Hashmap – Hashmap stores the page number as the key along with the address of the corresponding queue node as the value.
      6073×2635 73.3 KB
#2

A doubly linked list is an efficient data structure for building an LRU cache.We keep on inserting the data elements at the front…In case a reference comes for an existing element/page then we simply find that page in the list, delete it from its current position and insert it at the front.We can implement this using hash map along with DLL to reduce time complexity of finding that element in the DLL.

In case we have to replace a page, that page is the one at the back of the DLL I.e the last element of the DLL.

So the updations to the time frame of each element is also implemented easily plus the LRU page can be found and deleted in constant time .