1、前言

2、思路

所谓的 LRU，指的是，get 某一个 key，如果 key 存在，那么这个 <key,value> 要放到最新的位置。

如果 set 一个 <key,value>，如果这个 key 已经存在，那么要改变原先 value 的值，并把它放到最新的位置；如果这个 key 不存在，那么先要观察容量满没有，满了则先删除最近不使用的节点，然后将 <key,value> 放到最新位置；否则直接把 <key,value> 放到最新位置。

3、代码

import java.util.HashMap;
import java.util.Map;

class LRUCache {

    private Map<Integer, ListNode> map = new HashMap<>();

    private ListNode head, last;

    private Integer capacity;

    public LRUCache(int capacity) {
        this.head = new ListNode(null, null,  -1, -1);
        this.last = new ListNode(null, null, -1, -1);
        head.next = last;
        last.pre = head;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        ListNode node = map.get(key);
        if(node == null){
            return -1;
        }

        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        // 有重复的重新赋值并移动到前面即可
        // 如果直接判断大小，很可能出现这种情况：容量为2，{1=1, 2=2}，后面再 put(1,3)，直接判断会导致 2=2 没了，直接变成了 {1=3}
        ListNode node = map.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);
            return;
        }

        if(map.size() + 1 > capacity){
            ListNode lastNode = removeLast();
            map.remove(lastNode.key);
        }
        node = new ListNode(null, null, key, value);
        map.put(key, node);
        linkHead(node);
    }

    /**
     * 将节点链接到最后
     * @param node
     */
    private void linkHead(ListNode node) {
        ListNode nextNode = head.next;
        node.pre = head;
        node.next = nextNode;
        nextNode.pre = node;
        head.next = node;
    }

    /**
     * 将最后一个节点去掉
     * @return
     */
    private ListNode removeLast() {
        ListNode lastNode = last.pre;
        //删除节点
        removeNode(lastNode);
        return lastNode;
    }

    /**
     * 将要访问的节点移动最前面
     * @param node
     */
    private void moveToHead(ListNode node) {
        // 先删除节点
        removeNode(node);
        linkHead(node);
    }

    /**
     * 删除节点
     * @param node
     */
    private void removeNode(ListNode node) {
        ListNode preNode = node.pre;
        ListNode nextNode = node.next;
        preNode.next = nextNode;
        nextNode.pre = preNode;
        node.pre = null;
        node.next = null;
    }

    class ListNode {
        ListNode next;
        ListNode pre;
        Integer key;
        Integer value;

        public ListNode(ListNode next, ListNode pre, Integer key, Integer value) {
            this.next = next;
            this.pre = pre;
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}