Latest revision as of 19:22, 20 October 2021

Internal

LRU Cache

@@ Line 5: / Line 5: @@
 =Overview=
-=LRU Cache=
+=Cache Types=
+{{Internal|LRU Cache#Overview|LRU Cache}}
-An implementation where get() is O(1) and put() is O(n): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/LRUCacheOn.java Playground LRUCache O(n)]
-An implementation where both get() and put() are O(1): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/o1/LRUCacheO1.java 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): [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>