# My O(1) Java solution with comments beats 84%

• class LRUCache {
class Node {
public int key;
public int value;
public Node next;
public Node prev;
public Node (int key, int value) {
this.key = key;
this.value = value;
next = null;
prev = null;
}
}

``````HashMap<Integer, Node> map;
int mCapacity;
Node tail;
public LRUCache(int capacity) {
map = new HashMap<Integer, Node>(capacity);
this.mCapacity = capacity;
tail = null;
}

private void moveNodeToFront(Node node) {
return;
}

if (node == tail) {
tail = node.prev;
tail.next = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}

}

public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}

// Get from the map and update the LRU list.
Node node = map.get(key);
moveNodeToFront(node);
return node.value;
}

map.put(node.key, node);
tail = node;
return;
}

}

private void removeTail() {
if (tail == null) {
return;
}

Node temp = tail;
if (tail.prev != null) {
tail = tail.prev;
tail.next = null;
} else {
tail = null;
}
map.remove(temp.key);
}

public void put(int key, int value) {
if (map.containsKey(key)) {
// Move the node to the head;
Node node = map.get(key);
node.value = value;
moveNodeToFront(node);
return;
}

Node node = new Node(key, value);
// Put into HashMap and at the tail of the LRU list.
if (map.size() < mCapacity) {
return;
}

// Remove the tail from the LRU list and the map.
removeTail();

// Add the new one to the map and the front of LRU list.
}
``````

}

/**

• Your LRUCache object will be instantiated and called as such:
• LRUCache obj = new LRUCache(capacity);
• int param_1 = obj.get(key);
• obj.put(key,value);
*/

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.