设计LRU缓存结构

import java.util.*;

public class Solution {
    private int capacity;
    private List<Integer> status;//使用频率
    private Map<Integer, Integer> map; //存数据

    public Solution(int capacity) {
        this.capacity = capacity;
        this.status = new ArrayList<Integer>();
        this.map = new HashMap<Integer, Integer>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            map.put(key, value);
            return;
        } else {
            if (map.size() >= capacity) {
                map.remove(status.get(0));
                status.remove(0);
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            } else {
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            }
        }
    }
}

// 不想用链表，用队列可以嘛？
public class Solution {
    private Deque<Integer> queue;
    private Map<Integer, Integer> map;
    private int capacity;
    public Solution(int capacity) {
        // write code here
        queue = new ArrayDeque<>();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        // 更新缓存
        if (map.containsKey(key)) {
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key); // 访问过的一律放到队头
            return map.get(key);
        }

        return -1;
    }


    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)) { // 存在就放到队头
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key);
        } else { // 不存在就加入队头
            if (queue.size() == capacity) { // 容量满了，删一个
                int last = queue.getLast();
                // System.out.println(last+"-->"+map.get(key)+12);
                map.remove(last);
                queue.removeLast(); // 删掉最不常用的（队尾）
            }
            queue.addFirst(key);
        }
        map.put(key, value);
    }
}

import java.util.*;


public class Solution {
    // 缓存容量
    private int capacity;
    // 缓存链当前头节点
    private Node curHead;
    // 缓存链当前尾节点
    private Node curTail;
    // 缓存链当前长度
    private int curLen;
    // 存放缓存链的元素，便于查找，key是插入的数据的key，value是插入的数据所构成的节点Node
    private HashMap<Integer, Node> map;
    // 双向链表，记录当前缓存顺序
    class Node {
        // 需要存储的数据的key
        int key;
        // 需要存储的数据的value
        int val;
        Node pre;
        Node next;
        Node(int key, int value, Node pre, Node next) {
            this.key = key;
            this.val = value;
            this.pre = pre;
            this.next = next;
        }
    }

    public Solution(int capacity) {
// write code here
        this.capacity = capacity;
        this.curHead = null;
        this.curTail = null;
        this.curLen = 0;
        map = new HashMap<Integer, Node>();
    }

    public int get(int key) {
// write code here
        // 不存在返回-1
        if (!map.containsKey(key)) return -1;
        // 存在且该节点不是头结点，则将key对应的数据标记为最近使用，并返回数据值，
        // 通过map得到Node，再由Node得到数据值
        else {
            Node node = map.get(key);
            if (curHead != node) markRecently(node);
            return map.get(key).val;
        }
    }

    public void set(int key, int value) {
// write code here
        // 存在该节点
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 不是头结点，则更改当前节点值，将key对应的数据标记为最近使用
            if (node != curHead) {
                node.val = value;
                markRecently(node);
                // 是头结点，则更改当前节点值
            } else node.val = value;
            // 不存在该节点
        } else {
            // 如果头节点为空，则设置头结点和尾节点
            if (curHead == null) {
                // 设置头节点
                curHead = new Node(key, value, null, null);
                // 设置尾节点
                curTail = curHead;
                // 如果头节点不为空
            } else {
                // 创建该节点，并指向当前头结点
                Node node = new Node(key, value, null, curHead);
                // 将当前头节点指向该节点
                curHead.pre = node;
                // 将该节点置为当前头结点
                curHead = node;
            }
            // 当前链表长度+1
            curLen++;
            // 将当前节点加入map中
            map.put(key, curHead);
            // 如果当前链表超长，则进行末尾节点删除
            if (curLen > capacity) {
                // 删除map中的末尾节点
                map.remove(curTail.key);
                // 将链表中末尾节点的前序节点置为当前末尾节点
                curTail = curTail.pre;
                // 对末尾节点（此时的末尾节点为原末尾节点的前序节点）的后续节点置空
                curTail.next = null;
                // 当前长度-1
                curLen--;
            }
        }
    }
    // 将节点置为最近使用,即移到链表头部，已排除头部节点
    public void markRecently(Node node) {
        // 如果是末尾节点
        if (node == curTail) {
            // 将链表中末尾节点的前序节点置为当前末尾节点
            curTail = curTail.pre;
            // 对末尾节点（此时的末尾节点为原末尾节点的前序节点）的后序节点置空
            curTail.next = null;
        // 如果是中建节点
        } else {
            // 将该节点的后序节点置为该节点的前序节点的后序节点
            node.pre.next = node.next;
            // 将该节点的前序节点置为该节点的后序的前序节点
            node.next.pre = node.pre;
        }
        // 将该节点置为头结点的前序节点
        curHead.pre = node;
        // 将当前头节点置为该节点的后序节点
        node.next = curHead;
        // 当该节点置为当前头节点
        curHead = node;
    }
}

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

