Invert simply chained list

Question

I did the implementation of a chained list and the method to list the elements, but I now wanted to print it upside down (For example: 1>2>3 = 3>2>1). Could someone help me?

//iniciamente a minha lista não aponta para lugar algum
public static Nodo inicio = null;

public static void print() {

    if (inicio == null) {
        System.out.println("Nada a exibir - a lista está vazia!");
    } else {
        Nodo aux = inicio;
        while (aux != null) {
            System.out.print(aux.getChave() + " ");
            aux = aux.getProx();
        }
    }
}

public void inserir(int e) {
    //criar um novo Nodo
    Nodo novo = new Nodo();
    novo.setChave(e);    //inserindo elemento
    novo.setProx(null); //depois dele não vem ninguém

    if (inicio == null) {
        inicio = novo; //aponto para o novo nodo
    } else {     //ja tem gente na lista ai precisa percorrer até chegar na null
        Nodo aux = inicio; //joga o aux no inicio
        while (aux.getProx() != null) {
            aux = aux.getProx();
        }
        aux.setProx(novo);
    }
}

The implementation of the class Nodo is the following:

public class Nodo {

    public int chave;
    public Nodo prox;
    public Nodo ant;

    //+ métodos acessores
}

Answer 1

An alternative is to first invert the list by using this algorithm:

public void inverter() {
    Nodo prev = null;
    Nodo next = null;
    Nodo current = inicio;
    while (current != null) {
        next = current.getProx();
        current.setProx(prev);
        prev = current;
        current = next;
    }
    inicio = prev;
}

Basically, you start from the beginning and iterate in the list, and with each node you make the element N next to the element N + 1. Finally, the beginning of the list becomes the last node found. Note that if the list is empty (i.e., if inicio for null), he doesn’t even get into the while, and at the end, the beginning remains null (the list will continue - correctly - empty).

To better understand how this algorithm works:

After reversing the list, just print it out normally using the method print().

---

Without having to invert the list

Another alternative, but without having to invert the list, is to print it recursively:

public void printInvertido(Nodo nodo) {
    if (nodo != null) {
        printInvertido(nodo.getProx());
        System.out.print(nodo.getChave() + " ");
    }
}

In this case, do not need to invert the list, just call printInvertido(inicio). Recursive calls are being made to all elements of the list, and as the printing only occurs after these, the elements are printed in reverse order.

Obs: the above method does not deal with the case of the empty list, so just create one more method to treat this case:

public void printInvertido() {
    if (inicio == null) {
        System.out.println("Nada a exibir - a lista está vazia!");
    } else {
        printInvertido(inicio);
    }
}

So just call printInvertido() directly. If the list is empty, print the specific message. If it is not empty, call the recursive method, which prints the inverted list.

Remembering that if the list is too large, this whole amount of recursive calls can cause a StackOverflowError.

---

Another alternative: turn the list into double chained

How about taking advantage of your class Nodo also has a reference to the previous element? IE, let’s make it double chained - I’m assuming the field ant was not created for no reason.

In your current code you do not use the reference for the previous one, so a few adjustments would be enough to use this information. For example, a class could be created Lista thus:

public class Lista {

    private Nodo inicio = null;
    private Nodo fim = null;

    public void inserir(int e) {
        Nodo novo = new Nodo(e);
        if (inicio == null) {
            inicio = fim = novo; // aponto para o novo nodo
        } else { // insere no final
            fim.setProx(novo);
            novo.setAnt(fim);
            fim = novo;
        }
    }

    public void print(boolean invertido) {
        if (inicio == null) {
            System.out.println("Nada a exibir - a lista está vazia!");
        } else {
            // se for invertido, começa do final, senão, começa do início
            Nodo aux = invertido ? fim : inicio;
            while (aux != null) {
                System.out.print(aux.getChave() + " ");
                // se for invertido, vai para o anterior, senão, vai para o próximo
                aux = invertido ? aux.getAnt() : aux.getProx();
            }
        }
    }
}

And in class Nodo, I added this builder:

public Nodo(int chave) {
    this.chave = chave;
    this.prox = null;
    this.ant = null;
}

'Cause it seems to me there’s no point in creating a Nodo whose key has no value, so there would be no need to exist the constructor without arguments (because in your code you create a Nodo and then arrow the value of the key, but if it is mandatory, why not keep only a constructor that forces you to pass this value?). Just create builders that make sense.

Now I have the beginning and the end of the list, and the method inserir always inserts at the end, ie right after fim. See that I set the references to the next and the previous, so the list will be double linked.

Already in the method print() i pass a parameter indicating whether to print upside down or not. Depending on the value of this boolean, i start from the beginning or end of the list, and while i advance to the previous or to the next (in case, invertido ? fim : inicio means that if invertido for true, I use the fim, and if it is false, I use the inicio - the same logic applies to determine whether I take the next or the previous).

So if I call print(false), it prints the list in the normal order, and print(true) prints in reverse order. Ex:

Lista list = new Lista();
for (int i = 0; i < 10; i++) {
    list.inserir(i);
}
System.out.println("Ordem normal: ");
list.print(false);

System.out.println("\nInvertida: ");
list.print(true);

Exit:

Ordem normal: 
0 1 2 3 4 5 6 7 8 9 
Invertida: 
9 8 7 6 5 4 3 2 1 0