En Java existen las interfaces SortedSety SortedMap. Ambos pertenecen al marco de Java Collections y proporcionan una forma ordenada de acceder a los elementos.

Sin embargo, según tengo entendido, no hay SortedListen Java. Puede usar java.util.Collections.sort()para ordenar una lista.

¿Alguna idea de por qué está diseñado así?

Los iteradores de lista garantizan en primer lugar que obtiene los elementos de la lista en el orden interno de la lista (también conocido como orden de inserción ). Más específicamente, está en el orden en que ha insertado los elementos o en cómo ha manipulado la lista. La ordenación puede verse como una manipulación de la estructura de datos, y hay varias formas de ordenar la lista.

Ordenaré las formas en el orden de utilidad tal como lo veo personalmente:

1. Considere usar Seto Bagcolecciones en su lugar

NOTA: pongo esta opción en la parte superior porque esto es lo que normalmente quieres hacer de todos modos.

Un conjunto ordenado clasifica automáticamente la colección en la inserción , lo que significa que realiza la clasificación mientras agrega elementos a la colección. También significa que no necesita ordenarlo manualmente.

Además, si está seguro de que no necesita preocuparse por (o tener) elementos duplicados, puede usar el TreeSet<T>en su lugar. Implementa SortedSete NavigableSetinteractúa y funciona como probablemente esperarías de una 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"

Si no desea el orden natural, puede usar el parámetro constructor que toma a Comparator<T>.

Alternativamente, puede usar Multisets (también conocidos como Bolsas ) , es decir, Setque permite elementos duplicados, y hay implementaciones de terceros de ellos. Más notablemente de las bibliotecas de guayaba hay un TreeMultiset, que funciona mucho como el TreeSet.

2. Ordene su lista con Collections.sort()

Como se mencionó anteriormente, la clasificación de Lists es una manipulación de la estructura de datos. Entonces, para situaciones en las que necesita "una fuente de verdad" que se clasificará de varias maneras, entonces ordenarlas manualmente es el camino a seguir.

Puedes ordenar tu lista con el java.util.Collections.sort()método. Aquí hay un ejemplo de código sobre cómo:

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

Un beneficio claro es que puede usarlo Comparatoren el sortmétodo. Java también proporciona algunas implementaciones para Comparator, como la Collatorque es útil para cadenas de clasificación sensibles a la configuración regional. Aquí hay un ejemplo:

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

Collections.sort(strings, usCollator);

Ordenar en entornos concurrentes

Sin embargo, tenga en cuenta que el uso del sortmétodo no es amigable en entornos concurrentes, ya que la instancia de la colección será manipulada, y debería considerar el uso de colecciones inmutables. Esto es algo que Guava ofrece en la Orderingclase y es simple:

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

3. Envuelva su lista con java.util.PriorityQueue

Aunque no hay una lista ordenada en Java, hay una cola ordenada que probablemente funcione igual de bien para usted. Es la java.util.PriorityQueueclase.

Nico Haase enlazó en los comentarios a una pregunta relacionada que también responde a esto.

En una colección ordenada, lo más probable es que no desee manipular la estructura de datos interna, por lo que PriorityQueue no implementa la interfaz Lista (porque eso le daría acceso directo a sus elementos).

Advertencia sobre el PriorityQueueiterador

La PriorityQueueclase implementa las interfaces Iterable<E>y Collection<E>para que pueda iterarse como de costumbre. Sin embargo, no se garantiza que el iterador devuelva elementos en el orden ordenado. En cambio (como señala Alderath en los comentarios) necesita hacer poll()cola hasta que esté vacío.

Tenga en cuenta que puede convertir una lista en una cola prioritaria a través del constructor que toma cualquier colección :

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. Escribe tu propia SortedListclase

NOTA: No debería tener que hacer esto.

Puede escribir su propia clase Lista que se ordena cada vez que agrega un nuevo elemento. Esto puede hacer que el cálculo sea bastante pesado dependiendo de su implementación y no tiene sentido , a menos que desee hacerlo como un ejercicio, debido a dos razones principales:

1. Rompe el contrato que List<E>tiene la interfaz porque los addmétodos deben garantizar que el elemento residirá en el índice que el usuario especifique.
2. ¿Por qué reinventar la rueda? En su lugar, debe usar TreeSet o Multisets como se señala en el primer punto anterior.

Sin embargo, si desea hacerlo como ejercicio, aquí hay una muestra de código para comenzar, utiliza la AbstractListclase abstracta:

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();
    }

}

