Sorting list

Question

Sorting list

Navigation

#1 by (2 votes)

3

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

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

Terminal exit:

 Pedro
 Joao Pedro
 Maria Pedro

I'm missing the reference to John who should be in the middle of the list ..

java lista

asked by anonymous 28.06.2015 / 22:34

1 answer

Complex mapping Entity Framework Multi-language system

score 2 · Accepted Answer

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

Add pedro , then it is empty so no problem
Add joao , falls into the first if, does what needs to be done, and has no nearness to it.
Add Marie , falls into the first if, does what needs to be done, moves on to the next, and compares AGAIN with newNode and start messing up your entire list.

I've implemented a different way to add it:

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