Chain list ordering

Question

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

method to add and sort:

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());

Departure from the Terminal:

 Pedro
 Joao Pedro
 Maria Pedro

I’m missing the reference to the Joao that should be in the middle of the list..

Answer 1

Your function has a problem is that your for will run whether you have found the right position or not, the problem happens more or less like this:

• Add peter, is empty so no problems

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

• Add maria, falls in the first if, does what needs to be done, passes to the next and compares AGAIN with the new and starts messing up your whole list.

I implemented a different way to add, 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);
        }
    }
}