My double chained list is not ordering

Question

Class On Double

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

Double Chained Listed Class

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’s not ordering it, he’s not changing the reference of the lowest value.

Answer 1

What makes the ordination not work is the exchange (swap) of values within the second for that is not correct. We must not forget that an exchange of values between two variables always involves a temporary third variable.

Something like:

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

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

That’s not what’s done here (cutting the 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());                    
    }
    ...
}

In which atual and cpAtual are actually the same knot:

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

Then exchange one also exchange another. Moreover the own cpAtual is not necessary for the sorting method and can only be done with the atual and the proximo, thus:

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 cut the System.out legibility.

Two additional important notes:

1. The knot header and trailer are already us and so has values, also has a elemento, however these are never used! Because any browsing in the list starts at the next header:

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

   Or the one before the trailer:

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

   Which means there are always two blank nodes on the list.

2. Encapsulation concepts are not correctly applied as it is not possible to insert an element in the list without using the class NoDuplo:

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

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

   Instead the class should receive only the elements and create the nodes within the addition methods, this way:

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

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

   NoDuplo novoNo = new NoDuplo(novoElemento);