title: LRU cache in Java with Generics and O(1) operations
body: <p>This is a question that comes up a lot in job interviews. The idea is to define a data structure instead of using Java's built in LinkedHashMap.</p>
  
  <p>An LRU cache deletes the <em>least recently used</em> entry to insert a new one.
  So, given the following scenario:</p>
  
  <pre><code> A - B - C - D - E
  </code></pre>
  
  <p>Where A is the least recently used item, if we were to insert F, we need to remove A.</p>
  
  <p>This can be easily implemented if we keep a HashMap with the cache entries by (key,value) and a separate list that contains the elements' key and time of use. However, we would need to query the list to find the least recently used item, with a potential O(n) time complexity.</p>
  
  <p>How can this structure be implemented in Java for Generic objects and O(1) operations?</p>
  
  <p>This is different from the possible duplicate in that it focuses on efficiency (O(1) ops) and implementing the data structure itself, not extending Java's.</p>