[Java] Implement a LRU cache

Here is an interesting and quite simple exercise: implement a LRU cache in Java.

When thinking about the problem, it appears immediately that we cannot do away with a single "basic" data structure, so we must combine at least two of them in a custom class. We use a HashMap for fast object retrieval and a custom doubly linked list to keep track of the objects access order, from MRU to LRU.

In this solution we have the put and get operations working in O(1) and we use additional O(N) space where N is the max cache size.

You can check the implementation on my Gist along with the definition of the ListNode class and some test cases.

[Sheet music] Hans Zimmer & Lisa Gerrard - Now we are free

Download it here

[Sheet music] Yann Tiersen - Comptine d'un autre ete large version

This sheet music is an improvement over the original version, download it here.