public class LRUCache {
private HashMap<Integer, Entry> cache;
private Entry head;
private Entry tail;
private int capacity;
private int size;
public LRUCache(int capacity) {
cache = new HashMap<>();
this.capacity = capacity;
size = 0;
}
public int get(int key) {
if(!cache.containsKey(key)) {
return -1;
}
Entry e = cache.get(key);
afterAccess(e);
return e.value;
}
public void put(int key, int value) {
if(!cache.containsKey(key)) {
Entry e = new Entry(key,value);
cache.put(key,e);
afterInsertion(e);
size++;
} else {
Entry e = cache.get(key);
e.value = value;
cache.put(key, e);
afterAccess(e);
}
if(size > capacity) {
cache.remove(head.key);
removeHead();
}
}
private void removeHead() {
Entry e = head.next;
e.pre = null;
head = e;
size--;
}
private void afterAccess(Entry e) {
Entry before = e.pre;
Entry after = e.next;
if(before == null) {
Entry next = head.next;
if(next == null) {
return;
}
head = next;
next.pre = null;
tail.next = e;
e.pre = tail;
tail = e;
} else if( e == tail) {
return;
} else {
before.next = after;
after.pre = before;
tail.next = e;
e.pre = tail;
tail = e;
}
}
private void afterInsertion(Entry e) {
if(head == null) {
head = e;
} else {
tail.next = e;
e.pre = tail;
}
tail = e;
}
private static class Entry {
int key;
int value;
Entry pre;
Entry next;
public Entry(){}
public Entry(int key, int val) {
this.key = key;
this.value = val;
}
}
}
