Existe-t-il une implémentation de la liste sans doublon?

Question

Je connais les SortedSet . , mais dans mon cas, j'ai besoin de quelque chose qui implémente List, et non Set. Y a-t-il une implémentation disponible, dans l'API ou ailleurs?

Cela ne devrait pas être difficile à mettre en œuvre moi-même, mais je me suis dit pourquoi ne pas demander d'abord aux gens ici?

Answer 1

Il n'y a pas de collection Java dans la bibliothèque standard pour le faire. LinkedHashSet<E> conserve les commandes de la même manière qu'un < =>, cependant, donc si vous envelopper votre ensemble dans un List lorsque vous souhaitez l'utiliser comme commons-collections4, vous obtiendrez la sémantique que vous souhaitez.

Vous pouvez également utiliser les collections communes (ou SetUniqueList, pour la version générique). ) a un SetUniqueList<E> qui fait ce que vous voulez déjà: <=> / <=> .

Answer 2

Voici ce que j'ai fait et cela fonctionne.

En supposant que je puisse ArrayList travailler avec la première chose que j'ai faite, un nouveau LinkedHashMap a été créé.

LinkedHashSet<E> hashSet = new LinkedHashSet<E>()

J'essaie ensuite d'ajouter mon nouvel élément au LinkedHashSet. La méthode add ne modifie pas le LinkedHasSet et renvoie false si le nouvel élément est un doublon. Donc, cela devient une condition que je peux tester avant d’ajouter à la addAll.

if (hashSet.add(E)) arrayList.add(E);

C’est un moyen simple et élégant d’empêcher l’ajout de doublons à une liste de tableaux. Si vous le souhaitez, vous pouvez l'encapsuler et remplacer la méthode add dans une classe qui étend la <=>. N'oubliez pas de traiter avec <=> en parcourant les éléments et en appelant la méthode add.

Answer 3

Alors voici ce que j'ai fait par la suite. J'espère que cela aide quelqu'un d'autre.

class NoDuplicatesList<E> extends LinkedList<E> {
    @Override
    public boolean add(E e) {
        if (this.contains(e)) {
            return false;
        }
        else {
            return super.add(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(copy);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

    @Override
    public void add(int index, E element) {
        if (this.contains(element)) {
            return;
        }
        else {
            super.add(index, element);
        }
    }
}   

Answer 4

Vous devriez sérieusement réfléchir à la réponse de Dhiller:

1. Au lieu de vous inquiéter d'ajouter vos objets à une liste sans doublons, ajoutez-les à un ensemble (toute implémentation), qui filtrera par nature les doublons.
2. Lorsque vous devez appeler la méthode nécessitant une liste, placez-la dans un new ArrayList(set) (ou un new LinkedList(set), peu importe).

Je pense que la solution que vous avez publiée avec NoDuplicatesList présente certains problèmes, principalement avec la méthode contains(). En outre, votre classe ne gère pas la recherche de doublons dans la collection transmise à votre méthode addAll().

Answer 5

Pourquoi ne pas encapsuler un ensemble avec une liste, trier comme suit:

new ArrayList( new LinkedHashSet() )

Cela laisse l’autre implémentation à quelqu'un qui maîtrise vraiment les collections ;-)

Answer 6

J'avais besoin de quelque chose comme ça, alors je suis allé dans les collections communes et ai utilisé SetUniqueList, mais quand j'ai effectué un test de performance, j'ai constaté qu'il ne semblait pas être optimisé par rapport à la casse si je voulais utiliser un Set et obtenir un Array utilisant la méthode Set.toArray (), SetUniqueTest a mis 20: 1 fois pour remplir, puis parcourir 100 000 chaînes en comparant avec l’implémentation implémentée, ce qui représente une différence importante. Par conséquent, si vous vous inquiétez des performances, je vous recommande d’utiliser Set et obtenez un tableau au lieu d'utiliser SetUniqueList, sauf si vous avez vraiment besoin de la logique de SetUniqueList, vous devez alors vérifier les autres solutions ...

La méthode principale du code de test:

public static void main (String [] args) {

SetUniqueList pq = SetUniqueList.decorate(new ArrayList());
Set s = new TreeSet();

long t1 = 0L;
long t2 = 0L;
String t;


t1 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    pq.add("a" + Math.random());
}
while (!pq.isEmpty()) {
    t = (String) pq.remove(0);
}
t1 = System.nanoTime() - t1;

t2 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    s.add("a" + Math.random());
}

s.clear();
String[] d = (String[]) s.toArray(new String[0]);
s.clear();
for (int i = 0; i < d.length; i++) {
    t = d[i];

}
t2 = System.nanoTime() - t2;

System.out.println((double)t1/1000/1000/1000); //seconds
System.out.println((double)t2/1000/1000/1000); //seconds
System.out.println(((double) t1) / t2);        //comparing results

}

Cordialement Mohammed Sleem http://abusleem.net/blog

Answer 7

REMARQUE: la mise en œuvre de sous-liste n'est pas prise en compte.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class UniqueList<T> extends ArrayList<T> {

