思路：

题目要求实现“最近最少使用”缓存算法，这在Android中的图片缓存中有使用。

实现要求是，最近被访问（get,set）的放前后；最久被访问的放在最后，但容量不足时删除此结点。

实现方式：双链表 + HashMap

java code:

class Node {
int key,value;
Node pre,next;

public Node(int key, int value) {
this.key = key;
this.value = value;
}
}

public class LRUCache {

HashMap<Integer, Node> map;
int capicity;
int count;
Node head,tail;

// 设置一个头结点和一个尾结点，作为哨兵
public LRUCache(int capacity) {
this.capicity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);

head.next = tail;
tail.pre = head;
head.pre = null;
tail.next = null;
count = 0;
}

// 删除结点
public void deleteNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}

// 添加，添加到head的下一个结点
public void addToHead(Node node) {
node.pre = head;
node.next = head.next;

head.next.pre = node;
head.next = node;
}

//
public int get(int key) {
if(map.get(key)!=null) {
Node node = map.get(key);
int result = node.value;
deleteNode(node);
addToHead(node);
return result;
}
return -1;
}

//
public void set(int key, int value) {
if(map.get(key)!=null) {
Node node = map.get(key);
node.value = value;
deleteNode(node);
addToHead(node);
}else{
Node node = new Node(key, value);
map.put(key, node);
if(count < capicity) {
count++;
addToHead(node);
}else{
map.remove(tail.pre.key);
deleteNode(tail.pre);
addToHead(node);
}
}
}
}

集合类中LinkedHashMap的实现方式就是：双链表 + HashMap，也是Android LRU Cache中实现使用数据结构，因此只需在LinkedHashMap的基础上添加容量限制即可。

java code:

public class LRUCache {

private Map<Integer, Integer> map;

public LRUCache(int capacity) {
map = new LinkedCappedHashMap<>(capacity);
}

public int get(int key) {
if(!map.containsKey(key)) { return -1; }
return map.get(key);
}

public void set(int key, int value) {
map.put(key,value);
}

private static class LinkedCappedHashMap<K,V> extends LinkedHashMap<K,V> {

int maximumCapacity;

LinkedCappedHashMap(int maximumCapacity) {
super(16, 0.75f, true);
this.maximumCapacity = maximumCapacity;
}

protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maximumCapacity;
}
}
}