Caches: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
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): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/o1/LRUList.java Playground LRUList] | 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): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/o1/LRUList.java Playground LRUList] | ||
<center>[[Image: LRUCache_O1.png]]</center> | |||
Revision as of 06:03, 14 August 2018
Internal
Overview
LRU Cache
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
