Home / Questions / Which Data Structure Should be used for implementiong LRU cache?
Explanatory Question

Which Data Structure Should be used for implementiong LRU cache?

👁 4,917 Views
📘 Detailed Answer
🕒 Easy to Read
Read the answer carefully and go through the related questions on the right side to improve your understanding of this topic.

Answer with Explanation

We use two data structures to implement an LRU Cache.

  1. Queue which is 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. A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?