Existe-t-il une liste triée indexable dans le package Java.util?

Question

Je cherche une structure de données dans le paquet java.util. J'en ai besoin pour répondre aux exigences suivantes:

• Le nombre d'éléments est (théoriquement) illimité.
• Les éléments sont triés dans un ordre croissant.
• Vous pouvez obtenir le nième élément (rapide).
• Vous pouvez supprimer le nième élément (rapide).

Je m'attendais à trouver une liste de saut indexable, mais je ne l'ai pas fait. Ont-ils une structure de données qui répond aux exigences que j'ai indiquées?

Answer 1

Il n'existe aucune structure de données simple répondant à tous vos critères.

Le seul que je connaisse qui les remplisse tous serait un indexable skip list. Cependant, je ne connais aucune implémentation Java facilement disponible.

Answer 2

Regardez PriorityQueue.

Si vous n'avez pas besoin d'éléments similaires dans votre structure de données, TreeSet habituel répond également à vos besoins.

Answer 3

TreeSet vous offre la fonctionnalité de tri naturel tout en ajoutant des éléments à la liste. Mais si vous n'en avez pas besoin et que Collections.sort() est autorisé, vous pouvez utiliser le ArrayList simple.

Answer 4

Cette question est très similaire à

• Sorted array list in Java

Jetez un oeil à my answer to that question.

Fondamentalement, il suggère ce qui suit:

class SortedArrayList<T> extends ArrayList<T> { 

    @SuppressWarnings("unchecked") 
    public void insertSorted(T value) { 
     add(value); 
     Comparable<T> cmp = (Comparable<T>) value; 
     for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) { 
      T tmp = get(i); 
      set(i, get(i-1)); 
      set(i-1, tmp); 
     } 
    } 
} 

---

Une note sur votre première exigence: "Le nombre d'éléments est sans bornes.":

Vous pouvez limiter cela quelque chose comme "Le nombre d'éléments ne doit pas être limité par moins de 2 -1 ..." car sinon vous excluez toutes les options qui sont supportées par un tableau Java. (Vous pourriez obtenir un nombre arbitraire d'éléments en utilisant par exemple une LinkedList, mais je ne vois pas comment vous pourriez faire des recherches rapides dans cela.)

Answer 5

Considérons List combiné avec Collections.sort().

Answer 6

Voulez-vous profiter ce DWB dit avec List<T> et Collections.sort(), vous pouvez utiliser ArrayList<T> comme qui implémente List<T> (et n'est pas synchronisé comme Vector<T> à moins bien sûr que vous voulez que les frais généraux). C'est probablement votre meilleur pari parce qu'ils (Sun) font généralement beaucoup de recherches dans ces domaines (d'après ce que j'ai vu de toute façon). Si vous avez besoin de trier par quelque chose d'autre que le "défaut" (c'est-à-dire que vous n'êtes pas en train de trier une liste d'entiers, etc.), alors fournissez votre propre comparateur.

EDIT: La seule chose qui ne répond pas à vos besoins sont les déménagements rapides ...

Answer 7

Il n'y a pas un tel récipient dans les bibliothèques Java standard.

Quand je besoin d'une structure de données avec ces propriétés, j'utilise une implémentation List (généralement un ArrayList, mais il n'a pas d'importance), et je fais toutes les insertions utilisant Collections.binarySearch. Si je devais encapsuler une liste triée en tant que classe réutilisable, j'implémenterais l'interface List, en déléguant toutes les méthodes à une implémentation de liste «standard» (elle peut même être transmise en tant que paramètre au constructeur). J'implémenterais chaque méthode d'insertion (add, addAll, set, Iterator's remove) en lançant une exception (UnsupportedOperationException), afin que personne ne puisse casser la propriété 'always sorted'. Enfin, je fournirais une méthode insertSorted qui utiliserait Collections.binarySearch pour faire l'insertion.