My doubly chained list is not sorting

Question

My doubly chained list is not sorting

Navigation

#1 by (3 votes)

1

No Double Class

package ListaDuplamenteEncadeada;

public class NoDuplo {
    private Integer elemento;
    private NoDuplo anterior;
    private NoDuplo proximo;


    public NoDuplo(Integer elemento, NoDuplo anterior, NoDuplo proximo) {
        this.elemento = elemento;
        this.anterior= anterior;
        this.proximo = proximo;

    }

    public Integer getElemento() {
        return elemento;
    }
    public void setElemento(Integer elemento) {
        this.elemento = elemento;
    }
    public NoDuplo getAnterior(){
        return anterior;
    }
    public void setAnterior(NoDuplo anterior){
        this.anterior = anterior;
    }
    public NoDuplo getProximo() {
        return proximo;
    }
    public void setProximo(NoDuplo proximo) {
        this.proximo = proximo;
    }   
}

DoubleClass Class Enabled

package ListaDuplamenteEncadeada;

public class ListaDuplamenteEncadeada {
    private Integer tamanho;
    private NoDuplo header;
    private NoDuplo trailer;

    public ListaDuplamenteEncadeada() {
        tamanho = 0;
        header = new NoDuplo(null, null, null);
        trailer = new NoDuplo(null, null, null);
        header.setProximo(trailer);
        trailer.setAnterior(header);
    }

    public int getTamanho() {
        return tamanho;
    }

    public NoDuplo getPrimeiro() {
        if (tamanho == 0) {
            System.out.println("lista vazia");
            return null;
        }
        return header.getProximo();
    }

    public NoDuplo getUltimo() {
        if (tamanho == 0) {
            System.out.println("lista vazia");
            return null;
        }
        return trailer.getAnterior();
    }

    public void insereInicio(NoDuplo novoNo) {

        novoNo.setAnterior(header);
        novoNo.setProximo(header.getProximo());

        header.getProximo().setAnterior(novoNo);
        header.setProximo(novoNo);

        tamanho++;
        return;
    }

    public void insereFinal(NoDuplo novoNo) {
        novoNo.setAnterior(trailer.getAnterior());
        novoNo.setProximo(trailer);
        trailer.getAnterior().setProximo(novoNo);
        trailer.setAnterior(novoNo);

        tamanho++;
        return;
    }

    public void inserePos(NoDuplo novoNo, int pos) {
        if (pos < 1 || pos > tamanho + 1) {
            System.out.println("posi��o inv�lida");
            return;
        }
        if (tamanho == 0 || pos == 0) {
            insereInicio(novoNo);
            return;
        }
        if (pos == tamanho + 1) {
            insereFinal(novoNo);
            return;
        }

        NoDuplo aux = header.getProximo();
        for (int i = 1; i < pos; i++) {
            aux = aux.getProximo();
        }
        // novoNo REFERENCIA SEU PROXIMO E SEU ANTERIOR
        novoNo.setProximo(aux);
        novoNo.setAnterior(aux.getAnterior());

        // novoNo � REFERENCIADO PELO SEU ANTERIOR E PELO SEU PROXIMO
        aux.getAnterior().setProximo(novoNo);
        aux.setAnterior(novoNo);

        tamanho++;
    }

    public void removeInicio() {
        if (tamanho == 0) {
            System.out.println("lista vazia");
            return;
        }
        NoDuplo noRemovido = header.getProximo();
        header.setProximo(noRemovido.getProximo());
        header.getProximo().setAnterior(header);

        noRemovido.setAnterior(null);
        noRemovido.setProximo(null);

        tamanho--;
        return;
    }

    public void removeFim() {
        if (tamanho == 0) {
            System.out.println("lista vazia");
            return;
        }
        NoDuplo noRemovido = trailer.getAnterior();
        trailer.setAnterior(noRemovido.getAnterior());
        trailer.getAnterior().setProximo(trailer);

        noRemovido.setAnterior(null);
        noRemovido.setProximo(null);

        tamanho--;
    }

    public void removePos(int pos) {
        if (pos < 1 || pos > tamanho) {
            System.out.println("posi��o inv�lida");
            return;
        }

        if (pos == 1) {
            removeInicio();
            return;
        }

        if (pos == tamanho) {
            removeFim();
            return;
        }

        NoDuplo noRemovido = header.getProximo();
        for (int i = 1; i < pos; i++)
            noRemovido = noRemovido.getProximo();

        noRemovido.getAnterior().setProximo(noRemovido.getProximo());
        noRemovido.getProximo().setAnterior(noRemovido.getAnterior());

        noRemovido.setAnterior(null);
        noRemovido.setProximo(null);
        tamanho--;
    }

