从头开始使用双向链接列表的LRU缓存 – moveToHead（Java）

我已经实现了一个简单的LRU缓存作为从头开始手动编写的双向链表。 缓存中填充了由数字（整数）ID区分的对象Request。 这些请求对象被生成为针对一组N <L个预定义的请求对象的L个随机独立且相同分布的请求的流，并且逐个地（即以串行方式）到达高速缓存。 然后我检查缓存命中或未命中以及当前缓存大小是否已达到最大缓存大小，然后根据具体情况，我执行将请求的项目插入缓存或从请求的项目替换LRU缓存项目。

缓存的其中一个操作如下：当我有缓存命中时，如果请求的项目不在头部，则必须将其移动到那里。

举个例子，假设缓存的最大大小为M = 4，其给定时间的内容如下：

货号：7 | 3 | 4 | 五

缓存位置索引：0 | 1 | 2 | 3（头是0，尾是3）

现在，如果我们有一个项目4的缓存命中，由于这个项目不在缓存的头部，它应该被移动到那里，结果将是：

货号：4 | 7 | 3 | 五

缓存位置索引：0 | 1 | 2 | 3（头是0，尾是3）

但是，当我运行代码时，结果是这样：

货号：4 | 7 | 3 | 4 | 五

缓存位置索引：0 | 1 | 2 | 3 | 4（头是0，尾是4）

换句话说，相关项目（在此示例中为项目4）不会从缓存中删除，然后会添加到头部，但只是添加到头部。 因此，高速缓存大小增加1（在该示例中，它变为5，其大于最大高速缓存大小M = 4）。

以下是相关代码，以及显示我认为问题性质的评论：

public void moveToHead(Request request) { if(request != head) { // set previous node equal to the requested item request.left = request; // --> if I set here request = null; then I will move to the head a null object!!! What to do? <-- // move requested item to head head.left = request; request.right = head; head = request; } } 

正如我对注释所说，如果在第一行代码之后我将对象请求设置为null以便将其删除，那么以下代码行将向头部移动一个空对象。 怎么解决这个？ 我假设我必须在下面的代码中使用时间请求变量，但我还没有想出如何做到这一点。

Answer 1

为此，变量头由虚拟初始化：

 head = new Request(); head.left = head; head.right = head, 

对于缓存命中，首先从列表中删除条目：

 request.left.right = request.right; request.right.left = request.left, 

然后将其添加到列表头：

 request.left = head; request.right = head.right; request.right.left = request; head.right = request; 

也许在这里看到一些现实世界的实现： https ： //github.com/headissue/cache2k/blob/master/core/src/main/java/org/cache2k/impl/LruCache.java

祝你好运！