Por que não há SortedList em Java?

Em Java, existem as interfaces SortedSet e SortedMap . Ambas pertencem à estrutura de Coleções padrão do Java e fornecem uma maneira classificada para acessar os elementos.

No entanto, no meu entendimento, não há SortedList em Java. Você pode usar java.util.Collections.sort() para classificar uma lista.

Alguma idéia de por que ele é projetado assim?

Os iteradores de lista garantem, em primeiro lugar, que você obtenha os elementos da lista na ordem interna da lista ( ordem de inserção ). Mais especificamente, é na ordem em que você inseriu os elementos ou em como você manipulou a lista. A sorting pode ser vista como uma manipulação da estrutura de dados e existem várias maneiras de classificar a lista.

Vou ordenar os caminhos na ordem de utilidade, como eu pessoalmente vejo:

1. Considere usar collections Set ou Bag

NOTA: Eu coloquei esta opção no topo porque é isso que você normalmente quer fazer de qualquer maneira.

Um conjunto classificado classifica automaticamente a coleção na inserção , o que significa que ela faz a sorting enquanto você adiciona elementos à coleção. Isso também significa que você não precisa classificá-lo manualmente.

Além disso, se você tiver certeza de que não precisa se preocupar com (ou ter) elementos duplicados, use o TreeSet . Ele implementa as interfaces SortedSet e NavigableSet e funciona como você provavelmente esperaria de uma lista:

 TreeSet set = new TreeSet(); set.add("lol"); set.add("cat"); // automatically sorts natural order when adding for (String s : set) { System.out.println(s); } // Prints out "cat" and "lol" 

Se você não quiser a ordenação natural, você pode usar o parâmetro construtor que usa um Comparator .

Como alternativa, você pode usar Multisets (também conhecido como Bags ) , que é um Set que permite elementos duplicados, e há implementações de terceiros deles. Mais notavelmente das bibliotecas Guava existe um TreeMultiset , que funciona muito parecido com o TreeSet .

2. Classifique sua lista com Collections.sort()

Como mencionado acima, a sorting de List s é uma manipulação da estrutura de dados. Assim, para situações em que você precisa de “uma fonte de verdade” que será classificada de várias maneiras, classificá-la manualmente é o caminho a seguir.

Você pode classificar sua lista com o método java.util.Collections.sort() . Aqui está um exemplo de código sobre como:

 List strings = new ArrayList() strings.add("lol"); strings.add("cat"); Collections.sort(strings); for (String s : strings) { System.out.println(s); } // Prints out "cat" and "lol" 

Usando comparadores

Um claro benefício é que você pode usar o Comparator no método de sort . O Java também fornece algumas implementações para o Comparator , como o Collator que é útil para sequências de sorting sensíveis ao Collator idioma. Aqui está um exemplo:

 Collator usCollator = Collator.getInstance(Locale.US); usCollator.setStrength(Collator.PRIMARY); // ignores casing Collections.sort(strings, usCollator); 

Classificando em ambientes simultâneos

Observe que o uso do método de sort não é amigável em ambientes simultâneos, já que a instância de coleção será manipulada e você deve considerar o uso de collections imutáveis. Isso é algo que a Guava fornece na class Ordering e é um simples one-liner:

 List sorted = Ordering.natural().sortedCopy(strings); 

3. Enrole sua lista com java.util.PriorityQueue

Embora não haja uma lista classificada em Java, existe uma fila ordenada que provavelmente funcionaria bem para você. É a class java.util.PriorityQueue .

Nico Haase vinculado nos comentários a uma questão relacionada que também responde a isso.

Em uma coleção ordenada, você provavelmente não quer manipular a estrutura de dados interna, razão pela qual PriorityQueue não implementa a interface List (porque isso lhe daria access direto aos seus elementos).

Advertência no iterador PriorityQueue

A class PriorityQueue implementa as Iterable e Collection para que possam ser iteradas normalmente. No entanto, o iterador não é garantido para retornar elementos na ordem classificada. Em vez disso (como Alderath aponta nos comentários), você precisa poll() a fila até esvaziar.

Observe que você pode converter uma lista em uma fila de prioridades por meio do construtor que recebe qualquer coleção :

 List strings = new ArrayList() strings.add("lol"); strings.add("cat"); PriorityQueue sortedStrings = new PriorityQueue(strings); while(!sortedStrings.isEmpty()) { System.out.println(sortedStrings.poll()); } // Prints out "cat" and "lol" 

4. Escreva sua própria class SortedList

NOTA: Você não deveria ter que fazer isso.

