题解 | #设计LRU缓存结构# 主体是LinkedList

import java.util.*;


public class Solution {
    private int size = 0;
    //因为涉及到顺序问题 所以考虑有个集合 经常操作头部 所以考虑linkedlist
    private LinkedList<HashMap<Integer, Integer>> list = new LinkedList<>();
    //因为有key value 形式 所以 集合里面放map
    public Solution(int capacity) {
        size = capacity;
    }

    public int get(int key) {
        //第一步取 取不需要删除 找到返回即可
        for (int i = 0; i < list.size(); i++) {
            HashMap<Integer, Integer> map = list.get(i);
            if (map.get(key) != null) {
                int res = map.get(key);
                //第二步 返回之前调整缓存顺序 先删除这条数据 在插入到头部
                if (i != 0) {
                    HashMap<Integer, Integer> map2 = list.remove(i);
                    list.add(0, map2);
                }
                return res;
            }
        }
        //走到这里说明没找到
        return -1;
    }

    public void set(int key, int value) {
        // 第一步存 涉及到删除操作
        for (int i = 0; i < list.size(); i++) {
            HashMap<Integer, Integer> map = list.get(i);
            if (map.get(key) != null) {
                //先把旧的删除
                list.remove(i);
                break;
            }
        }
        HashMap<Integer, Integer> map2 = new HashMap<>();
        map2.put(key,value);
        list.add(0,map2);
        
        if(list.size() > size){
            list.removeLast();
        }
    }
}

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