Design a Least recently used cache.

Any item that is added newly should remain at the top of the cache. Any item that is read should be moved from it's present location to the top. Also the cache only has a limited capacity, in terms of number of elements, so when it hits the capacity limit during element addition, the least recently used element must be deleted from it.
Insertion, search and deletion should happen in O(1) time complexity.

The problem revolves mainly around figuring out the right data structures to use.