LRU每次的操作都会将节点放入链表首部，双向链表的头插法与删除

核心点：LRU的每次操作(get,put)都会将节点放入链表首部。需要自定义双向链表。

双向链表需要提供addToHead,moveToHead,removeNode,removeLast的接口。这些接口只需要熟悉双向链的删除与头插法就能写出来。

链表插入删除过程的简化---虚拟节点，dummyHead,dummyTail。且初始化时要让dummyTail.prev保存最开的头结点，即dummyHead.next.

双向链表的头插法要明确，是将node插入到dummyHead与真正的头结点之间。而真正的头结点是dummyHead.插入完成后，node则变为真正的头结点。

put操作有则更新，无则创建，超过长度时，需要同时删除链表和map中的数据。---都需要将带插入元素放入链表头部！

大佬的图解，来源https://leetcode-cn.com/problems/lru-cache/solution/hashmap-shuang-xiang-lian-biao-chao-ji-xiang-xi-by/

import java.util.*;

class LURCache{

    class DoubleLinkedNode{
        int key,val;
        DoubleLinkedNode prev,next;

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

    DoubleLinkedNode dummyHead,dummyTail;
    Map<Integer,DoubleLinkedNode> map;
    int size,capacity;

    public LURCache(int capacity){
        this.capacity=capacity;
        map=new HashMap<>();
        dummyHead=new DoubleLinkedNode(-1,-1);
        dummyTail=new DoubleLinkedNode(-1,-1);
        dummyHead.next=dummyTail;
        dummyTail.prev=dummyHead;
        size=0;
    }

    private void removeNode(DoubleLinkedNode node){
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }
    private void addToHead(DoubleLinkedNode node){
        node.next=dummyHead.next;
        node.prev=dummyHead;

        dummyHead.next.prev=node;
        dummyHead.next=node;
    }

    private void moveToHead(DoubleLinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    private DoubleLinkedNode removeLast(){
        DoubleLinkedNode lastNode=dummyTail.prev;
        removeNode(lastNode);
        return lastNode;
    }

    public int get(int key){
        DoubleLinkedNode node=map.get(key);
        if(node==null){
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    public void put(int key ,int val){
        DoubleLinkedNode node=map.get(key);
        if(node!=null){
            node.val=val;
            moveToHead(node);
        }else{
            node=new DoubleLinkedNode(key,val);
            map.put(key,node);
            addToHead(node);
            size++;
            if(size>capacity){
                DoubleLinkedNode tail=removeLast();
                map.remove(tail.key);
                size--;
            }
        }


    }

}


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        LURCache cache=new LURCache(k);
        ArrayList<Integer> record=new ArrayList<>();
        for(int[] each : operators){
            int operation=each[0];
            if(operation==1){
                cache.put(each[1],each[2]);
            }else{
                record.add(cache.get(each[1]));
            }
        }
        int length=record.size();
        int[] res=new int[length];
        for(int i=0;i<length;i++){
            res[i]=record.get(i);
        }
        return res;

    }


}