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

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    private Map<Integer, DlinkedNode> map = new HashMap<>();
    int size = 0;
    int capacity;
    DlinkedNode head;
    DlinkedNode tail;

    class DlinkedNode{
        int key, value;
        DlinkedNode next, pre;
        public DlinkedNode(){}
        public DlinkedNode(int key, int value){this.key = key;this.value = value;}
    }
    
    public int[] LRU (int[][] operators, int k) {
        // write code here
        List<Integer> list = new ArrayList<>();
        this.capacity = k;
        head = new DlinkedNode();
        tail = new DlinkedNode();
        head.next = tail;
        tail.pre = head;
        int count = 0;
        for(int i = 0; i < operators.length; i++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }
            else{ 
                list.add(get(operators[i][1]));
                count++;
            }
        }
        int index = 0;
        int[] ans = new int[count];
        for(int j = 0; j < list.size(); j++){
            ans[index++] = list.get(j);
        }
        return ans;
    }
    
    public int get(int key){
        DlinkedNode node = map.get(key);
        if(node == null) return -1;
        else{
            moveToHead(node);
            return node.value;
        }
        
    }
    
    public void set(int key, int value){
        DlinkedNode node = map.get(key);
        if(node == null){
            DlinkedNode newNode = new DlinkedNode(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
            if(size > capacity){
                map.remove(tail.pre.key);
                removeNode(tail.pre);
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    
    public void moveToHead(DlinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    
    public void addToHead(DlinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    
    public void removeNode(DlinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}