java - Inverter lista simplesmente encadeada - Stack Overflow em Português
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;
System.out.println("Nada a exibir - a lista está vazia!");
Nodo aux = inicio;
System.out.print(aux.getChave() + " ");
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
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.setProx(novo);
A implementação da classe Nodo é a seguinte:
public int chave;
public Nodo prox;
public Nodo ant;
//+ métodos acessores
java lista-encadeada
editada 21/08/2019 às 16:37
perguntada 20/08/2019 às 17:40
Rodrigo ValleRodrigo Valle
691010 medalhas de bronze
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.
Faltam informações, não sei como o Nodo foi implementado.
20/08/2019 às 18:32
Pronto, atualizei!
– Rodrigo Valle
20/08/2019 às 19:04
Uma alternativa é primeiro inverter a lista, usando este algoritmo:
public void inverter() {
Nodo prev = null;
Nodo next = null;
Nodo current = inicio;
next = current.getProx();
current.setProx(prev);
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:
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) {
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() {
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:
private Nodo inicio = null;
private Nodo fim = null;
Nodo novo = new Nodo(e);
inicio = fim = novo; // aponto para o novo nodo
} else { // insere no final
fim.setProx(novo);
novo.setAnt(fim);
public void print(boolean invertido) {
// se for invertido, começa do final, senão, começa do início
Nodo aux = invertido ? fim : inicio;
// 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:
list.inserir(i);
System.out.println("Ordem normal: ");
list.print(false);
System.out.println("\nInvertida: ");
list.print(true);
Ordem normal:
editada 21/08/2019 às 20:44
respondida 21/08/2019 às 16:36
Adorei o gif da inversão!
22/08/2019 às 1:33
@JeffersonQuesado Esse gif é muito bom, né? Teria sido muito mais legal se minhas aulas de estruturas de dados tivessem sido com gifs...
Sanou todas as minhas duvidas, perfeito!
20/09/2019 às 17:39
Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag java lista-encadeada ou faça sua própria pergunta.