LRU Cache: Difference between revisions
Jump to navigation
Jump to search
(Created page with "=Internal= * Caches =Overview= An implementation where get() is O(1) and put() is O(n): [https://github.com/NovaOrdis/playground/blob/master/leetcode/...") |
|||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Caches#Cache_Types|Caches]] | * [[Caches#Cache_Types|Caches]] | ||
* [[The Optimal Caching Problem]] | |||
=Overview= | =Overview= | ||
Revision as of 19:22, 20 October 2021
Internal
Overview
An implementation where get() is O(1) and put() is O(n): Playground LRUCache O(n)
An implementation where both get() and put() are O(1): Playground LRUCache O(1)
The idea is to maintain the keys in a map (O(1)) for retrieval, but the time ordering is maintained implicitly in the structure of a double-linked list that can be manipulated in O(1): Playground LRUList
