java – Linked list ordering

Question:

I'm doing a job that I need to create a linked list and sort it in ascending order, performing my tests I realized that I'm losing the reference to a node, the problem may be logical but I'm not able to find my error.

method for adding and sorting:

public void adiciona(Nodo novoNodo) {

    for (Nodo i = primeiroNodoDistancia; i != null; i = i
            .getProximoNodoDistancia()) {
        if (i.getDistancia() > novoNodo.getDistancia()) {
            novoNodo.setProximoNodoDistancia(i);
            if (i.getNodoAnteriorDistancia() != null) {
                novoNodo.setNodoAnteriorDistancia(i
                        .getNodoAnteriorDistancia());
                i.getNodoAnteriorDistancia().setProximoNodoDistancia(
                        novoNodo);
                i.setNodoAnteriorDistancia(novoNodo);
            } else {
                i.setNodoAnteriorDistancia(novoNodo);

            }
            if (i == primeiroNodoDistancia)
                primeiroNodoDistancia = novoNodo;
        }
        if (novoNodo.getDistancia() > i.getDistancia()) {
            novoNodo.setNodoAnteriorDistancia(i);
            if (i.getProximoNodoDistancia() != null) {
                novoNodo.setProximoNodoDistancia(i
                        .getProximoNodoDistancia());
                i.getProximoNodoDistancia().setNodoAnteriorDistancia(
                        novoNodo);
            }
            i.setProximoNodoDistancia(novoNodo);
        }

    }

}

My test code looks like this:

    c.adicionar(pedro, 50);
    System.out.println(c.imprimirListaDistancia());

    c.adicionar(joao, 20);
    System.out.println(c.imprimirListaDistancia());

    c.adicionar(maria, 10);
    System.out.println(c.imprimirListaDistancia());

Saida do Terminal:

 Pedro
 Joao Pedro
 Maria Pedro

I'm losing the reference to John who should be in the middle of the list…

Answer:

Your function has a problem which is that your for will run regardless of whether you have found the right position or not, the problem goes something like this:

  • Add pedro , it's empty so no problems

  • Add joao , falls to the first if, does what needs to be done and as there is no next for there.

  • Add maria , go to the first if, do what needs to be done, move to the next one and compare AGAIN with the newNode and start messing up your entire list.

I implemented a different way to add it, follows:

public void adicionar(Nodo novoNodo) {
    // está vazio, só adicionar e ir embora
    if (primeiroNodoDistancia == null) {
        primeiroNodoDistancia = novoNodo;
        return;
    }

    Nodo aux = primeiroNodoDistancia;
    Nodo anterior = null;
    // Procura a posição que o novo será adicionado
    while (aux != null) {
        if (aux.getDistancia() > novoNodo.getDistancia()) {
            break;
        }
        anterior = aux;
        aux = aux.getProximoNodoDistancia();
    }

    if (anterior == null) { // inserir no começo
        primeiroNodoDistancia.setNodoAnteriorDistancia(novoNodo);
        novoNodo.setProximoNodoDistancia(primeiroNodoDistancia);
        primeiroNodoDistancia = novoNodo;
    } else { // vai inserir entre o anterior e o aux (proximo)
        anterior.setProximoNodoDistancia(novoNodo);
        novoNodo.setNodoAnteriorDistancia(anterior);
        novoNodo.setProximoNodoDistancia(aux);

        if (aux != null) { // se for nulo ele é o ultimo
            aux.setNodoAnteriorDistancia(novoNodo);
        }
    }
}
Scroll to Top
AllEscort