Como ordenar uma lista ligada no Java

Escrito por ehow contributor | Traduzido por rodrigo castilhos
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como ordenar uma lista ligada no Java
Organizando a lista lincada no Java (interrogation image by danimages from Fotolia.com)

Como organizar uma lista lincada no Java. Uma lista lincada é um dos principais tipos de estruturas de dados no mundo da programação. É uma organização de nós que contém dados e referências apontando para o próximo nó. Para ordenar uma lista lincada no Java, há uma classe de lista que funciona com o framework Collections, que implementa algoritmos como uma ordenação.

Nível de dificuldade:
Moderado

Outras pessoas estão lendo

Instruções

    Ordenar uma lista lincada no Java

  1. 1

    Declare a lista ligada criando um novo objeto LinkedList e atribuindo uma variável LinkedList. Uma LinkedList vem da classe genérica List, então qualquer método que aceita uma List também será aceito pelo objeto LinkedList. ""LinkedList l = new LinkedList();""

  2. 2

    Adicione objetos do mesmo tipo (tais como inteiros) à lista. Estes podem ser objetos de qualquer tipo, mas para poder ordenar a lista lincada, todos devem ser do mesmo tipo.

  3. 3

    Use o método List.addFirst para inserir novos objetos no início da lista, de modo que quaisquer objetos que adicionar fiquem na ordem contrária. Se quiser adicioná-los ao final da lista, use o método List.addLast. ""list.addFirst(1);list.addFirst(3);list.addFirst(2);""

  4. 4

    Use um iterator para iterá-los na lista e os imprima antes e depois de ver o que o método de ordenação estiver fazendo. ""for( Iterator i = list.iterator(); i.hasNext(); ) { System.out.println(i.next());}""

    Ordenar usando os comparadores predeterminados e personalizados

  1. 1

    Ordene a lista com o comparador predeterminado. Um comparador é um objeto que compara dois objetos. O objeto comparador predeterminado usa o operador menor, então a lista estará ordenada em ordem crescente. Para ordenar a lista, use o método estático Collections.sort. ""Collections.sort(list);""

  2. 2

    Ordene a lista com um comparador personalizado escrevendo uma classe que implemente uma interface de comparação e passe-a a uma instância como argumento da ordenação. A classe que implementa o comparador tem somente que implementar o método simples "compare". ""public class GreaterThan implements Comparator else if(x == y) {return 0;} else {return 1;}}}""

  3. 3

    Use a chamada para Collections.sort passando por uma nova instância de GreaterThan como um segundo argumento. Uma vez que os objetos que são maiores ficarão na frente dos demais, a lista estará ordenada de forma decrescente ao invés da ordem crescente. Como alternativa, se for ordenar uma lista de objetos de uma classe personalizada que você mesmo escreveu, essa classe pode implementar a interface Comparable ao invés de usar a classe Comparador separada. ""Collections.sort(list, new GreaterThan());""

Dicas & Advertências

  • É problemático usar um inteiro para iterar no circuito e o método List.size(). Iterar uma lista lincada é uma operação computacional cara. Quando se usa um operador de índice (como l[2]) como se faz em qualquer comando, o Java tem que iterar sobre a lista até chegar ao índice 2. Para pequenas listas, isto é um problema, porém, com algo grande, usar o operador de índice para iterar se transforma em algo que requer muitos recursos.
  • Não importa como esteja implementado o objeto List, já que LinkedList implementa a mesma interface.
  • O método de comparação deve retornar à -1 se arg0 for ordenado antes que arg1, 0 se for ordenado de forma igual e 1 se arg1 for ordenado antes que arg0.
  • O objeto iterador assegura que cada nó da lista se visite somente uma vez. Isto é algo importante para relembrar, já que visitar nós sem necessidade pude abusar das estruturas de dados até o ponto em que o programa tenha mau funcionamento.

Não perca

Referências

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível