Найдите ключ в списке идентификаторов LinkedList и добавьте ключ в начало списка, если его еще нет в заголовке.

Question

Мне нужна помощь: я делаю программу, которая обращается к списку и «ищет» int ID, идентичный его последовательности запросов.

Допустим, у меня есть кэш с 3 числами, 20 30 10.

Последовательность запросов с 6 номерами, 20 30 5 30 5 20.

Программа запускается с первого числа в последовательности запросов и go через кеш, сравнивая запрос с каждым номером в кеше, по одному и останавливается, если находит совпадение. Матч увеличит переменную 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

Вместо добавления его на передний план, я добавил ключ к хвосту LinkedList, если он отсутствует.

Код должен быть следующим:

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

Кроме того, я не нашел способа переместить число в LinkedList к голове.

После следующего l oop:

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