    private static final long serialVersionUID = 1L;

    /** Unique elements SET */
    private final Set<T> set=new HashSet();

    /** Used by addAll methods */
    private Collection<T> addUnique(Collection<? extends T> col) {
        Collection<T> unique=new ArrayList();
        for(T e: col){
            if (set.add(e)) unique.add(e);
        }
        return unique;
    }

    @Override
    public boolean add(T e) {
        return set.add(e) ? super.add(e) : false;
    }

    @Override
    public boolean addAll(Collection<? extends T> col) {
        return super.addAll(addUnique(col));
    }

    @Override
    public void add(int index, T e) {
        if (set.add(e)) super.add(index, e);
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> col) {
        return super.addAll(index, addUnique(col));
    }

}

Answer 8

La documentation sur les interfaces de collection indique:

  

Définissez & # 8212; une collection qui ne peut pas contenir d'éléments en double.
  Liste & # 8212; une collection ordonnée (parfois appelée séquence). Les listes peuvent contenir des éléments en double.

Donc, si vous ne voulez pas de doublons, vous ne devriez probablement pas utiliser de liste.

Answer 9

dans add méthode, pourquoi ne pas utiliser HashSet.add() pour vérifier les doublons au lieu de HashSet.consist(). true renverra false s'il n'y a pas de doublon et <=> sinon.

Answer 10

En tête de liste, les listes permettent les doublons. Vous pouvez rapidement implémenter un UniqueArrayList et remplacer toutes les add / insert fonctions pour vérifier contains() avant d'appeler les méthodes héritées. Pour une utilisation personnelle, vous ne pouvez implémenter que la méthode <=> que vous utilisez et remplacer les autres méthodes par une exception si les futurs programmeurs essaient d’utiliser la liste différemment.

Answer 11

Je viens de créer ma propre UniqueList dans ma propre petite bibliothèque, comme ceci:

package com.bprog.collections;//my own little set of useful utilities and classes

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Jonathan
*/
public class UniqueList {

private HashSet masterSet = new HashSet();
private ArrayList growableUniques;
private Object[] returnable;

public UniqueList() {
    growableUniques = new ArrayList();
}

public UniqueList(int size) {
    growableUniques = new ArrayList(size);
}

public void add(Object thing) {
    if (!masterSet.contains(thing)) {
        masterSet.add(thing);
        growableUniques.add(thing);
    }
}

/**
 * Casts to an ArrayList of unique values
 * @return 
 */
public List getList(){
    return growableUniques;
}

public Object get(int index) {
    return growableUniques.get(index);
}

public Object[] toObjectArray() {
    int size = growableUniques.size();
    returnable = new Object[size];
    for (int i = 0; i < size; i++) {
        returnable[i] = growableUniques.get(i);
    }
    return returnable;
    }
}

J'ai une classe TestCollections qui ressemble à ceci:

package com.bprog.collections;
import com.bprog.out.Out;
/**
*
* @author Jonathan
*/
public class TestCollections {
    public static void main(String[] args){
        UniqueList ul = new UniqueList();
        ul.add("Test");
        ul.add("Test");
        ul.add("Not a copy");
        ul.add("Test"); 
        //should only contain two things
        Object[] content = ul.toObjectArray();
        Out.pl("Array Content",content);
    }
}

Fonctionne bien. Tout ce qu'il fait, c'est ajouter à un ensemble s'il ne l'a pas déjà et s'il existe un Arraylist qui peut être renvoyé, ainsi qu'un tableau d'objets.