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

利用hashmap+双向链表实现LRU缓存，头部存放较新的节点，尾部存放不常使用的节点。
维护size字段，为链表长度，当长度超过k时，删除尾部节点

import java.util.*;

public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/

//链表节点类
class DNode{
    DNode pre;
    DNode next;
    int key;
    int val;
    public DNode(){}
    public DNode(int key,int val){
        this.key = key;
        this.val = val;
    }
}
//存放值
HashMap<Integer,DNode> map = new HashMap<>();
DNode head = new DNode();
DNode tail = new DNode();
int size  = 0;
int capacity ;

public int[] LRU (int[][] operators, int k) {
    //初始化
    this.capacity = k;
    this.head.next = tail;
    this.tail.pre = head;

    List<Integer> list = new ArrayList<>();
    // write code here
    for(int i = 0;i<operators.length;i++){
        int opt = operators[i][0];
        if(opt==1){
            set(operators[i][1],operators[i][2]);
        }else{
            list.add(get(operators[i][1]));
        }
    }
    int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
    return res;
}


public void set(int key,int value){
    DNode node = map.get(key);
    if(node!=null){
        node.val = value;
        moveToHead(node);
    }else{
        node = new DNode(key,value);
        addHead(node);
        map.put(key,node);
        size++;
        if(size>capacity){
            size--;
            map.remove(tail.pre.key);
            deleteNode(tail.pre);
        }
    }


}

public int get(int key){
    DNode dnode = map.get(key);
    if(dnode!=null){
        //移动到队首
        moveToHead(dnode);
        return dnode.val;
    }else{
         return -1;   
    }
}

private void moveToHead(DNode node){
    //删除旧节点
    deleteNode(node);
    //头节点新增
    addHead(node);
}

private void deleteNode(DNode node){
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

private void addHead(DNode node){
    node.pre = head;
    node.next = head.next;
    head.next.pre =  node;
    head.next = node;
}

}