import java.util.*;

public class Solution {
    int capacity;
    // key -> Node
    Map<Integer, Node> cache;
    // lru 
    DeLinkedList lru;
    public Solution(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new DeLinkedList();
    }

    public int get(int key) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            lru.remove(node);
            lru.addLast(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            node.val = value;
            lru.remove(node);
            lru.addLast(node);
        } else {
            Node node = new Node(key, value);
            cache.put(key, node);
            lru.addLast(node);
            // evict
            if ( cache.size() > this.capacity ) {
                Node evict = lru.removeFirst();
                cache.remove(evict.key);
            }
        }
    }
}

class Node {
    int key;
    int val;
    Node pre;
    Node next;
    public Node(){}
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class DeLinkedList {
    // 虚拟节点
    Node head;
    Node tail;

    public DeLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public void addLast(Node node) {
        Node last = tail.pre;
        last.next = node;
        node.pre = last;
        node.next = tail;
        tail.pre = node;
    }

    public Node removeFirst() {
        Node remove = head.next;
        head.next = remove.next;
        remove.next.pre = head;
        return remove;
    }

    public Node remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

}

class Solution {
        int capacity = 0;
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> mp = new HashMap<>();
        public Solution(int capacity) {
            // write code here
            this.capacity = capacity;
        }
        public int get(int key) {
            // write code here
            if(!mp.containsKey(key)){
                return -1;
            }
            list.remove(Integer.valueOf(key));
            list.add(0,key);
            return mp.get(key);
        }

        public void set(int key, int value) {
            // write code here
            if(mp.containsKey(key)){
                list.remove(Integer.valueOf(key));
                list.add(0,key);
                mp.remove(key);
                mp.put(key,value);
                return;
            }
            if(list.size() < capacity){
                list.add(0,key);
                mp.put(key,value);
            } else{
                mp.remove(list.get(capacity-1));
                list.remove(capacity - 1);
                list.add(0,key);
                mp.put(key,value);
            }
        }
    }

    LinkedHashMap<Integer,Integer> map;
    int capacity;
    public Solution(int capacity) {
    // write code here
        this.capacity=capacity;
        map=new LinkedHashMap<Integer,Integer>(capacity);
    }

    public int get(int key) {
    // write code here
        if(map.containsKey(key)){
            int val=map.get(key);
            map.remove(key);
            map.put(key,val);
            return val;
        }
        return -1;
    }

    public void set(int key, int value) {
    // write code here
        if(map.size()==capacity && !map.containsKey(key)){
            map.remove(map.keySet().iterator().next());
        }
        map.put(key,value);
    }

public static class BinaryNode {
        int x;
        int y;

        BinaryNode(int x, int y) {
            this.x = x;
            this.y = y;
        }

        BinaryNode next = null;
    }

