[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.