java 双向链表+HashMap

import java.util.*;

public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        //初始化LRU
        LRUcache lrucache = new LRUcache(k);
        //建立一个数组存放get值
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < operators.length; i ++){
            //判断为1
            if(operators[i][0] == 1){
                lrucache.put(operators[i][1], operators[i][2]);
            }else{
                //为2时，放入数组
                list.add(lrucache.get(operators[i][1]));
            }
        }
        
        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}

// 手写LRU缓存
class LRUcache{
    // 全局
    HashMap<Integer, Node> map;
    DoubleLinkedList cache;
    int cap;
    
    public LRUcache(int capacity){
        //定义一个HashMap
        map = new HashMap<>();
        //定义一个名字叫cache的双向链表
        cache = new DoubleLinkedList();
        //定义一个LRU容量
        cap = capacity;
    }
    
    public void put(int key, int value){
        Node newNode = new Node(key, value);
        
        //如果map中已存在key
        if(map.containsKey(key)){
            //删除链表中key
            cache.delete(map.get(key));
            //将新key添加到链表头
            cache.addFirst(newNode);
            //将新节点放入map
            map.put(key, newNode);
        }else{
            // 判断map是否达到容量
            if(map.size() == cap){
                //删除尾结点
                map.remove(cache.deleteLast());
            }
            //链表中添加新节点至头部
            cache.addFirst(newNode);
            //map中添加该节点
            map.put(key, newNode);
        }
    }
    
    public int get(int key){
        //判断map中是否有该节点
        //map没有的话
        if(!map.containsKey(key)) return -1;
        //map中有该节点，更新一下该节点，让其放在链表头
        int val = map.get(key).value;
        put(key,val);
        
        return val;
    }
    
    
}

// 定义双向链表
class DoubleLinkedList{
    
    Node head,tail;
    
    public DoubleLinkedList(){
        head = new Node(0, 0);
        tail = new Node(0, 0);
        
        head.next = tail;
        tail.prev = head;
    }
    
    // 内部方法 将当前节点添加到链表头
    public void addFirst(Node node){
        node.next = head.next;
        node.prev = head.next.prev;

        head.next.prev = node;
        head.next = node;
    }

    //内部方法 删除尾结点
    public int deleteLast(){
        if(head.next == tail) return -1;

        return delete(tail.prev);
    }

    //内部方法 删除key为n的节点
    public int delete(Node node){
        int key = node.key;
        
        node.prev.next = node.next;
        node.next.prev = node.prev;
        
        return key;
    }
    
}

// 定义节点
class Node{
    int key, value;
    Node prev, next;
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}