    // 设计lru
    public static ArrayList<String> LRUCache(ArrayList<String> operators, ArrayList<ArrayList<Integer>> param, int capacity) {
        // write code here
        Map<Integer, BinaryNode> keyHashMap = new HashMap<Integer, BinaryNode>();
        ArrayList<String> resultList = new ArrayList<String>();
        BinaryNode firNode = new BinaryNode(-1, -1);
        for (int i = 0; i < operators.size(); i++) {
            if ("set".equals(operators.get(i))) {
                resultList.add(set(param.get(i),keyHashMap,firNode,capacity));
            } else if ("get".equals(operators.get(i))) {
                resultList.add(get(param.get(i),keyHashMap,firNode));
            }
        }
        return resultList;
    }

    public static String set(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode,int capacity) {
        Integer key = params.get(0);
        Integer value = params.get(1);
        BinaryNode node = new BinaryNode(key, value);
        // 存在 清除 队尾补齐
        if (keyHashMap.containsKey(key)) {
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
        } else {
            // 不存在
            // 超过空间大小 清除头 队尾补齐
            if (keyHashMap.keySet().size() >= capacity) {
                keyHashMap.remove(firNode.next.x);
                removeFirNode(firNode);
                setBinaryNodeToLast(firNode,node);
            } else {
                // 未超过空间大小 队尾补齐
                setBinaryNodeToLast(firNode,node);
            }
        }
        keyHashMap.put(key,new BinaryNode(key, value));
        return "null";
    }

    public static String get(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode) {
        Integer key = params.get(0);
        // get也会默认为最常使用
        if (!keyHashMap.containsKey(key)) {
            return "-1";
        } else {
            BinaryNode node = keyHashMap.get(key);
            // 清除 放队尾
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
            return String.valueOf(keyHashMap.get(key).y);
        }
    }

    private static void removeFirNode(BinaryNode firNode) {
        firNode.next = firNode.next.next;
    }

    public static void removeTempNode(BinaryNode firNode ,BinaryNode tempNode) {
        while (firNode.next != null) {
            if (firNode.next.x == tempNode.x) {
                firNode.next = firNode.next.next;
                return;
            }
            if (firNode.next.next == null) {
                firNode.next = null;
                return;
            }
        }
    }

    public static void setBinaryNodeToLast(BinaryNode firNode,BinaryNode lastNode) {
        while (firNode.next != null) {
            firNode = firNode.next;
        }
        firNode.next = lastNode;
    }

public class Solution {
   
    //双向链表结点结构
    static class Node {
        int key;
        int val;
        Node pre;
        Node next;

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

    HashMap<Integer, Node> cache; //缓存结构
    int capacity;//最大容量
    Node head = null;//链表表头
    Node tail = null;//链表表尾

    public Solution(int capacity) {

        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        //判断缓存是否存在这个key
        if (cache.containsKey(key)) {
            //将访问的元素添加到双向链表的表头
            //添加表头元素
            Node cur = cache.get(key);
            //判断该元素是否是表头元素
            if (cur != head) {  //表头元素不移动
                cur.pre.next = cur.next;

                if (cur.next != null)//表尾元素移动需要修改尾部指针
                    cur.next.pre = cur.pre;
                else tail = cur.pre;//说明是表尾元素
                //将元素设为表头元素
                head.pre = cur;
                cur.next = head;
                cur.pre = null;
                head = cur;
            }
            return cache.get(key).val;
        }
        //没有就返回-1
        return -1;
    }

