本文共 2175 字，大约阅读时间需要 7 分钟。

class LRUCache {
       class Node {
           int key;        int value;        Node pre;        Node post;        public Node() {
   }        public Node(int key, int value) {
               this.key = key;            this.value = value;        }    }    private Map
   
     map;    private int size;//节点的个数    private int capacity;//缓存的容量    private Node head;//头节点    private Node tail;//未节点    public LRUCache(int capacity) {
           map = new HashMap<>();        size = 0;        this.capacity = capacity;        head = new Node();        tail = new Node();        head.post = tail;        tail.pre = head;    }        public int get(int key) {
           Node cur = map.get(key);        //当前节点不存在返回-1        if(cur == null) {
               return -1;        }else {
               //存在就移到队列头部            moveToHead(cur);            return cur.value;        }    }        public void put(int key, int value) {
           //获取该节点        Node cur = map.get(key);        //存在        if(cur != null) {
               //覆盖            cur.value = value;            //移到对头            moveToHead(cur);        }else {
               //不存在就创建一个            Node newNode  = new Node(key, value);            //加进map            map.put(key, newNode);            //加到对头            addToHead(newNode);            //数量加一            size++;            if(size > capacity) {
                   //超过容量删除队尾元素 删除map的值                Node tail = removeTail();                map.remove(tail.key);                size--;            }        }    }    public void moveToHead(Node node) {
           removeNode(node);        addToHead(node);    }    public void removeNode(Node node) {
           node.pre.post = node.post;        node.post.pre = node.pre;    }    public void addToHead(Node node) {
           node.pre = head;        node.post = head.post;        head.post = node;        node.post.pre = node;    }    public Node removeTail() {
           Node res = tail.pre;        removeNode(res);        return res;    }}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
   

转载地址：http://eqhzi.baihongyu.com/