题解 | #设计LRU缓存结构 哈希表+定制双向链表#

import java.util.*;
public class Solution {
    private int capacity;
    private int used;
    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;
    //创建内部类，定制双向链表；
    class Node {
        int key;
        int value;
        Node pre;
        Node pos;
        public Node(int key, int value, Node pre, Node pos) {
            this.key = key;
            this.value = value;
            this.pre = pre;
            this.pos = pos;
        }
    }


    public Solution(int capacity) {
        // write code here
        this.used = 0;
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        //不包含key
        if (!map.containsKey(key)) {
            return -1;
        }

        toHead(map.get(key));
        return map.get(key).value;
    }

    public void set(int key, int value) {
        // write code here
        //考虑数值更新
        if (map.containsKey(key)) {
            map.get(key).value = value;
            toHead(map.get(key));
            return;
        }
        //考虑数值的插入
        //(1)已经达到capacity
        if (used == capacity) {
            map.remove(tail.key);
            tail = tail.pre;
            tail.pos = null;
            used--;
        }
//        未满容量时，从双向链表头节点的pre添加新的头节点，添加操作包括
        //1.创建新头节点
        //2.更新Hashmap

        //(2)头节点为空

        if (head == null) {
            head = new Node(key, value, null, null);
            tail = head;
        }
        //(3)非空未满容量
        else {
            Node newHead = new Node(key, value, null, head);
            head.pre = newHead;
            head = newHead;
        }
        map.put(key, head);
        used++;
    }

    public void toHead(Node node) {
        if (node != head) {
            // 需要更新位置的是尾部节点
            if (node == tail) {
                tail = tail.pre;
                tail.pos = null;
            } else {
                node.pre.pos = node.pos;
                node.pos.pre = node.pre;
            }
            node.pre = null;
            node.pos = head;
            head.pre = node;
            head = node;
        }

    }
}


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