Collection triée en Java

Question

Je suis un débutant en Java. Veuillez me suggérer quelle(s) collection(s) peut/doivent être utilisée(s) pour maintenir une liste triée en Java. J'ai essayé Map et Set mais ce n'était pas ce que je recherchais.

Answer 1

Il existe plusieurs options. Je suggérerais TreeSet si vous ne voulez pas de doublons et si les objets que vous insérez sont comparables.

Vous pouvez également utiliser les méthodes statiques de la classe Collections pour ce faire.

Voir Collections#sort(java.util.List) et Ensemble d'arbres pour plus d'informations.

Answer 2

Si vous voulez simplement trier une liste, utilisez n'importe quel type de Liste et utiliser Collections.sort() . Si vous voulez vous assurer que les éléments de la liste sont uniques et toujours triés, utilisez une balise SortedSet .

Answer 3

Ce que j'ai fait, c'est implémenter une liste ayant une instance interne avec toutes les méthodes déléguées.

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

Après, j'ai implémenté une nouvelle méthode "putOrdered" qui insère dans la bonne position si l'élément n'existe pas ou remplace juste au cas où il existe.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

Si vous souhaitez autoriser les éléments répétés, implémentez simplement addOrdered à la place (ou les deux).

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

Si vous voulez éviter les insertions, vous pouvez également lancer une exception pour opération non prise en charge sur les méthodes "add" et "set".

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

... et aussi Vous devez être prudent avec les méthodes ListIterator car elles pourraient modifier votre liste interne. Dans ce cas, vous pouvez retourner une copie de la liste interne ou encore lever une exception.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}

Answer 4

TreeSet ne fonctionnerait pas car il n'autorise pas les doublons et ne fournit pas de méthode pour récupérer un élément à une position spécifique. PriorityQueue ne fonctionnerait pas car il ne permet pas de récupérer des éléments à une position spécifique, ce qui est une exigence de base pour une liste. Je pense que vous devez implémenter votre propre algorithme pour maintenir une liste triée en Java avec un temps d'insertion O(logn), à moins que vous n'ayez pas besoin de doublons. Peut-être qu'une solution pourrait être d'utiliser un TreeMap où la clé est une sous-classe de l'élément surchargeant la méthode equals afin que les doublons soient autorisés.

Answer 5

Comme je le disais... oui, je sais que c'est un vieux post, mais les technologies apparaissent tous les jours et la réponse changera avec le temps.

Vous pouvez essayer de résoudre ces tâches avec LambdaJ . Vous pouvez le trouver ici : http://code.google.com/p/lambdaj/

Vous avez ici un exemple :

Tri Iteratif

List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
        public int compare(Person p1, Person p2) {
           return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
        }
}); 

Trier avec lambda

List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge()); 

Bien sûr, avoir ce genre de beauté a un impact sur les performances (en moyenne 2 fois), mais pouvez-vous trouver un code plus lisible ?