在 ID 的 LinkedList 中搜索键，如果键不在列表的头部，则将其添加到列表的头部

Question

我需要一些帮助：我正在制作一个访问列表和 "looks for" 与其请求序列相同的 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;
     }
 }

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

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

编辑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];
    }
}

在 ID 的 LinkedList 中搜索键，如果键不在列表的头部，则将其添加到列表的头部

Search for key in a LinkedList of IDs and add key to the head of the list if it is not already at the head

java

doubly-linked-list