Ordenar lista com ponteiros (hipotéticos) em Java

[krafterwerk 0]

Olá.

Sou um iniciante em Java e nas últimas horas vim resolvindo exercícios sobre ponteiros hipotéticos em Java. Digo hipotéticos pois apontam para valores anteriores/posteriores na memória, mas como é Java, não são endereços de memória explícitos.

O primeiro exercício já está okay, era sobre formular uma lista encadeada e não ordenada. Agora, estou me quebrando pra ordenar esta lista para imprimir na tela depois (tanto em ordem crescente quanto decrescente). Apreciaria muito a ajuda de alguém pois já estou tentando fazer isso a horas e não cheguei em nenhuma solução.

package lista; 

import java.util.*; 

public class Lista { 


 private static class lista 

 { 

 public int num; 

 public lista prox; // prox - ponteiro para proximo endereço 


 } 

 public static void main(String[] args) 

 { 

 Scanner entrada = new Scanner(System.in); 

 lista inicio = null; 

 lista fim = null; 

 lista aux; 

 lista anterior; 

 int op, numero, achou; 

 do{ 

 System.out.println("\nMenu de opções\n"); 

 System.out.println("1-Inserir no início da lista"); 

 System.out.println("2-Inserir no fim da lista"); 

 System.out.println("3-Consultar toda lista"); 

 System.out.println("4-Remover da lista"); System.out.println("5-Esvaziar a lista"); 

 System.out.println("6-Sair"); 

 System.out.print("Digite sua opção: ");

 op = entrada.nextInt(); 

 if(op < 1||op>6) 

 { 

 System.out.println("Opção inválida!"); 

 } 

 if(op == 1) 

 { 

 System.out.println("Digite o número a ser inserido no inicio da lista:"); 

 lista novo = new lista(); 

 novo.num = entrada.nextInt(); 

 if(inicio == null) 

 { 

 inicio = novo; 

 fim = novo; 

 novo.prox = null; 

 } 

 else 

 { 

 novo.prox = inicio; 

 inicio = novo; 

 } 

 System.out.println("Número inserido no inicio da lista!"); 

 } 

 if(op == 2) 

 { 

 System.out.println("Digite o número a ser inserido no fim da lista:"); 

 lista novo = new lista(); 

 novo.num = entrada.nextInt(); 

 if(inicio == null) 

 { 

 inicio = novo; 

 fim = novo; 

 novo.prox = null; 

 } 

 else 

 { 

 fim.prox = novo; 

 fim = novo; 

 novo.prox = null; 

 } 

 System.out.println("Número inserido no fim da lista!"); 

 } 

 if(op == 3) 

 { 

 if(inicio == null) 

 { 

 System.out.println("Lista está vazia!"); 

 } 

 else 

 { System.out.println("\nConsultando toda a lista\n"); 

 aux = inicio; 

 while(aux!=null) 

 { 

 System.out.print(aux.num+ " "); 

 aux = aux.prox; 


 } 

 } 

 } 

 if(op == 4) 

 { 

 if(inicio == null) 

 { 

 System.out.println("Lista está vazia!"); 

 } 

 else 

 { 

 System.out.println("\nDigirte o número a ser removido:\n"); 

 numero = entrada.nextInt(); 

 aux = inicio; 

 anterior = null; 

 achou = 0; 


 while(aux!=null) 

 { 

 if(aux.num == numero) 

 { 

 achou = achou +1; 

 if(aux == inicio) 

 { 

 inicio = aux.prox; 

 aux = inicio; 

 } 

 else if(aux == fim) 

 { 

 anterior.prox = null; 

 fim = anterior; 

 aux = null; 

 } 

 else 

 { 

 anterior.prox =aux.prox; 

 aux = aux.prox; 

 } 

 } 

 else 

 { 

 anterior = aux; 

 aux =aux.prox; 

 } 

 } 

 if(achou ==0) { 

 System.out.append("Número não encontrado!"); 

 } 

 else if(achou ==1) 

 { 

 System.out.append("Número removido uma vez!"); 

 } 

 else 

 { 

 System.out.append("Número removido "+achou+" vezes!"); 

 } 

 } 

 } 

 if(op == 5) 

 { 

 if(inicio == null) 

 { 

 System.out.println("Lista vazia!"); 

 } 

 else 

 { 

 inicio = null; 

 System.out.println("Lista esvaziada!"); 

 } 

 } 

 }while(op !=6); 

 } 

}

[Leonardo Leal 4]

Boa noite,

Deve ser tarde para lhe ajudar no seu trabalho, mas não para aprender.

Sou iniciante em java também e também acabei de fazer um trabalho sobre isto...

Bem, acho que esta faltando um pouco de OO ai e penso que está querendo fazer a tal da lista duplamente encadeada.

No site caelum ( http://www.caelum.com.br/apostila-java-estrutura-dados/listas-ligadas/ ) tem uma explicação excelente.

Quanto a ela ser ordenada, já que a lista encadeada não seria a melhor opção para este tipo de operação, é só fazer a leitura até achar a posição correta onde inserir o elemento e a lista não deve conter os métodos para inserir no final nem no início, ou seja, somente inserir.

Para melhorar a busca e inserção da para usar a busca binária.

 

Espero ter contribuído.