The key point is to keep in mind that always put the latest node at the beginning.
import java.util.HashMap;
class LRUCache {
HashMap<Integer, Entry> map;
final static int LRU_SIZE = 4;
Entry start, end;
public LRUCache() {
map = new HashMap<>();
}
public void putEntry(int key, int value) {
if(map.containsKey(key)) {
Entry entry = map.get(key);
entry.value = value;
remove(entry);
addToTop(entry);
}else {
Entry e = new Entry();
e.key=key;
e.value=value;
e.prev=null;
e.next=null;
if(map.size() > LRU_SIZE - 1) {
map.remove(end.key);
remove(end);
addToTop(e);
}else {
addToTop(e);
}
map.put(key, e);
}
}
public int getEntry(int key) {
if(map.containsKey(key)) {
Entry entry = map.get(key);
remove(entry);
addToTop(entry);
return entry.value;
}
return -1;
}
public void addToTop(Entry node) {
node.prev = null;
node.next = start;
if(start != null)
start.prev = node;
start = node;
if(end == null) {
end = start;
}
}
public void remove(Entry node) {
if(node.prev != null) {
node.prev.next = node.next;
}else {
start = node.next;
}
if(node.next != null) {
node.next.prev = node.prev;
}else {
end = node.prev;
}
}
public static void main(String[] args)
{
LRUCache lrucache = new LRUCache();
lrucache.putEntry(1, 1);
lrucache.putEntry(10, 15);
lrucache.putEntry(15, 10);
lrucache.putEntry(10, 16);
lrucache.putEntry(12, 15);
lrucache.putEntry(18, 10);
lrucache.putEntry(13, 16);
System.out.println(lrucache.getEntry(1));
System.out.println(lrucache.getEntry(10));
System.out.println(lrucache.getEntry(18));
}
}
class Entry{
int value;
int key;
Entry prev;
Entry next;
}
Comments
Post a Comment