Java LRU 缓存使用 LinkedList

Question

堆栈溢出的新手，所以请不要介意我以菜鸟的方式问这个问题。我正在尝试使用链表实现 LRU 缓存，我在这里看到了使用 linkedHashMap 和其他数据结构的其他实现，但对于这种情况，我正在尝试使用链表创建最佳优化版本，正如我在技术期间被问到的那样圆形。

我将此处的缓存大小限制为 3

1. 有什么方法可以更好地优化这个 LRU 实现吗？

2. 此实现的时间复杂度是多少？如果不考虑只是打印 linkedList 中的值的 for 循环，它的数量级会是 O(N) 吗？

   public class LRU {
       public static void main(String[] args) {
   
           LinkedList list = new LinkedList();
           int[] feed = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };
           for (int i = 0; i < feed.length - 1; i++) {
               if (list.size() <= 2) {
                   list.add(feed[i]);
                   System.out.println();
                   System.out.println("Added " + feed[i]);
                   System.out.println("size of list is " + list.size());
                   System.out.print("this is list ");
                   for (int k = 0; k < list.size(); k++) {
                       System.out.print(" " + list.get(k));
                   }
               }
   
               System.out.println();
               if (list.size() >= 3) {
                   System.out.println();
                   System.out.println("feed is *" + feed[i + 1] + "*");
   
                   Integer value1 = (Integer) list.get(0);
                   Integer value2 = (Integer) list.get(1);
                   Integer value3 = (Integer) list.get(2);
                   if ((feed[i + 1] != value1) || (feed[i + 1] != value2)
                           || (feed[i + 1] != value3)) {
                       list.removeLast();
                       list.addLast(feed[i + 1]);
                       list.set(0, value2);
                       list.set(1, value3);
                       list.set(2, feed[i + 1]);
                   }
                   if (feed[i + 1] == value1) {
                       list.removeLast();
                       list.addLast(value1);
                       list.removeFirst();
                       list.addFirst(value2);
                       list.set(1, value3);
                   }
                   if (feed[i + 1] == value2) {
                       list.removeLast();
                       list.addLast(value2);
                       list.set(1, value3);
                       list.removeFirst();
                       list.addFirst(value1);
                   }
                   if (feed[i + 1] == value3) {
                       list.set(0, value1);
                       list.set(1, value2);
                   }
               }
               System.out.println("Current elements in cache at " + i);
               for (int t = 0; t < list.size(); t++) {
                   System.out.print(" " + list.get(t));
               }
               System.out.println();
           }
           System.out.println();
           System.out.println("------------------------------");
           System.out.println("current elements in cache ");
           for (int i = 0; i < list.size(); i++) {
               System.out.print(" " + list.get(i));
           }
       }
   }
   

Answer 1

首先你要定义一个接口(interface)。现在我不知道你应该如何使用你的缓存或者事实上你在做什么。尝试实现以下类:

class LRUCache {
    final int size;
    Cache(int size){
        this.size = size;
    }
    void put(String key, Integer value){
        //
    }
    Integer get(String key){
        //
    }
}

编辑(对评论的回复):
无论问题是什么，第一步都是定义接口(interface)(我指的不是 Java 接口(interface)，而是传达正在发生的事情的东西)。对于您的情况，请尝试实现此操作。

class MRU {
    final int size;
    MRU(int size){
        this.size = size;
    }

    void put(Integer value){
        //
    }

    Set<Integer> mostRecentlyUsed(){
        //
    }
}