Skip to main content

LRU Cache

Learn LRU Cache (Linked List, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is an LRU Cache? A Least-Recently-Used cache holds a fixed number of items; when full, adding a new item EVICTS the item that hasn't been accessed in the longest time. Both get and put must run in O(1) - which needs a HashMap (O(1) lookup) PLUS a doubly linked list (O(1) reordering) working together: HashMap maps key → node, for instant lookup. Doubly linked list keeps items ordered by recency - most-recently-used at the front, least-recently-used at the back, ready for O(1) eviction.

More lessons in Linked List