Em Java, há o SortedSeteSortedMap interfaces . Ambos pertencem à estrutura Java Collections e fornecem uma maneira classificada de acessar os elementos.

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

Alguma idéia de por que é projetado assim?

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

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

1. Considere usar Setou Bagcoleções

NOTA: Coloquei essa opção no topo, porque é isso que você normalmente deseja fazer.

Um conjunto classificado classifica automaticamente a coleção na inserção , o que significa que faz a classificação 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 (ou ter) elementos duplicados, poderá usá-lo TreeSet<T>. Ele implementa SortedSete NavigableSetinterfaces e obras como você provavelmente esperaria de uma lista:

TreeSet<String> set = new TreeSet<String>();
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 deseja a ordem natural, pode usar o parâmetro construtor que recebe a Comparator<T>.

Como alternativa, você pode usar Multisets (também conhecidos como Bags ) , ou seja, Setque permite elementos duplicados, e existem implementações de terceiros. Mais notavelmente das bibliotecas do Guava, existe um TreeMultiset, que funciona muito como o TreeSet.

2. Classifique sua lista com Collections.sort()

Como mencionado acima, a classificação de Lists é uma manipulação da estrutura de dados. Portanto, 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 percorrer.

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

List<String> strings = new ArrayList<String>()
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 benefício claro é que você pode usar Comparatorno sortmétodo. Java também fornece algumas implementações para Comparatoras Collatorque são úteis para seqüências de classificação sensíveis ao código do idioma. Aqui está um exemplo:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Classificação em ambientes simultâneos

Observe, porém, que o uso do sortmétodo não é amigável em ambientes simultâneos, pois a instância da coleção será manipulada e, em vez disso, você deve considerar o uso de coleções imutáveis. Isso é algo que o Guava fornece na Orderingclasse e é uma linha simples:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Envolva sua lista com java.util.PriorityQueue

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

Nico Haase vinculou nos comentários a uma pergunta relacionada que também responde a isso.

Em uma coleção classificada, você provavelmente não deseja manipular a estrutura de dados interna, e é por isso que o PriorityQueue não implementa a interface List (porque isso lhe daria acesso direto a seus elementos).

Advertência sobre o PriorityQueueiterador

A PriorityQueueclasse implementa as interfaces Iterable<E>e Collection<E>para que possa ser iterada como de costume. No entanto, não é garantido que o iterador retorne elementos na ordem classificada. Em vez disso (como Alderath aponta nos comentários), você precisa ficar poll()na fila até ficar vazio.

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

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

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

4. Escreva sua própria SortedListturma

NOTA: Você não precisa fazer isso.

Você pode escrever sua própria classe List, que é classificada sempre que adicionar um novo elemento. Isso pode tornar a computação pesada, dependendo da sua implementação e não faz sentido , a menos que você queira fazer isso como um exercício, por dois motivos principais:

1. Ele quebra o contrato que a List<E>interface possui, porque os addmétodos devem garantir que o elemento resida no índice especificado pelo usuário.
2. Por que reinventar a roda? Você deve usar 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 começar, ele usa a AbstractListclasse abstract:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // 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 substituiu os métodos necessários, as implementações padrão de AbstractListirão lançar UnsupportedOperationExceptions.

Como o conceito de uma lista é incompatível com o conceito de uma coleção classificada automaticamente. O objetivo de uma lista é que, após a chamada list.add(7, elem), uma chamada para list.get(7)retornará elem. Com uma lista classificada automaticamente, o elemento pode terminar em uma posição arbitrária.

Como todas as listas já estão "classificadas" pela ordem em que os itens foram adicionados (ordem FIFO), você pode "recorrer" a elas com outra ordem, incluindo a ordem natural dos elementos, usando java.util.Collections.sort().

EDITAR:

As listas como estruturas de dados são baseadas no que é interessante é a ordem na qual os itens foram inseridos.

Os conjuntos não possuem essa informação.

Se você deseja pedir adicionando tempo, use List. Se você deseja solicitar por outros critérios, use SortedSet.

Set e Map são estruturas de dados não lineares. Lista é estrutura de dados linear.

A estrutura de dados SortedSete as SortedMapinterfaces da árvore implementam TreeSete, TreeMaprespectivamente, usando o algoritmo de implementação de árvore Red-Black usado . Portanto, verifique se não há itens duplicados (ou chaves no caso de Map).

• List já mantém uma coleção ordenada e uma estrutura de dados baseada em índice, as árvores não são estruturas de dados baseadas em índice.
• Tree por definição, não pode conter duplicatas.
• Em Listpodemos ter duplicatas, então não há TreeList(ou seja, não SortedList).
• Lista mantém elementos em ordem de inserção. Então, se queremos classificar a lista, temos que usar java.util.Collections.sort(). Ele classifica a lista especificada em ordem crescente, de acordo com a ordem natural de seus elementos.

JavaFX SortedList

Embora tenha demorado um pouco, o Java 8 tem uma classificação List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Como você pode ver nos javadocs, ele faz parte das coleções JavaFX , destinadas a fornecer uma exibição classificada em um ObservableList.

Atualização: Observe que, com o Java 11, o kit de ferramentas JavaFX foi movido para fora do JDK e agora é uma biblioteca separada. O JavaFX 11 está disponível como um SDK para download ou no MavenCentral. Consulte https://openjfx.io

Para todos os recém-chegados, a partir de abril de 2015, o Android agora possui uma classe SortedList na biblioteca de suporte, projetada especificamente para trabalhar RecyclerView. Aqui está o post sobre isso.

Outro ponto é a complexidade do 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 classificada.

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

Pense nisso como este: a Listinterface possui métodos como add(int index, E element), set(int index, E element). O contrato é que, depois de adicionar um elemento na posição X, você o encontrará, a menos que adicione ou remova elementos antes dele.

Se alguma implementação de lista armazenasse elementos em alguma ordem que não fosse o índice, os métodos de lista acima não teriam sentido.

A primeira linha da API da lista diz que é uma coleção ordenada (também conhecida como sequência). Se você classificar a lista, não poderá manter a ordem, portanto, não haverá TreeList em Java.
Como a API diz, a lista Java foi inspirada na sequência 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 o Java é estrito à sua definição e não fornece versões classificadas das listas por padrão.

Caso você esteja procurando uma maneira de classificar elementos, mas também possa acessá-los por índice de maneira eficiente, faça o seguinte:

1. Use uma lista de acesso aleatório para armazenamento (por exemplo ArrayList)
2. Verifique se ele está sempre classificado

Em seguida, para adicionar ou remover um elemento, você pode usar Collections.binarySearchpara obter o índice de inserção / remoção. Como sua lista implementa o acesso aleatório, você pode modificar eficientemente a lista com o índice determinado.

Exemplo:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}

Considere usar o mapa da árvore indexada . É um TreeSet aprimorado do JDK que fornece acesso ao elemento por índice e localiza o índice de um elemento sem iteração ou listas subjacentes ocultas que fazem backup da árvore. O algoritmo é baseado na atualização de pesos dos nós alterados toda vez que há uma alteração.