En Java, il y a les interfaces SortedSetet SortedMap. Les deux appartiennent au framework Java Collections et fournissent un moyen trié d'accéder aux éléments.

Cependant, à ma connaissance, il n'y SortedListen a pas en Java. Vous pouvez utiliser java.util.Collections.sort()pour trier une liste.

Une idée pourquoi il est conçu comme ça?

Les itérateurs de liste garantissent avant tout que vous obtenez les éléments de la liste dans l'ordre interne de la liste (aka. Ordre d'insertion ). Plus précisément, c'est dans l'ordre dans lequel vous avez inséré les éléments ou dans la façon dont vous avez manipulé la liste. Le tri peut être considéré comme une manipulation de la structure des données, et il existe plusieurs façons de trier la liste.

Je vais ordonner les chemins dans l'ordre d' utilité tel que je le vois personnellement:

1. Pensez à utiliser Setou Bagcollections à la place

REMARQUE: je mets cette option en haut parce que c'est ce que vous voulez normalement faire de toute façon.

Un ensemble trié trie automatiquement la collection à l'insertion , ce qui signifie qu'il effectue le tri pendant que vous ajoutez des éléments dans la collection. Cela signifie également que vous n'avez pas besoin de le trier manuellement.

De plus, si vous êtes sûr de ne pas avoir à vous soucier (ou d'avoir) des éléments en double, vous pouvez utiliser le à la TreeSet<T>place. Il implémente SortedSetet NavigableSetinterface et fonctionne comme vous l'attendriez probablement d'une liste:

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 vous ne voulez pas l'ordre naturel, vous pouvez utiliser le paramètre constructeur qui prend a Comparator<T>.

Alternativement, vous pouvez utiliser des multisets (également appelés sacs ) , c'est-à-dire Setqui autorisent les éléments en double, et il existe des implémentations tierces. Plus particulièrement à partir des bibliothèques de Guava, il y en a un TreeMultiset, qui fonctionne beaucoup comme le TreeSet.

2. Triez votre liste avec Collections.sort()

Comme mentionné ci-dessus, le tri de Lists est une manipulation de la structure des données. Donc, pour les situations où vous avez besoin d'une "source de vérité" qui sera triée de différentes manières, puis la trier manuellement est la voie à suivre.

Vous pouvez trier votre liste avec la java.util.Collections.sort()méthode. Voici un exemple de code expliquant comment:

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"

Utiliser des comparateurs

Un avantage évident est que vous pouvez l'utiliser Comparatordans la sortméthode. Java fournit également quelques implémentations pour le Comparatortel que le Collatorqui est utile pour les chaînes de tri sensibles aux paramètres régionaux. Voici un exemple:

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

Collections.sort(strings, usCollator);

Tri dans des environnements simultanés

Notez cependant que l'utilisation de la sortméthode n'est pas conviviale dans les environnements simultanés, car l'instance de collection sera manipulée, et vous devriez plutôt envisager d'utiliser des collections immuables. C'est quelque chose que Guava fournit dans la Orderingclasse et c'est un simple doublure:

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

3. Enveloppez votre liste avec java.util.PriorityQueue

Bien qu'il n'y ait pas de liste triée en Java, il existe cependant une file d'attente triée qui fonctionnerait probablement aussi bien pour vous. C'est la java.util.PriorityQueueclasse.

Nico Haase a lié dans les commentaires une question connexe qui répond également à cela.

Dans une collection triée, vous ne voulez probablement pas manipuler la structure de données interne, c'est pourquoi PriorityQueue n'implémente pas l'interface List (car cela vous donnerait un accès direct à ses éléments).

Avertissement sur l' PriorityQueueitérateur

La PriorityQueueclasse implémente les interfaces Iterable<E>et Collection<E>afin qu'elle puisse être itérée comme d'habitude. Cependant, l'itérateur n'est pas garanti de renvoyer les éléments dans l'ordre trié. Au lieu de cela (comme le souligne Alderath dans les commentaires), vous devez mettre poll()la file d'attente jusqu'à ce qu'elle soit vide.

Notez que vous pouvez convertir une liste en file d'attente prioritaire via le constructeur qui prend n'importe quelle collection :

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. Écrivez votre propre SortedListclasse

REMARQUE: vous ne devriez pas avoir à le faire.

Vous pouvez écrire votre propre classe List qui trie chaque fois que vous ajoutez un nouvel élément. Cela peut être assez lourd à calculer en fonction de votre implémentation et est inutile , sauf si vous voulez le faire comme un exercice, pour deux raisons principales:

1. Il rompt le contrat de l' List<E>interface car les addméthodes doivent garantir que l'élément résidera dans l'index spécifié par l'utilisateur.
2. Pourquoi réinventer la roue? Vous devez utiliser le TreeSet ou les Multisets à la place, comme indiqué au premier point ci-dessus.

Cependant, si vous voulez le faire comme un exercice, voici un exemple de code pour vous aider à démarrer, il utilise la AbstractListclasse abstraite:

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

}

