题解 | #设计LRU缓存结构#

import java.util.*;


public class Solution {
        class Node {
            int key;
            int value;
            Node pre;
            Node next;

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

        // cache
        HashMap<Integer, Node> map;
        // 记录最长时间没使用的节点
        Node head;
        // 记录最后使用的节点
        Node tail;

        // cache 长度
        int capacity;

        public Solution(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity);
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            // 节点之前存在了，然后被使用了需要移动到链表的尾部
            moveNode(node);
            return node.value;
        }

        public void set(int key, int value) {
            Node node = map.get(key);
            if (node == null) {
                // 节点之前不存在
                node = new Node(key, value);
                if (head == null) {
                    head = node;
                } else {
                    node.pre = tail;
                    tail.next = node;
                }
                tail = node;
            } else {
                // 节点之前已经存在了，更新值，然后移动位置
                node.value = value;
                moveNode(node);
            }
            map.put(key, node);
            // put进去后，缓存超过capacity,需要将头结点移除
            removeCacheIfNecessary();
        }

        private void removeCacheIfNecessary() {
            if (map.size() > capacity) {
                Node delete = head;
                head = head.next;
                delete.next =null;
                head.pre = null;
                map.remove(delete.key);
            }
        }

        /**
         * 将节点移动到链表尾部
         * @param node 要移动的节点
         */
        private void moveNode(Node node) {
            if (node == head && head.next != null) {
                // 要移动的节点时头节点，且节点的长度不为1
                head = head.next;
                head.pre = null;
                tail.next = node;
                node.pre = tail;
                tail = node;
                node.next = null;
                return;
            }
            if (tail != node) {
                // 要移动的节点不是头，也不是尾
                Node pre = node.pre;
                Node next = node.next;
                pre.next = next;
                next.pre = pre;
                tail.next = node;
                node.pre = tail;
                tail = node;
                node.next = null;
            }
            // 要移动的节点时尾节点，不需要移动
        }
    }

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

map + 双向链表的结构，给是使用数据后，把使用的数据移动到链表的最尾部，具体可以看代码中的注释