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

import java.util.*;


public class Solution {

    private Map<Integer, ListNode> map = new HashMap<>();
    private ListNode head;
    private ListNode tail;
    private int capacity;
    private int size;

    public Solution(int capacity) {
         // write code here
         this.capacity = capacity;
         this.size = 0;
    }

    public int get(int key) {
         // write code here
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode node = map.get(key);
        moveToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
         // write code here
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = value;
            moveToHead(node);
            return;
        }
        // remove old node
        if (this.size == this.capacity) {
            map.remove(tail.key);
            this.size--;
            ListNode pre = tail.pre;
            if (pre != null) {
                pre.next = null;
                tail.pre = null;
                tail = pre;
            } else {
                tail = null;
                head = null;
            }
        }
        this.size++;
        ListNode newNode = new ListNode(key, value);
        map.put(key, newNode);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.pre = newNode;
            head = newNode;
        }
    }

    private void moveToHead(ListNode node) {
        if (node == head) {
            return;
        }
        if (node == tail) {
            tail = node.pre;
            tail.next = null;
        } else {
            ListNode pre = node.pre;
            ListNode next = node.next;
            pre.next = next;
            next.pre = pre;
        }
        node.next = head;
        head.pre = node;
        node.pre = null;
        head = node;
    }

    public static class ListNode {
        public int key;
        public int val;
        public ListNode pre;
        public ListNode next;

        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

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