
import java.util.HashMap;
import java.util.Map; public class LRUCache {
private int capacity;
private int len; class Data {
int key;
int value;
Data next;
Data pre;
} private Map<Integer, Data> dataSet; private Data head;
private Data rail; public LRUCache(int capacity) {
this.capacity = capacity;
this.len = 0;
this.head = null;
this.rail = null;
this.dataSet = new HashMap<Integer, Data>();
} public int get(int key) {
if (!dataSet.containsKey(key))
return -1;
Data temp = dataSet.get(key);
if (temp == head) {
return temp.value;
} else if (temp == rail) {
temp.pre.next = null;
rail = temp.pre;
} else {
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
}
temp.next = head;
temp.pre = null;
head.pre = temp;
head = temp;
return temp.value; } public void set(int key, int value) {
if (capacity == 0)
return;
if (dataSet.containsKey(key)) {
Data temp = dataSet.get(key);
if (temp == head) {
temp.value = value;
dataSet.put(key, head);
return;
} else if (temp == rail) {
temp.pre.next = null;
rail = temp.pre;
} else {
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
}
temp.value = value;
temp.next = head;
temp.pre = null;
head.pre = temp;
head = temp;
dataSet.put(key, head);
} else {
if (len == capacity) {
dataSet.remove(rail.key);
if (rail == head)
head = null;
else {
rail.pre.next = null;
rail = rail.pre;
}
len--;
} if (head == null) {
head = new Data();
head.key = key;
head.value = value;
head.next = null;
head.pre = null;
dataSet.put(key, head);
rail = head;
len++;
} else {
Data temp = new Data();
temp.key = key;
temp.value = value;
temp.next = head;
temp.pre = null;
head.pre = temp;
head = temp;
dataSet.put(key, head);
len++;
} } } public static void main(String args[]) {
LRUCache l = new LRUCache(2);
l.set(2, 1);
l.set(1, 1);
l.set(2, 3);
l.set(4, 1);
System.out.println(l.get(1));
System.out.println(l.get(2)); } }