java - 在 ID 的 LinkedList 中搜索 key，如果 key 尚未位于列表的头部，则将其添加到列表的头部

Question

我需要一些帮助:我正在编写一个程序来访问列表并“查找”与其请求序列相同的 int ID。

假设我有一个包含 3 个数字的缓存，20 30 10。

包含 6 个数字的请求序列，20 30 5 30 5 20。

程序将从请求序列中的第一个数字开始，然后遍历缓存，将请求与缓存中的每个数字进行比较，一次一个，如果找到匹配则停止。一场比赛会增加一个变量命中。变量 compCount 测量找到匹配项所需的比较次数。如果比较大于1，或者换句话说，如果在缓存中找到的键不在LinkedList的头部，则程序将该键移动到LinkedList的头部。

下图展示了30后的新缓存与缓存的对比:

30 20 10

另一方面，如果未命中，程序会将键添加到 LinkedList 的头部。

下图为5后的新缓存与缓存对比:

5 30 20 10

以下是我到目前为止所做的事情:

static void moveToFront() {

    int key = 0;
    int hit = 0;
    int cacheSize = initCount;

    boolean found = false;

    int[] comparisons = new int[reqCount];

    for(int i = 0; i < reqCount; i++) {
        found = false;
        key = reqData[i];
        int compCount = 0;

        Node curr = head;
        while(curr != null) {
            compCount++;

            if(curr.data == key) {
                found = true;
                comparisons[i] = compCount;
            }
            curr = curr.next;
        }
        if(found == true) {
            hit++;
        }
        else {
            Node newNode = new Node(key);
            newNode.next = null;
            newNode.prev = tail;
            if(tail != null) {
                tail.next = newNode;
            }
            else {
                head = newNode;
            }
            tail = newNode;
            cacheSize++;
            comparisons[i] = compCount;
        }
    }

    for(int x = 0; x < reqCount; x++) {
        System.out.print(comparisons[x] + " ");
    }
    System.out.println();
    System.out.println(hit + " h");
    printList(); //prints the updated list
}

这段代码有很多问题。如果未命中，我不会将其添加到前面，而是将键添加到 LinkedList 的尾部。另外，我还没有找到一种方法将 LinkedList 中的数字移动到头部。我认为这段代码可能是一个很好的起点，但我没有想法。

下面是双向链表的代码块:

class Node {

public int data; 
public Node next;
public Node prev;
public int freq;

     // constructor to create a new node with data equals to parameter i
     public Node (int i) {

        next = null;
        data = i;
        freq = 1;
     }
 }

我也不允许使用任何内置方法。我愿意接受任何想法和建议。谢谢!

编辑:比较数组是请求序列中每个请求的比较次数

编辑2:输出如下所示:

1 2 3 2 4 1
5 h
List: 20 30 10 5

第一行来自比较数组，第二行是命中总数，最后一行是更新的列表。

Answer 1

Instead of adding it to the front, I added the key to the tail of the LinkedList if it is a miss.

代码应如下所示:

if(found == true) {
    hit++;
} else {
    Node newNode = new Node(key);
    newNode.next = head;
    head.prev = newNode;
    cacheSize++;
    comparisons[i] = compCount;
}

Also, I have not found a way to move the number in the LinkedList to the head.

在以下循环之后:

for(int x = 0; x < reqCount; x++) {
    System.out.print(comparisons[x] + " ");
}

您需要输入以下代码:

for(int x = 0; x < reqCount; x++) {
    if(comparisons[x] > 1){
        int temp = cacheData[0];        
        for(int i = cacheSize - 1; i >= 1; i--) {
            cacheData[i] = cacheData[i-1];
        }
        cacheData[0] = reqData[i];
    }
}