题解 | 设计LRU缓存结构

import java.util.*;


public class Solution {

    static  class Node {
        int value ;
        Node next;
        Node previous;
        Node(int key, int value) {
            this.value = value;
            this.key = key;
        }
        int key ;
    }

    //头节点
    static  Node head = new Node(Integer.MAX_VALUE,Integer.MAX_VALUE);
    //尾节点
    static   Node tail = new Node(Integer.MIN_VALUE,Integer.MIN_VALUE);

    //当前值
    static  int count;

    static int maxCount;

    static  Map<Integer, Node> map = new HashMap<>();


    public Solution(int capacity) {
        maxCount = capacity;
        head.next = tail;
        tail.previous = head;
    }

    static  public int get(int key) {
        Node node3 = map.get(key);

        if (node3 == null) {
            //System.out.print("-1 ");
            return -1;
        } else {
            //断开当前的连接
            //当前节点的前置节点的下一个设置成当前节点的下一个
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后前置链表(next)是 1->3
            node3.previous.next = node3.next;
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后置链表(previous)是 3->1
            node3.next.previous = node3.previous;

            //当前节点指向头节点后的第一个节点
            node3.next = head.next;

            //头节点后的第一个节点的上一个指向当前节点
            head.next.previous = node3;

            //头节点指向当前节点(因为当前节点变成第一个节点了)
            head.next = node3;

            //当前节点的上一级指向头节点
            node3.previous = head;
           // System.out.print(node3.value + " ");
            return node3.value;
        }

    }

    static  public void set(int key, int value) {
        Node node3 = map.get(key);
        //如果包含，需要移动位置
        if (map.get(key) != null) {
            node3.value = value;
            map.put(key, node3);
            node3.previous.next = node3.next;
            node3.next.previous = node3.previous;
            node3.next = head.next;
            head.next.previous = node3;
            head.next = node3;
            node3.previous = head;
        } else {
            count++;
            Node node = new Node(key, value);
            map.put(key, node);
            Node temp = head.next;
            head.next = node;
            node.previous = head;
            if (temp != null) {
                temp.previous = node;
                node.next = temp;
            }
            //数量已达上限，删除一个
            if (count > maxCount) {
                count--;
                Node node1 = tail.previous;
                if (node1 != null) {
                    Node node2 = node1.previous;
                    if (node2 != null) {
                        tail.previous = node2;
                        node2.next = tail;
                    }
                    map.remove(node1.key);
                }
            }
        }

        // System.out.print("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);
 */