Tenga en cuenta que si no ha anulado los métodos que necesita, las implementaciones predeterminadas de AbstractListarrojarán UnsupportedOperationExceptions.

Porque el concepto de una Lista es incompatible con el concepto de una colección ordenada automáticamente. El punto de una Lista es que después de llamar list.add(7, elem), list.get(7)volverá una llamada a elem. Con una lista ordenada automáticamente, el elemento podría terminar en una posición arbitraria.

Como todas las listas ya están "ordenadas" por el orden en que se agregaron los elementos (orden FIFO), puede "recurrirlas" con otro orden, incluido el orden natural de los elementos java.util.Collections.sort().

EDITAR:

Las listas ya que las estructuras de datos se basan en lo interesante es el orden en que se insertaron los elementos.

Los conjuntos no tienen esa información.

Si desea ordenar agregando tiempo, use List. Si desea ordenar por otros criterios, use SortedSet.

Set y Map son estructuras de datos no lineales. La lista es una estructura de datos lineal.

La estructura de datos de árbol SortedSety las SortedMapinterfaces implementan TreeSety TreeMaputilizan respectivamente el algoritmo de implementación de árbol rojo-negro utilizado . Por lo tanto, asegúrese de que no haya elementos duplicados (o claves en caso de Map).

• List ya mantiene una colección ordenada y una estructura de datos basada en índices, los árboles no son estructuras de datos basadas en índices.
• Tree por definición no puede contener duplicados.
• En Listpodemos tener duplicados, por lo que no hay TreeList(es decir, no SortedList).
• La lista mantiene los elementos en orden de inserción. Entonces, si queremos ordenar la lista, tenemos que usarla java.util.Collections.sort(). Ordena la lista especificada en orden ascendente, de acuerdo con el orden natural de sus elementos.

JavaFX SortedList

Aunque tomó un tiempo, Java 8 tiene un orden List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Como puede ver en los javadocs, forma parte de las colecciones JavaFX , destinadas a proporcionar una vista ordenada en un ObservableList.

Actualización: Tenga en cuenta que con Java 11, el kit de herramientas JavaFX se ha movido fuera del JDK y ahora es una biblioteca separada. JavaFX 11 está disponible como un SDK descargable o desde MavenCentral. Ver https://openjfx.io

Para cualquier recién llegado, a partir de abril de 2015, Android ahora tiene una clase SortedList en la biblioteca de soporte, diseñada específicamente para trabajar RecyclerView. Aquí está la publicación del blog al respecto.

Otro punto es la complejidad temporal de las operaciones de inserción. Para una inserción de lista, se espera una complejidad de O (1). Pero esto no se puede garantizar con una lista ordenada.

Y el punto más importante es que las listas no asumen nada sobre sus elementos. Por ejemplo, puede hacer listas de cosas que no implementan equalso compare.

Piense en ello como esto: la Listinterfaz tiene métodos como add(int index, E element), set(int index, E element). El contrato es que una vez que haya agregado un elemento en la posición X, lo encontrará allí a menos que agregue o elimine elementos antes.

Si cualquier implementación de la lista almacenara elementos en un orden distinto al basado en el índice, los métodos de lista anteriores no tendrían sentido.

La primera línea de la API de lista dice que es una colección ordenada (también conocida como secuencia). Si ordena la lista, no puede mantener el orden, por lo que no hay TreeList en Java.
Como dice API, Java List se inspiró en Sequence y vea las propiedades de secuencia http://en.wikipedia.org/wiki/Sequence_(mathematics )

No significa que no pueda ordenar la lista, pero Java es estricto con su definición y no proporciona versiones ordenadas de listas de forma predeterminada.

En caso de que esté buscando una forma de ordenar elementos, pero también poder acceder a ellos por índice de manera eficiente, puede hacer lo siguiente:

1. Utilice una lista de acceso aleatorio para el almacenamiento (p ArrayList. Ej. )
2. Asegúrese de que siempre esté ordenado

Luego, para agregar o eliminar un elemento que puede usar Collections.binarySearchpara obtener el índice de inserción / eliminación. Como su lista implementa acceso aleatorio, puede modificar eficientemente la lista con el índice determinado.

Ejemplo:

/**
 * @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 indexed-tree-map . Es un TreeSet de JDK mejorado que proporciona acceso al elemento por índice y encuentra el índice de un elemento sin iteración o listas subyacentes ocultas que respaldan el árbol. El algoritmo se basa en actualizar los pesos de los nodos cambiantes cada vez que hay un cambio.