在ID的LinkedList中搜索关键字，如果尚未在列表的开头，则将其添加到列表的开头

Question

我需要一些帮助：我正在制作一个程序，该程序可访问列表并“寻找”与其请求顺序相同的int ID。

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

具有6个数字的请求顺序，20 30 5 30 5 20。

程序将从请求序列中的第一个数字开始，然后通过缓存，将请求与缓存中的每个数字进行比较，一次比较一个，如果找到匹配项则停止。匹配将增加变量hit。变量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;
     }
 }

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

Answer 1

不是将其添加到前面，而是将密钥添加到了LinkedList如果错过了。

代码应如下：

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