3

Fiz a implementação de uma lista encadeada e o método para listar os elementos, mas queria agora printar ela invertida (Por exemplo: 1>2>3 = 3>2>1). Alguém poderia me ajudar?

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

A implementação da classe Nodo é a seguinte:

public class Nodo {

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

    //+ métodos acessores
}
3
  • 1
    Coloca um print depois do metodo recursivo, assim ele vai printar de trás pra frente. Se colocar o print antes do metodo recursivo, ele vai printar na ordem. 20/08/2019 às 17:47
  • Faltam informações, não sei como o Nodo foi implementado.
    – Scarabelo
    20/08/2019 às 18:32
  • Pronto, atualizei! 20/08/2019 às 19:04

1 Resposta 1

3

Uma alternativa é primeiro inverter a lista, usando este algoritmo:

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

Basicamente, você parte do início e vai iterando na lista, e a cada nó você faz o elemento N ser o próximo do elemento N + 1. Por fim, o início da lista passa a ser o último nó encontrado. Repare que se a lista for vazia (ou seja, se inicio for null), ele nem entra no while, e ao final, o início continua sendo null (a lista continuará - corretamente - vazia).

Para entender melhor como esse algoritmo funciona:

inverter lista ligada

Depois de inverter a lista, basta imprimí-la normalmente, usando o método print().


Sem precisar inverter a lista

Outra alternativa, mas sem precisar inverter a lista, é imprimí-la recursivamente:

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

Neste caso, não precisa inverter a lista, basta chamar printInvertido(inicio). As chamadas recursivas vão sendo feitas para todos os elementos da lista, e como a impressão só ocorre depois destas, os elementos são impressos na ordem inversa.

Obs: o método acima não trata o caso da lista vazia, então bastaria criar mais um método para tratar este caso:

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

Assim, basta chamar printInvertido() diretamente. Se a lista for vazia, imprime a mensagem específica. Caso não seja vazia, chama o método recursivo, que imprime a lista invertida.

Lembrando que, caso a lista seja muito grande, essa quantidade toda de chamadas recursivas pode causar um StackOverflowError.


Outra alternativa: transformar a lista em duplamente encadeada

Que tal aproveitar que a sua classe Nodo também possui uma referência para o elemento anterior? Ou seja, vamos torná-la duplamente encadeada - estou assumindo que o campo ant não foi criado à toa.

No seu código atual você não usa a referência para o anterior, então bastariam alguns ajustes para usar esta informação. Por exemplo, poderia ser criada uma classe Lista assim:

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

E na classe Nodo, acrescentei este construtor:

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

Pois me parece que não faz sentido criar um Nodo cuja chave não tenha algum valor, então não teria necessidade de existir o construtor sem argumentos (pois no seu código você cria um Nodo e depois seta o valor da chave, mas se este é obrigatório, por que não manter apenas um construtor que obriga a passar este valor?). Só crie construtores que façam sentido.

Agora eu tenho o início e o fim da lista, e o método inserir sempre insere no final, ou seja, logo depois de fim. Veja que eu acerto as referências para o próximo e o anterior, assim a lista será duplamente ligada.

Já no método print() eu passo um parâmetro indicando se deve imprimir invertido ou não. Dependendo do valor deste booleano, eu começo do início ou do fim da lista, e no while eu avanço para o anterior ou para o próximo (no caso, invertido ? fim : inicio significa que, se invertido for true, eu uso o fim, e se for false, eu uso o inicio - a mesma lógica vale para determinar se eu pego o próximo ou o anterior).

Sendo assim, se eu chamar print(false), ele imprime a lista na ordem normal, e print(true) imprime na ordem inversa. 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);

Saída:

Ordem normal: 
0 1 2 3 4 5 6 7 8 9 
Invertida: 
9 8 7 6 5 4 3 2 1 0 
3
  • 1
    Adorei o gif da inversão! 22/08/2019 às 1:33
  • 1
    @JeffersonQuesado Esse gif é muito bom, né? Teria sido muito mais legal se minhas aulas de estruturas de dados tivessem sido com gifs...
    – hkotsubo
    22/08/2019 às 10:41
  • 1
    Sanou todas as minhas duvidas, perfeito! 20/09/2019 às 17:39

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .