What is LRU Cache and it’s implementation? what data structure should be used?
Everything you should know about LRU,Cache and it’s implementation with different data structures
4 min readApr 20, 2020
Google img…
So before understanding LRU we should know about cache so computers have cache memory that temporarily stores the most frequently used data. It’s a great way to get the data that is used most often because the retrieval process is super fast. Computers also have memory but it’s more expensive to retrieve data from there. However, cache memory is limited in size and there needs to be a way to manage what data needs to be removed from the cache in order to store new data. That’s where LRU cache comes in. It’s a cache replacement algorithm that removes the least recently used data in order to make room for new data.
Cache Requirements:
- Fixed Size: Cache needs to have some bounds to limit memory usages.
- Fast Access: Cache Insert and lookup operation should be fast , preferably O(1) time.
- Replacement of Entry in case , Memory Limit is reached: A cache should have efficient algorithm to evict the entry when memory is full
