使用链表的Java LRU缓存(Java LRU cache using LinkedList)

新堆栈溢出，所以请不要介意问这个我小白方式。我试图用链表实现LRU缓存，我看到这里其他实现使用LinkedHashMap的和其他的数据结构，但这种情况下，我试图创建一个使用链表最好的优化版本，因为我在一个技术被问回合。

我在这里限制缓存大小3

有什么办法可以更好地优化这个LRU实现？

还什么将是这个实现的时间复杂度？不会是顺序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:

首先你要定义一个接口。现在，我看不出你应该如何使用您的缓存或实际上你在做什么。尝试执行下面的类：

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

编辑（回应评论）：
不管问题是什么，第一步是定义接口（由我并不意味着Java接口，只是一些通信，这是怎么回事）。在你的情况下，尝试再执行此操作。

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

    void put(Integer value){
        //
    }

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

Answer 2:

我会使用

LinkedList<Integer> list = new LinkedList<>();

而是你的实现我会使用

if (list.size() >= 3) {
    System.out.println();
    System.out.println("feed is *" + feed[i + 1] + "*");

    // retrieve the next value from the feed
    Integer next = feed[i + 1];

    if (!list.remove(next)) {
        list.removeLast();
    }
    list.addFirst(next);

}

System.out.println("Current elements in cache at " + i);

如果下一个值是在列表中，它被删除，并把在列表中的第一个元素。

如果下一个值是不在列表中，最后一个元素被删除，下一个值置为列表中的第一个元素。

当你再看看元素在列表中，例如，通过的indexOf（...）的列表从最新到最旧的条目搜索。

Answer 3:

这里是我的LRU缓存链表实现了一套，因为LinkedList的时间过长，将无法通过本文给出了法官（你会得到时间超出限制）。

公共类LRUCache {

private Map<Integer, Integer> blocks = new HashMap<Integer,Integer>();
private LinkedList<Integer> bru = new LinkedList<Integer>();
private int capacity;
private int length;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.length = 0;
}

public int get(int key) {
    Integer value = blocks.get(key);
    if (value != null) {
        bru.remove(value);
        bru.addFirst(value);
        return value;
    }
    return -1;
}

public void set(int key, int value) {
    if (blocks.containsKey(key)) {
        bru.remove(blocks.get(key));
        blocks.put(key, value);
    } else {
        if (length >= capacity) {
            blocks.remove(bru.removeLast());
            length--;
        }

        length++;
        blocks.put(key, value);
    }
    bru.addFirst(value);
}

}

文章来源: Java LRU cache using LinkedList