Notez que si vous n'avez pas remplacé les méthodes dont vous avez besoin, les implémentations par défaut de AbstractListjetteront UnsupportedOperationExceptions.

Parce que le concept d'une Liste est incompatible avec le concept d'une collection triée automatiquement. Le point d'une liste est qu'après l'appel list.add(7, elem), un appel à list.get(7)retournera elem. Avec une liste triée automatiquement, l'élément pourrait se retrouver dans une position arbitraire.

Étant donné que toutes les listes sont déjà "triées" par l'ordre dans lequel les articles ont été ajoutés (ordre FIFO), vous pouvez les "recentrer" avec un autre ordre, y compris l'ordre naturel des éléments, à l'aide de java.util.Collections.sort().

ÉDITER:

Les listes, car les structures de données sont basées sur ce qui est intéressant, c'est l'ordre dans lequel les éléments ont été insérés.

Les ensembles n'ont pas cette information.

Si vous souhaitez commander en ajoutant du temps, utilisez List. Si vous souhaitez commander selon d'autres critères, utilisez SortedSet.

Set et Map sont une structure de données non linéaire. La liste est une structure de données linéaire.

La structure de données d'arborescence SortedSetet les SortedMapinterfaces implémentent TreeSetet TreeMaputilisent respectivement l' algorithme d'implémentation d' arbre rouge-noir utilisé. Ainsi, il s'assure qu'il n'y a pas d'articles en double (ou de clés en cas de Map).

• List maintient déjà une collection ordonnée et une structure de données basée sur un index, les arbres ne sont pas des structures de données basées sur un index.
• Tree par définition, ne peut pas contenir de doublons.
• En Listnous pouvons avoir des doublons, donc il n'y en a pas TreeList(c'est-à-dire non SortedList).
• La liste conserve les éléments dans l'ordre d'insertion. Donc, si nous voulons trier la liste, nous devons utiliser java.util.Collections.sort(). Il trie la liste spécifiée par ordre croissant, selon l'ordre naturel de ses éléments.

JavaFX SortedList

Bien que cela ait pris un certain temps, Java 8 a un tri List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Comme vous pouvez le voir dans les javadocs, il fait partie des collections JavaFX , destiné à fournir une vue triée sur une ObservableList.

Mise à jour: Notez qu'avec Java 11, la boîte à outils JavaFX s'est déplacée en dehors du JDK et est maintenant une bibliothèque distincte. JavaFX 11 est disponible en tant que SDK téléchargeable ou depuis MavenCentral. Voir https://openjfx.io

Pour tous les nouveaux arrivants, depuis avril 2015, Android dispose désormais d'une classe SortedList dans la bibliothèque de support, conçue spécifiquement pour fonctionner avec RecyclerView. Voici le blog à ce sujet.

Un autre point est la complexité temporelle des opérations d'insertion. Pour une insertion de liste, on attend une complexité de O (1). Mais cela ne pouvait pas être garanti avec une liste triée.

Et le point le plus important est que les listes n'assument rien de leurs éléments. Par exemple, vous pouvez créer des listes de choses qui n'implémentent pas equalsou compare.

Pensez-y comme ceci: l' Listinterface a des méthodes comme add(int index, E element),set(int index, E element) . Le contrat est qu'une fois que vous avez ajouté un élément à la position X, vous le trouverez là, sauf si vous ajoutez ou supprimez des éléments avant lui.

Si une implémentation de liste stockait des éléments dans un ordre différent de celui basé sur l'index, les méthodes de liste ci-dessus n'auraient aucun sens.

La première ligne de l'API List indique qu'il s'agit d'une collection ordonnée (également appelée séquence). Si vous triez la liste, vous ne pouvez pas maintenir l'ordre, il n'y a donc pas de TreeList en Java.
Comme le dit l'API, Java List s'est inspiré de Sequence et affiche les propriétés de la séquence http://en.wikipedia.org/wiki/Sequence_(mathematics )

Cela ne signifie pas que vous ne pouvez pas trier la liste, mais Java strict à sa définition et ne fournit pas de versions triées des listes par défaut.

Dans le cas où vous cherchez un moyen de trier les éléments, mais aussi d'être en mesure d'y accéder par index de manière efficace, vous pouvez faire ce qui suit:

1. Utilisez une liste d'accès aléatoire pour le stockage (par exemple ArrayList)
2. Assurez-vous qu'il est toujours trié

Ensuite, pour ajouter ou supprimer un élément, vous pouvez utiliser Collections.binarySearchpour obtenir l'index d'insertion / suppression. Étant donné que votre liste implémente l'accès aléatoire, vous pouvez modifier efficacement la liste avec l'index déterminé.

Exemple:

/**
 * @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);
    }
}

Pensez à utiliser une arborescence indexée . Il s'agit d'un TreeSet JDK amélioré qui permet d'accéder à l'élément par index et de rechercher l'index d'un élément sans itération ni listes sous-jacentes cachées qui sauvegardent l'arborescence. L'algorithme est basé sur la mise à jour des poids des nœuds changeants à chaque fois qu'il y a un changement.