https://leetcode-cn.com/problems/lru-cache/ 模拟了缓存机制。 这道题需要一个东西来存储键值对的信息，所以采用map 整个过程包括的操作有插入，删除。因此使用双向链表是比较容易实现这一功能的目的的。
class LRUCache { private class Node{ private int key; private int value; private Node pre; private Node next; public Node(){} public Node(int key,int value){ this.key = key; this.value = value; } } private Node dummyHead = new Node(); private Node dummyTail = new Node(); private int capacity; private int size; private HashMap<Integer,Node> map = new HashMap<>(); private void add(Node node){ Node originHead = dummyHead.next; dummyHead.next = node; node.pre = dummyHead; node.next = originHead; originHead.pre = node; } private void del(Node node){ Node preNode = node.pre; Node nextNode = node.next; preNode.next = nextNode; nextNode.pre = preNode; node.pre = null; node.next = null; } public LRUCache(int capacity) { dummyHead.next = dummyTail; dummyTail.pre = dummyHead; this.capacity = capacity; size = 0; } public int get(int key) { Node node = map.get(key); if(node == null){ return -1; } del(node); add(node); return node.value; } public void put(int key, int value) { Node node = map.get(key); if(node != null){ node.value = value; del(node); add(node); }else{ if(size<capacity){ size++; }else{ Node delNode = dummyTail.pre; map.remove(delNode.key); del(delNode); } Node newNode = new Node(key,value); add(newNode); map.put(key,newNode); } } }还可用LinkedHashMap进行实现：
class LRUCache { private LinkedHashMap<Integer, Integer> map; private int maxSize; private int curSize; public LRUCache(int capacity) { map = new LinkedHashMap<>(); this.maxSize = capacity; this.curSize = 0; } public int get(int key) { if(!map.containsKey(key)){ return -1; } int val = map.get(key); map.remove(key); map.put(key, val); return val; } public void put(int key, int value) { if(map.containsKey(key)){ map.remove(key); map.put(key,value); }else{ curSize++; map.put(key,value); if(curSize > maxSize){ int oldestKey = map.keySet().iterator().next(); map.remove(oldestKey); curSize--; } } } }