手写 双向链表实现 LRU，get() 和 set() 方法时间复杂度都为 O(1)

import java.util.*;


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
        init(k);
       
        List<Integer> ans = new ArrayList<>();
        for (int[] ele: operators) {
            if (ele.length == 3) {
                set(ele[1], ele[2]);
            } else {
                 ans.add(get(ele[1]));
                
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public void init(int k) {
        size = 0; // 当前元素个数
        capacity = k;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    static class DLinkedNode {
        int k;
        int v;
        public DLinkedNode(int k, int v) {
            this.k = k;
            this.v = v;
        }
        public DLinkedNode() {}
        DLinkedNode prev; // 前置节点
        DLinkedNode next; // 后继节点
        
    }
    DLinkedNode head;
    DLinkedNode tail;
    int capacity;
    int size;
    
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    public int get(int k) {
        DLinkedNode cur =  cache.get(k);
        if (cur == null) {
            // 表明没有查找到元素
            return -1;
        } else {
            moveToHead(cur); // 当前元素移到最前面
            return cur.v;
        }
    }
    
    public void set(int k, int v) {
        DLinkedNode cur =  cache.get(k);
        if (cur == null) {
            // 第一次 set (k, v)
            DLinkedNode node = new DLinkedNode(k, v);
            
            addToHead(node);
            size++;
            cache.put(k, node);
            if (size > capacity) {
                DLinkedNode last =  moveLast();
                size--;
                cache.remove(last.k);
            }
        } else {
            cur.v = v;
            moveToHead(cur);
        }
    }
    
    
    public void moveToHead(DLinkedNode node) {
        delNode(node);
        addToHead(node);
    }
    
    public void delNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = null;
        node.prev = null;
    }
    
    public void addToHead(DLinkedNode node) {
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    
    public DLinkedNode moveLast() {
        DLinkedNode last = tail.prev;
        delNode(last);
        return last;
    }
}