The Problem can be described as follow:
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key)  Get the value (will always be positive) of the key if the key exists in the cache, otherwise return 1.
put(key, value)  Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
And the Example is:


Analysis of the question
For HashMap Get/Set the time complexity is O(1), and for LinkedList Insert/Delete the time complexity is O(1). So, we are going to use these two data structure to form our solution. I will create a node as:


And create two Nodes: head and tail.
When we put a new value, if the capacity is full. We remove head.next, and add the new one to tail.prev. If there is still remaining space, we just add it to tail.prev directly.
The following code is the complete Java code and I am going to illustrate more on the code:


Get function:
In the get function:


is used to remove the current value we get from the its original position and call moveToTail(current);
to add it to tail.prev which presents the current value.
Put function:
In the put function:


The above code is used for removing the Least recently used value. And then we need to put the new one into tail.prev, still by calling: Node insert = new Node(key, value);
hm.put(key, insert);
moveToTail(insert);
moveToTail function:
This function is the complex one, because the link between them sometimes makes me a bit confused. And I explain these code with a comment after each line:


Hope it can help. :) Thanks for reading it.