    public void set(int key, int value) {
        //如果是缓存里面的第一个元素
        if (head == tail && head == null) {

            Node cur = new Node(key, value); //构造链表结点
            cache.put(key, cur); //将结点加入缓存
            head = cur;//表头表尾指向该结点
            tail = cur;
        } else {
            //将新添加的元素加入表头
            Node cur = null;
            if (cache.containsKey(key)) {//如果缓存里有key，则更新该key的value值
                cur = cache.get(key);
                cur.val = value;
            } else {
                cur = new Node(key, value);
                if (capacity ==
                        cache.size()) { //如果缓存溢出,删除表尾元素，并将新元素添加进表头
                    //删除表尾元素
                    cache.remove(tail.key);
                    tail = tail.pre;
                    tail.next = null;

                }
            }
            cache.put(key, cur);//将新元素放入缓存
            //添加表头元素
            head.pre = cur;
            cur.next = head;
            head = cur;

        }
    }
}

//标着困难没想到出奇的简单
import java.util.*;
class Node {
    int key = 0;
    int value = 0;
    Node next = null;
}

public class Solution {
    int n = 0;
    int capacity;
    LinkedList<Node> list = new LinkedList<>();
    public Solution(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        int a;
        if (find(key) == -1) return -1;
        else {
            a = list.get(find(key)).value;
            Node node = list.get(find(key));
            list.remove(find(key));
            list.addFirst(node);
            return a;
        }
    }

    public void set(int key, int value) {
        n++;
        if (n > capacity) {
            list.removeLast();
        }
        if (find(key) == -1) {
            Node node = new Node();
            node.key = key;
            node.value = value;
            list.addFirst(node);
        } else {
            list.get(find(key)).value = value;
        }
    }
    public int find(int key) {
        for (int i = 0 ; i < list.size(); i++) {
            if (list.get(i).key == key) return i;
        }
        return -1;
    }
}

import java.util.*;

public class Solution {
    class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

    private HashMap<Integer, Integer> entity;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.entity = new HashMap<>();
    }

    public int get(int key) {
        // write code here
        Integer val = entity.get(key);
        if (val == null) {
            return -1;
        }

        removeNode(key, val);
        insertHead(new Node(key, val));

        return val;
    }

    public void set(int key, int value) {
        // write code here
        Integer oldVal = entity.put(key, value);
        if (oldVal == null) {
            if (this.size == this.capacity) {
                removeLast();
            } else {
                this.size++;
            }
        }

        if (oldVal != null) {
            removeNode(key, oldVal);
            this.entity.remove(key, oldVal);
        }

        insertHead(new Node(key, value));
    }

    private void removeNode(int key, int val) {
        if (this.size == 0) {
            return;
        }

        Node node = this.head.next;
        while (node != null) {
            if (node.key == key && node.val == val) {
                Node pre = node.pre;
                Node next = node.next;
                pre.next = next;
                next.pre = pre;
                break;
            } else {
                node = node.next;
            }
        }
    }

    private void insertHead(Node node) {
        Node tmp = this.head.next;
        node.next = tmp;
        tmp.pre = node;
        node.pre = this.head;
        this.head.next = node;
    }

    private void removeLast() {
        if (this.size == 0) {
            return;
        }

        Node node = this.tail.pre;
        Node pre = node.pre;
        pre.next = this.tail;
        this.tail.pre = pre;
        node.next = null;
        node.pre = null;
        this.entity.remove(node.key, node.val);
    }
}

import java.util.*;


public class Solution {
    class DLinkedNode{
        int key,value;
        DLinkedNode pre,next;
        public DLinkedNode(){}
        public DLinkedNode(int key1,int value1){
            key=key1;
            value=value1;
        }
    }
    int size,capacity;
    Map<Integer,DLinkedNode> map=new HashMap<Integer,DLinkedNode>();
    DLinkedNode dummyhead,dummytail;
    
    
    public Solution(int capacity) {
        this.size=size;
        this.capacity=capacity;
        dummyhead=new DLinkedNode();
        dummyhead=new DLinkedNode();
        dummyhead.next=dummytail;
        dummytail.pre=dummyhead;
         // write code here
    }

    public int get(int key) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            return node.value;
        }else{return -1;}
    }

    public void set(int key, int value) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            node.value=value;
        }else{
            DLinkedNode node=new DLinkedNode(key,value);
            addTohead(node);
            size=size+1;
            if(size>capacity){
                DLinkedNode tail=dummytail.pre;
                removeNode(tail);
                size=size-1;
                map.remove(tail.key);
            }
        }
    }
    public void addTohead(DLinkedNode node){
        node.pre=dummyhead;
        node.next=dummyhead.next;
        dummyhead.next.pre=node;
        dummyhead.next=node;
    }
    public void removeNode(DLinkedNode node){
        node.next.pre=node.pre;
        node.pre.next=node.next;
    }
    public void moveTohead(DLinkedNode node){
        removeNode(node);
        addTohead(node);
    }
}

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

