题解 | #设计LRU缓存结构# 记得更新map

import java.util.*;

 class Node{
    int key;
    int value;
    Node pre;
    Node next;
 }
public class Solution {
    int capacity ;
    HashMap<Integer,Node> map ;
    Node head ;
    Node tail ;
 public Solution(int capacity) {
    this.capacity = capacity;
    map = new HashMap<>();
    head = new Node();
    tail = new Node();
    head.next = tail;
    tail.pre = head;
 }
 public int get(int key) {
    Node node = map.get(key);
    if(node==null){
       return -1;
    }
    // 访问过，需要移动到头
    // 首先删除
    delete(node);
    // 移动到头
    addFirst(node);
    return node.value;
 }
 public void addFirst(Node node){
    head.next.pre=node;
    node.next=head.next;
    node.pre=head;
    head.next=node;
 }
public void delete(Node node){
    Node right = node.next;
    Node left  = node.pre;
    left.next=right;
    right.pre=left;
}
public void removeLast(){
    Node node = tail.pre;
    map.remove(node.key);
    delete(node);
}
public void set(int key, int value) {
    // write code here
    Node node=map.get(key);
    if(node == null){
        node = new Node();
        node.key = key;
        // 非常重要
        map.put(key,node);
    }else{
        // 首先删除
        delete(node);
    }
    // 改变元素
    node.value=value;
    // 移动到头
    addFirst(node);
    // 如果size 超过 capacity
    if(map.size()>capacity){
        removeLast();
    }
}
}

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

删除或者添加Node的时候，记得更新map，即上述代码中48、57行