Você pode escrever sua própria class List que classifica cada vez que você adicionar um novo elemento. Isso pode ficar um pouco pesado, dependendo da sua implementação e é inútil , a menos que você queira fazer isso como um exercício, por duas razões principais:

  1. Ele quebra o contrato que a interface List possui porque os methods add devem garantir que o elemento residirá no índice especificado pelo usuário.
  2. Por que reinventar a roda? Você deve estar usando o TreeSet ou Multisets, como indicado no primeiro ponto acima.

No entanto, se você quiser fazer isso como um exercício, aqui está um exemplo de código para você começar, ele usa a class abstrata AbstractList :

 public class SortedList extends AbstractList { private ArrayList internalList = new ArrayList(); // Note that add(E e) in AbstractList is calling this one @Override public void add(int position, E e) { internalList.add(e); Collections.sort(internalList, null); } @Override public E get(int i) { return internalList.get(i); } @Override public int size() { return internalList.size(); } } 

Observe que, se você não tiver sobrescrito os methods necessários, as implementações padrão de AbstractList exibirão UnsupportedOperationException s.

Porque o conceito de uma lista é incompatível com o conceito de uma coleção classificada automaticamente. O ponto de uma lista é que depois de chamar list.add(7, elem) , uma chamada para list.get(7) retornará elem . Com uma lista de sorting automática, o elemento pode acabar em uma posição arbitrária.

Como todas as listas já estão “classificadas” pela ordem em que os itens foram adicionados (ordenação FIFO), é possível “reclassificá-las” com outro pedido, incluindo a ordenação natural de elementos, usando java.util.Collections.sort() .

EDITAR:

Listas como estruturas de dados são baseadas no que é interessante é a ordenação em que os itens foram inseridos.

Conjuntos não têm essa informação.

Se você quiser encomendar adicionando tempo, use List . Se você quiser encomendar por outros critérios, use SortedSet .

Para qualquer recém-chegado, a partir de abril de 2015, o Android agora tem uma class SortedList na biblioteca de suporte, projetada especificamente para trabalhar com o RecyclerView . Aqui está o post do blog sobre isso.

Definir e Mapear são estruturas de dados não lineares. Lista é estrutura de dados linear.

insira a descrição da imagem aqui


As interfaces SortedSet e SortedMap estrutura de dados de tree implementam TreeSet e TreeSet respectivamente, usando o algoritmo de implementação de tree Red-Black usado. Por isso, certifique-se de que não há itens duplicados (ou chaves no caso do Map ).

  • List já mantém uma coleção ordenada e uma estrutura de dados baseada em índice, as trees não são estruturas de dados baseadas em índice.
  • Tree por definição não pode conter duplicados.
  • Na List podemos ter duplicatas, então não há TreeList (ou seja, não SortedList ).
  • List mantém elementos no pedido de inserção. Então, se quisermos ordenar a lista, temos que usar java.util.Collections.sort() . Classifica a lista especificada em ordem crescente, de acordo com a ordenação natural de seus elementos.

SortedList JavaFX

Embora demorou um pouco, o Java 8 tem uma List ordenada. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Como você pode ver nos javadocs, ele faz parte das collections do JavaFX , destinadas a fornecer uma visualização ordenada em um ObservableList.

Outro ponto é a complexidade de tempo das operações de inserção. Para uma inserção de lista, espera-se uma complexidade de O (1). Mas isso não pode ser garantido com uma lista ordenada.

E o ponto mais importante é que as listas não assumem nada sobre seus elementos. Por exemplo, você pode criar listas de coisas que não implementam equals ou compare .

Pense nisso assim: a interface List possui methods como add(int index, E element) , set(int index, E element) . O contrato é que, uma vez que você tenha adicionado um elemento na posição X, você o encontrará a menos que adicione ou remova elementos antes dele.

Se qualquer implementação de lista armazenasse elementos em alguma ordem que não fosse baseada no índice, os methods de lista acima não farão sentido.

Primeira linha na List API diz que é uma coleção ordenada (também conhecida como sequência). Se você classificar a lista, não poderá manter o pedido, portanto, não há TreeList em Java.
Como a API diz que a lista de Java foi inspirada em Sequence e veja as propriedades da sequência http://en.wikipedia.org/wiki/Sequence_(mathematics )

Isso não significa que você não pode classificar a lista, mas sim o Java estrito em sua definição e não fornece versões ordenadas de listas por padrão.

Considere o uso do mapa de trees indexadas . É um TreeSet do JDK aprimorado que fornece access ao elemento por índice e ao encontrar o índice de um elemento sem iteração ou listas ocultas subjacentes que fazem backup da tree. O algoritmo baseia-se na atualização de pesos de troca de nós sempre que houver uma alteração.