import java.util.*;
public class Solution {
    int capacity = 0;
    HashMap<Integer,Node> map;
    // 双向链表的头尾节点
    Node head;
    Node tail;
    // 标记，用于第一次构成链表时的头尾指针指向
    class Node{
        // K-V
        int key;
        int value;
        // 双指针
        Node prev = null;
        Node next = null;
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        this.map = new HashMap<Integer,Node>();
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
    }

    public int get(int key) {
         // write code here
        if(map.containsKey(key)){
            Node tmp = map.get(key);
            removeFromLink(tmp);
            insertToHead(tmp);
            return tmp.value;
        }
        else{
            return -1;
        }
    }

    public void set(int key, int value) {
         // write code here
        Node node = new Node(key,value);
        addMapAndConnectNode(key,node);
        
    }
    // 用于添加数据进哈希表和连接链表
    public void addMapAndConnectNode(int key,Node node) {
        if(map.containsKey(key)){
            Node recentlyNode= map.get(key);
            recentlyNode.value = node.value;
            removeFromLink(recentlyNode);
            insertToHead(recentlyNode);
            return;
        }
        else if(map.size() < capacity){
            // 第一个元素特殊处理，添加头尾节点
            if(map.size()==0){
                head.next = node;
                node.prev = head;
                node.next = tail;
                tail.prev = node;
                insertToHead(node);
            }
            else{
                insertToHead(node);
            }
        }
        else if(map.size() >= capacity){
            Node removeNode = removeFromLinkTail();
            insertToHead(node);
            map.remove(removeNode.key);
        }
        map.put(key,node);
    }
    // 移除链表末尾的元素
    public Node removeFromLinkTail(){
        Node removeNode = tail.prev;
        tail.prev.next = null;
        tail.prev = tail.prev.prev;
        tail.prev.next.prev = null;
        tail.prev.next = tail;
        return removeNode;
    }
    // 把某个传进来的元素插到链表头
    public void insertToHead(Node node){
        // 在get的时候，如果该节点就在头部，那么就不用移到头部了
        if(node.prev == head){
            return ;
        }
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    // 从链表中移除某个传进来的元素元素
    public void removeFromLink(Node node){
        // 在get的时候，如果该节点就在头部，那么就不用移除了
        if(node.prev == head){
            return ;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = 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);
 */

public class Solution {
    private int curCapacity;
    Map<Integer,DoubleLinkedList> mp;
    private DoubleLinkedList head,tail;  // 头尾指针
    public Solution(int capacity) {
        mp = new HashMap<>();
        curCapacity = capacity;
    }
    public void makeHead(int key) {
        DoubleLinkedList tmp = mp.get(key);
        if(tmp!=head) {
            // 摘掉tmp
            if(tmp==tail) {
                tail = tail.pre;
                tail.next = null;
            } else {
                tmp.pre.next = tmp.next;
                tmp.next.pre = tmp.pre;
            }
            // tmp成为头结点
            tmp.next = head;
            head.pre = tmp;
            tmp.pre = null;
            head = tmp;
        }
    }
    public int get(int key) {
        if(!mp.containsKey(key)) return -1;
        DoubleLinkedList tmp = mp.get(key);
        makeHead(key);
        return tmp.value;
    }

    public void set(int key, int value) {
        // write code here
        if(mp.containsKey(key)) {  // 如果存在修改值
            DoubleLinkedList tmp = mp.get(key);
            tmp.value=value;
            makeHead(key);
        }else if(curCapacity==0){  // 当无容量
            mp.remove(tail.key); // 删除双链表最后一个节点的哈希值
            tail.value = value;
            tail.key = key;
            mp.put(key, tail);  // 存放到最后一个节点并对应新的键值对
            makeHead(key);  // 调整到链表最前面
        } else if(head==null) {  // 第一个值 初始化头尾指针
            head = new DoubleLinkedList(key, value, null, null);
            tail = head;
            mp.put(key, head);
            curCapacity--;
        }else {  // 容量不满
            DoubleLinkedList tmp = new DoubleLinkedList(key, value, null,head);
            head.pre = tmp;
            head = tmp;
            mp.put(key,head);
            curCapacity--;
        }
    }
    class DoubleLinkedList{
        int key;
        int value;
        DoubleLinkedList pre;
        DoubleLinkedList next;
        public DoubleLinkedList(int k,int v,DoubleLinkedList p,DoubleLinkedList n){
            key = k;value=v;pre=p;next=n;
        }
    }
}

import java.util.*;


public class Solution {
    //本质上每一个node节点都是有两个next的，但是DoubleList中我们只定义了一个，另一个是hashmao的单向链表的指向
    //DoubleList的双向链表单独一条，虽然hashmap有一条单链表，但是仅仅用于hashmap的查找，真正最近使用的元素获取是双向确定的
    //我们操作的next都是自己双链表的，hashmap本身的next是内部单链表的查找
    DoubleList head;
    DoubleList tail;
    int capacity;
    //总的node个数，而不是map的key数量或者单个双向链表的长度
    int size;
    Map<Integer,DoubleList> map = new HashMap<>();
    class DoubleList{
        int key;
        int value;
        DoubleList pre;
        DoubleList next;

        public DoubleList() {
        }

        public DoubleList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public Solution(int capacity) {
        this.capacity = capacity;
        //不需要直接链接，是一个两个虚拟的首尾节点,只是为了确定链表的头和尾方便直接找到
        head = new DoubleList();
        tail = new DoubleList();
        head.next = tail;
        tail.pre = head;
        this.size = 0;

    }

    public int get(int key) {
        if(map.containsKey(key)){
            DoubleList node = map.get(key);
            nodeTOHead(node);
            return node.value;
        }else {
            return -1;
        }

    }

    private void nodeTOHead(DoubleList node) {
        removeNode(node);
        putNode(node);

    }

    private void removeNode(DoubleList node) {
        node.next.next = node.pre;
        node.pre.next = node.next;
        node.next = null;
        node.pre = null;
    }

    public void set(int key, int value) {
         if(map.containsKey(key)){
             DoubleList node = map.get(key);
             node.value = value;
             nodeTOHead(node);
         }else {
            DoubleList node = new DoubleList(key,value);
            map.put(key,node);
            size++;
            putNode(node);
            if(capacity < size){
                removeLast();

            }

         }
    }

    private void removeLast() {
        DoubleList lastNode = tail.pre;
        removeNode(lastNode);
        map.remove(lastNode.key);
        size--;

    }
    //插到双链表头部
    private void putNode(DoubleList node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre  = node;
        head.next = node;

    }

}

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

import java.util.*;


public class Solution {
    class DLinkedNode{
        DLinkedNode prev;
        DLinkedNode next;
        int key;
        int value;
        public DLinkedNode(){}
        public DLinkedNode(int k,int v){
            this.key = k;
            this.value = v;
        }
    }
    
    Map<Integer,DLinkedNode> cache = new HashMap<>();
    DLinkedNode head = new DLinkedNode();
    DLinkedNode tail = new DLinkedNode();
    int size =0;
    int capacity;
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
         // write code here
        DLinkedNode node = cache.get(key);
        if(node==null) return -1;
        
        moveToHead(node);
        return node.value;
    }

    public void set(int key, int value) {
         // write code here
        DLinkedNode node =  cache.get(key);
        if(node==null){
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            ++size;
            if(size > capacity){
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                --size;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    
    void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        
    }
    void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    void removeNode(DLinkedNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    DLinkedNode removeTail(){
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

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