Java O(1) get/set solution, with map + double linked list

• This question is really practical. I have used similar code in a database system design project though this is more simple.

``````public class LRUCache {

final int CAPACITY;
Map<Integer, DListNode> map;

public LRUCache(int capacity) {
CAPACITY = capacity;
map = new HashMap<>(CAPACITY);
tail = new DListNode(0,0);
}

public int get(int key) {
DListNode node = map.get(key);
if(node == null){
return -1;
} else {
updateNode(node);
return node.val;
}
}

public void set(int key, int value) {
DListNode node = map.get(key);
if(node == null){
node = new DListNode(key, value);
if(map.size() < CAPACITY){
map.put(key, node);
} else { // do LRU
policy_LRU(node);
}
} else {
node.val = value;
map.put(key, node);
updateNode(node);
}
}

private void policy_LRU(DListNode node){
//delete the last one
map.remove(tail.pre.key);
deleteNode(tail.pre);
map.put(node.key, node);
}

private void updateNode(DListNode node){
deleteNode(node);
}

secondNode.pre = node;
node.next = secondNode;
}

private void deleteNode(DListNode node){
DListNode preNode = node.pre;
DListNode nextNode = node.next;
preNode.next = node.next;
nextNode.pre = preNode;
}

class DListNode{
int key;
int val;
DListNode next;
DListNode pre;
DListNode(int key, int val){
this.key = key;
this.val = val;
}
}
}
``````

• O(1) you are kidding me!!!!?

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