Caches

From NovaOrdis Knowledge Base
Revision as of 06:03, 14 August 2018 by Ovidiu (talk | contribs)
Jump to navigation Jump to search

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

LRUCache O1.png