Which Data Structure Should be used for implementiong LRU cache?

Which Data Structure Should be used for implementiong LRU cache?

Their can be multiple approaches but we mainly use two data structures to implement an LRU Cache.

  1. Queue implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near rear end and least recently pages will be near front end.
  2. Hash with page number as key and address of the corresponding queue node as value.