力扣146
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
链接：https://leetcode-cn.com/problems/lru-cache
本题用到的数据结构为双端链表，为了提高查询效率，需使用hashmap，key为key，value为一个节点。节点中包含key,value,前节点和后节点。
当对链表进行增加删除的操作时，同时维护这个map。
进行LRUpu操作时，若map中无当前key，则在ma中新建节点。将节点通过前后指针，插入到链表中。若有当前key，则更新map中的值，将原有的node节点在链表中删除，将新建节点插入头部。
若put操作后，列表长度(即map长度)大于上限，则删除最后节点，并将map对应值删除。
代码如下。
1 import java.util.HashMap; 2 import java.util.Map; 3 4 public class LRUCache { 5 int capacity; 6 7 class doubleNode { 8 int key; 9 int value; 10 doubleNode pre; 11 doubleNode next; 12 13 public doubleNode(int key, int value) { 14 this.key = key; 15 this.value = value; 16 } 17 } 18 19 doubleNode start = new doubleNode(-1, 0); 20 doubleNode end = new doubleNode(-2, 0); 21 Map<Integer, doubleNode> map = new HashMap<>(); 22 23 public LRUCache(int capacity) { 24 this.capacity = capacity; 25 start.next = end; 26 } 27 28 public int get(int key) { 29 if (!map.containsKey(key)) { 30 return -1; 31 } else { 32 int value = map.get(key).value; 33 doubleNode cur = map.get(key); 34 cur.pre.next = cur.next; 35 cur.next.pre = cur.pre; 36 doubleNode next = start.next; 37 start.next = cur; 38 cur.pre = start; 39 next.pre = cur; 40 cur.next = next; 41 return value; 42 } 43 } 44 45 public void put(int key, int value) { 46 47 if (map.containsKey(key)) { 48 //移到顶端 49 //删除原有 50 doubleNode cur = map.get(key); 51 cur.pre.next = cur.next; 52 cur.next.pre = cur.pre; 53 //增加新的 54 map.put(key, new doubleNode(key, value)); 55 cur = map.get(key); 56 doubleNode next = start.next; 57 start.next = cur; 58 cur.pre = start; 59 next.pre = cur; 60 cur.next = next; 61 } else { 62 //移到顶端 63 map.put(key, new doubleNode(key, value)); 64 doubleNode cur = map.get(key); 65 doubleNode next = start.next; 66 cur.pre = start; 67 start.next = cur; 68 next.pre = cur; 69 cur.next = next; 70 //删尾巴 71 if (map.size() > capacity) { 72 cur = end.pre; 73 map.remove(cur.key); 74 doubleNode pre = cur.pre; 75 pre.next = end; 76 end.pre = pre; 77 } 78 } 79 } 80 81 public static void main(String[] args) { 82 LRUCache l = new LRUCache(2); 83 l.put(2, 1); 84 l.put(2, 2); 85 l.get(2); 86 l.put(1, 1); 87 l.put(4, 1); 88 l.get(2); 89 90 91 } 92 }
原文：https://www.cnblogs.com/zhangbochao/p/12461049.html