146_LRU_Cache.java

classLRUCache {
privateclassDLLNode {
privateintkey, value;
privateDLLNodenext, prev;

publicDLLNode() {
key = -1;
value = -1;

next = null;
prev = null;
 }

publicDLLNode(intk, intv) {
key = k;
value = v;

next = null;
prev = null;
 }
 }

privateDLLNodehead, tail;
privateMap<Integer, DLLNode> hm;
privateintcap, size;

publicLRUCache(intcapacity) {
cap = capacity;
size = 0;

hm = newHashMap<>();

head = newDLLNode();
tail = newDLLNode();

head.next = tail;
tail.prev = head;
 }

publicintget(intkey) {
if (!hm.containsKey(key)) {
return -1;
 }

DLLNodenode = hm.get(key);
moveToHead(node);
returnnode.value;
 }

publicvoidput(intkey, intvalue) {
if (hm.containsKey(key)) {
DLLNodenode = hm.get(key);
node.value = value;
hm.put(key, node);
moveToHead(node);
return;
 }

DLLNodenode = newDLLNode(key, value);
hm.put(key, node);
moveToHead(node);
 ++size;

if (size > cap) {
remove(tail.prev);
 --size;
 }
 }

privatevoidremove(DLLNodenode) {
node.prev.next = node.next;
node.next.prev = node.prev;

hm.remove(node.key);
 }

privatevoidmoveToHead(DLLNodenode) {
if (node.prev != null) {
node.prev.next = node.next;
 }

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

node.next = head.next;
node.prev = head;

head.next.prev = node;
head.next = node;
 }
}