Know the most repetitive code in a data structure (list)

Question

I’m doing a project in Java of data structures and I have a list simply chained that gets the code, name, sex and course of each person. I only need to validate which code (whole type) repeats the most times and display the last value of the list with this code. In case of a tie in the number of repetitions, I show the last one that was inserted with this code. The logic is SIMPLE, but I’m not able to develop it in this type (lists).

This is my code, remembering that aux and comp are the nodes. The tamanho() is a method that returns the number of people on the list, and the method mostra_noh is to show the value I want.

public void consultar_repeticao()
{

    Noh aux = null;
    Noh comp = null;
    int p = 0;
    int q = 0;
    int cont = 0;

    for (aux = this.primeiro, p = 1;
         aux != null && p <tamanho();
         aux = aux.getProximo(), p++) {

        for (comp = this.primeiro.getProximo(), q = 2;
             comp != null &&  q <=tamanho();
             comp = comp.getProximo(), q++) {

            if(aux.getCodigo()==comp.getCodigo()){
                cont++;
            }

         };
    };
    aux.mostra_noh(q);
}

Answer 1

Your problem is that you have a single variable (cont) which is incremented every time two codes are equal. Every time any codes are the same. If the code a repeat 10 times and the b repeat 2 times, cont will be 12. That doesn’t tell you anything about which one repeats the most, or which node has that repeated code.

To solve this, I suggest storing in another data structure a list with the following values:

• repeated code
• how many times it repeats
• which last node has that code

Since this structure can start empty - or with all the codes in the list, repeated zero times, with last node null (is at your discretion). Clarify: these values must exist for each code. The data structure is up to you, but as you are studying chained lists, I suggest using another chained list to store these values (and duplicate your suffering rsrs).

Let me give you an example using arrays:

class Repeticao {
    int codigo;
    int quantasVezes = 0;
    int ultimoNoh = -1;
}

Repeticao[] repeticoes = new Repeticao[max_nos];
// Popular o array com objetos Repeticao, um para cada código

void incrementarRepeticao(int codigo, int ultimoNoh) {
    for ( int i = 0 ; i < repeticoes.length ; i++ )
        if ( repeticoes[i].codigo == codigo ) {
            repeticoes[i].quantasVezes++;
            if ( ultimoNoh > repeticoes[i].ultimoNoh )
                repeticoes[i].ultimoNoh = ultimoNoh;
        }
}

int maiorRepeticao() {
    Repeticoes maior = repeticoes[0];
    for ( int i = 1 ; i < repeticoes.length ; i++ )
        if ( repeticoes[i].quantasVezes > maior.quantasVezes )
            maior = repeticoes[i];
    return maior.ultimoNoh;
}

---

In addition, there are other problems in your code that may be making it difficult to arrive at an answer:

for (aux = this.primeiro, p = 1;
        aux != null && p <tamanho();

What happens if you only have 1 element in your list? It won’t even enter the loop... I think that’s exactly what you want (because if you only have one element, you don’t need to compare it with anyone), but it’s good to remember that other variables - like q - have not been initialized in that case (i.e. still have the initial value of 0).

    for (comp = this.primeiro.getProximo(), q = 2;
        comp != null &&  q <=tamanho();

The problem here is that it will always start from the second element forward - even if aux for the second itself! The ideal is to start from the next list element - the one in front of the aux

// Sugestão: modificar o código acima para:
    for (comp = aux.getProximo(), q = p + 1;
        comp != null &&  q <=tamanho();

That is, the element 1 will compare with the 2, 3, 4... the element 2 will compare with the 3, 4... and so on, down to the last element - that won’t compare to anyone.

aux.mostra_noh(q);

Here, what you want to show is not the q (for that will always be 0 or tamanho()), but yes the last element with more repetitions. If in this code snippet you update the suggested data structure at the beginning of the answer:

        if(aux.getCodigo()==comp.getCodigo()){
            //cont++;

            // Procura `aux.getCodigo()` na estrutura de dados
            // Incrementa o número de repetições
            // Atribui o último nó, que nesse caso é `comp` (o de maior índice)
            incrementarRepeticao(aux.getCodigo(), q);
        }

Then at the end you have to go through this structure to get the highest value, and print the corresponding node (or sort the list in descending order and pick the first value at your discretion).

aux.mostra_noh(maiorRepeticao());