    public void ordenarLista() {
        NoDuplo atual = header.getProximo();
        NoDuplo prox = atual.getProximo();

        System.out.println("Atual antes do for " + atual.getElemento());
        System.out.println("Prox Antes do for " + prox.getElemento());

        NoDuplo cpAtual = atual;
        System.out.println("Cpatual antes do For " + cpAtual.getElemento());

        for (int i = 0; i < tamanho - 1; i++) {

            for (int j = i + 1; j < tamanho; j++) {
                if (atual.getElemento() > prox.getElemento()) {
                    cpAtual.setElemento(atual.getElemento());
                    System.out.println("Cp atual dentro do FOR j + if " + cpAtual.getElemento());
                    atual.setElemento(prox.getElemento());
                    System.out.println("Atual dentro do FOR J + if " + atual.getElemento());
                    prox.setElemento(cpAtual.getElemento());
                    System.out.println("Prox Dentro do FOR J + if " + prox.getElemento());
                }
                prox = prox.getProximo();
                System.out.println("Prox DENTRO DO FOR J sem IF " + prox.getElemento());
            }
            atual = atual.getProximo();
            System.out.println("Atual dentro do FOR I " + atual.getElemento());
            prox = atual.getProximo();
            System.out.println("Prox dentro do FOR I " + prox.getElemento());
            cpAtual = atual;
            System.out.println("Cpatual dentro do FOR I " + cpAtual.getElemento());

        }

    }

    public void imprimeLista() {
        if (tamanho == 0) {
            System.out.println("lista vazia");
        }
        NoDuplo aux = header.getProximo();
        System.out.println("------------- LISTA ATUAL -----------");
        for (int i = 0; i < tamanho; i++) {
            System.out.print(" -> " + aux.getElemento() + "\t");
            aux = aux.getProximo();
        }

        System.out.println();
    }
}

He is not ordering it, it is not changing the reference of the smallest value.

java lista

asked by anonymous 29.07.2017 / 16:56

1 answer

Click event does not work in custom control Why does the "container" class in Bootstrap leave side spaces on the page? This is normal?

score 3 · Accepted Answer

What makes sorting not work is swap ) of values within the second for that is not correct. Let's not forget that an exchange of values between two variables always involves a third temporary variable.

Something like:

int x = ...;
int y = ...;

//troca 
int temp = x;
x = y;
y = temp;

That's not what's done here (cutting System.out to be short):

for (int j = i + 1; j < tamanho; j++) {
    if (atual.getElemento() > prox.getElemento()) {
        cpAtual.setElemento(atual.getElemento());                 
        atual.setElemento(prox.getElemento());  
        prox.setElemento(cpAtual.getElemento());                    
    }
    ...
}

Where atual and cpAtual are actually the same node:

...
System.out.println("Prox dentro do FOR I " + prox.getElemento());
cpAtual = atual;
...

Soon to change one also changes another. In addition, the cpAtual itself is not necessary for the sort method, which can only be done with atual and proximo , like this:

public void ordenarLista() {
    NoDuplo atual = header.getProximo();
    NoDuplo prox = atual.getProximo();

    for (int i = 0; i < tamanho - 1; i++) {
        for (int j = i + 1; j < tamanho; j++) {
            if (atual.getElemento() > prox.getElemento()) {
                //a troca de variaveis agora de forma correta
                Integer temp = atual.getElemento(); //temp = x
                atual.setElemento(prox.getElemento()); // x = y
                prox.setElemento(temp); // y = temp
            }

            prox = prox.getProximo();
        }

        atual = atual.getProximo();
        prox = atual.getProximo();
   }

}

I also chopped the System.out for readability.

Two additional important notes:

The header and trailer node are already nodes and therefore have values, it also has a elemento , however they are never used! Because any navigation in the list starts at the next header:

public NoDuplo getPrimeiro() {
    if (tamanho == 0) {
       ...
    }
    return header.getProximo();
}

Or the previous trailer:

public NoDuplo getUltimo() {
    if (tamanho == 0) {
       ...
    }
    return trailer.getAnterior();
}

This means that there are always two empty nodes in the list.

The encapsulation concepts are not correctly applied because you can not insert an element into the list without using the NoDuplo class:

public void insereInicio(NoDuplo novoNo)
public void insereFinal(NoDuplo novoNo)
public void inserePos(NoDuplo novoNo, int pos)

This forces the code that uses the list to depend directly on the NoDuplo class and consequently on its implementation. It is not possible, for example, to change the implementation to a NoSimples without changing the code used by the list.

Instead the class should only get the elements and create the nodes inside the addition methods, like this:

public void insereFinal(Integer novoElemento) {
    NoDuplo novoNo = new NoDuplo(novoElemento, null, null);
    ...
}

And to complement a constructor of NoDuplo that put the two references to null also helped a lot to be even simpler and to be able to do:

NoDuplo novoNo = new NoDuplo(novoElemento);