The initial problem can be solved by double linked list, the linked list acts like a queue, but keeps moving the latest used (by put and get) node to the end of the queue so that the least recently used node will be at the head. Note that both **get** and **put** operation need to find the key in the list first, which costs at least O(n) time if n is the list's length (list is not sorted so binary search is not applicable). Even with the most advanced search method, the follow-up's requirement of O(1) is impossible. The only way to find some key in a data structure in O(1) time is to memorize the key's location. Thus, the hashtable, hashmap and array are suitable for storing the keys. For here I use hashmap, since array has disadvantages in resizing.

Still, we would like to keep track of the nodes in the linked list, considering a key is with its corresponding node, we combine the hashmap and linked list, which is to store the key as the hashmap's key, and the key's corresponding node as the value. The linked list is formed by node pointer within the node class. Every time a node in the linked list changes, we update the hashmap so it keeps tracking of the structure change in the list.

In this case, we find any node with certain value in O(1) time, and maintain the linked list's structure. The sample code is as follows, I also store the key in the node as well for a clear understanding. The runtime is about 200ms, only 20% above others, so I'm also looking for other optimization.

```
public class LRUCache {
class ListNode {
int val;
int key;
ListNode next;
ListNode prev;
ListNode(int key, int val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
private HashMap<Integer, ListNode> list = new HashMap<>();
private ListNode head = null;
private ListNode tail = null;
private int cap = 0;
public LRUCache(int capacity) {
if (capacity > 0) {
cap = capacity;
} else {
System.out.println("Capacity should be positive integer!");
return;
}
}
public int get(int key) {
int val = -1;
ListNode n = list.get(key);
if (n != null) {
val = n.val;
refreshNode(n);
}
return val;
}
public void put(int key, int value) {
ListNode n = list.get(key);
if (n != null) { // key already in
n.val = value;
refreshNode(n);
} else {
removeHead();
addTail(key, value);
}
}
private void removeHead() {
if (list.size() == cap) {// remove head
if (head.next != null) { // more than 1 element
head.next.prev = null;
}
ListNode temp = head;
head = head.next;
temp.next = null;
temp.prev = null;
int temp_key = temp.key;
temp = null;
list.remove(temp_key);
}
}
private void addTail(int key, int value) {
ListNode new_element = new ListNode(key, value);
if (tail != null) { // Add to tail
tail.next = new_element;
new_element.prev = tail;
tail = tail.next;
} else { // Initialize the head element
head = new_element;
tail = head;
}
list.put(new_element.key, new_element);
}
private void refreshNode(ListNode node) {
if (node.next != null) {
if (node.prev == null) {// head element
head = node.next;
} else {
node.prev.next = node.next;
}
node.next.prev = node.prev;
node.next = null;
tail.next = node;
node.prev = tail;
tail = tail.next;
} // else the element is the last one, do nothing
}
}
```