The O(1) Requirement
To be efficient, a cache must retrieve and update data in O(1) time. A standard array queue fails here because updating a recently accessed item (moving it to the "most recent" end) takes O(N) time to shift elements.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
A Least Recently Used (LRU) Cache discards the least recently used items first when it runs out of capacity. It can be implemented using a HashMap paired with a Doubly Linked List (Deque).
To be efficient, a cache must retrieve and update data in O(1) time. A standard array queue fails here because updating a recently accessed item (moving it to the "most recent" end) takes O(N) time to shift elements.
We use a Deque to maintain the chronological order of usage. The "Front" represents the Least Recently Used item, and the "Back" represents the Most Recently Used item.
To achieve O(1) updates, a HashMap stores keys mapped directly to the Memory Address (Node pointer) in the Deque. When an item is accessed, we use the map to find it in O(1), severe its pointers, and push it to the Back of the Deque.