Gibt es da draußen eine No-Duplicate-List-Implementierung?

Ich weiß Bescheid SortedSet, aber in meinem Fall brauche ich etwas, das implementiert wird List, und nicht Set. Gibt es da draußen eine Implementierung, in der API oder anderswo?

Es sollte nicht schwer sein, mich selbst zu implementieren, aber ich dachte mir, warum nicht zuerst die Leute hier fragen?

Es gibt keine Java-Sammlung in der Standardbibliothek, um dies zu tun. LinkedHashSet<E>Die Reihenfolge bleibt jedoch ähnlich wie bei a erhalten. ListWenn Sie also Ihr Set in a einschließen, wenn Sie Listes als a verwenden möchten, Listerhalten Sie die gewünschte Semantik.

Alternativ haben die Commons-Sammlungen (oder commons-collections4für die generische Version) eine, die Listdas tut, was Sie bereits wollen: SetUniqueList/ SetUniqueList<E>.

Hier ist was ich getan habe und es funktioniert.

Angenommen, ich muss ArrayListmit dem ersten arbeiten, was ich getan habe, ist ein neues erstellt LinkedHashMap.

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

Dann versuche ich mein neues Element zum hinzuzufügen LinkedHashSet. Die add-Methode ändert das nicht LinkedHasSetund gibt false zurück, wenn das neue Element ein Duplikat ist. Dies wird also zu einer Bedingung, die ich testen kann, bevor ich sie hinzufüge ArrayList.

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

Dies ist eine einfache und elegante Methode, um zu verhindern, dass Duplikate zu einer Array-Liste hinzugefügt werden. Wenn Sie möchten, können Sie es in die add-Methode in einer Klasse einkapseln und überschreiben, die das erweitert ArrayList. Denken Sie daran, addAlldie Elemente zu durchlaufen und die add-Methode aufzurufen.

Also hier ist, was ich schließlich getan habe. Ich hoffe das hilft jemand anderem.

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

Warum kapseln Sie ein Set nicht mit einer Liste? Sortieren Sie wie folgt:

new ArrayList( new LinkedHashSet() )

Damit bleibt die andere Implementierung für jemanden, der ein echter Meister der Sammlungen ist ;-)

Sie sollten ernsthaft über Dhillers Antwort nachdenken:

1. Anstatt sich Gedanken über das Hinzufügen Ihrer Objekte zu einer Liste ohne Duplikate zu machen, fügen Sie sie einem Set (einer beliebigen Implementierung) hinzu, wodurch die Duplikate von Natur aus herausgefiltert werden.
2. Wenn Sie die Methode aufrufen müssen, für die eine Liste erforderlich ist, schließen Sie sie in eine new ArrayList(set)(oder eine new LinkedList(set), was auch immer) ein.

Ich denke, dass die Lösung, die Sie mit veröffentlicht NoDuplicatesListhaben, einige Probleme hat, hauptsächlich mit der contains()Methode, und dass Ihre Klasse nicht nach Duplikaten in der Sammlung sucht, die an Ihre addAll()Methode übergeben wurde.

Ich brauchte so etwas, also ging ich zu den Commons-Sammlungen und benutzte die SetUniqueList, aber als ich einen Leistungstest durchführte, stellte ich fest, dass es im Vergleich zum Fall nicht optimiert zu sein scheint, wenn ich eine verwenden Setund eine Arraymit der Set.toArray()Methode erhalten möchte .

Das Ausfüllen und anschließende Durchlaufen von 100.000 Strings im Vergleich zur anderen Implementierung SetUniqueTestdauerte 20: 1 , was einen großen Unterschied darstellt.

Wenn Sie sich also Gedanken über die Leistung machen, empfehle ich Ihnen, Set and Get a Array anstelle von zu verwenden SetUniqueList, es sei denn, Sie benötigen wirklich die Logik von SetUniqueList, dann müssen Sie andere Lösungen überprüfen ...

Hauptmethode zum Testen des Codes :

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

}}

Grüße, Mohammed Sleem

HINWEIS: Die Implementierung der Unterliste wird nicht berücksichtigt.

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

}

Die Dokumentation für Sammlungsschnittstellen lautet:

Set - eine Sammlung, die keine doppelten Elemente enthalten darf.
Liste - eine geordnete Sammlung (manchmal auch als Sequenz bezeichnet). Listen können doppelte Elemente enthalten.

Wenn Sie also keine Duplikate möchten, sollten Sie wahrscheinlich keine Liste verwenden.

in der addMethode, warum nicht verwenden HashSet.add(), um Duplikate anstelle von zu überprüfen HashSet.consist(). HashSet.add()wird zurückgegeben, truewenn kein Duplikat und falsesonst.

Listen erlauben Duplikate. Sie können a schnell implementieren UniqueArrayListund alle zu überprüfenden add/ insertFunktionen überschreiben, contains()bevor Sie die geerbten Methoden aufrufen. Für den persönlichen Gebrauch können Sie die von addIhnen verwendete Methode nur implementieren und die anderen überschreiben, um eine Ausnahme auszulösen, falls zukünftige Programmierer versuchen, die Liste auf andere Weise zu verwenden.

Ich habe gerade meine eigene UniqueList in meiner eigenen kleinen Bibliothek erstellt:

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

Ich habe eine TestCollections-Klasse, die so aussieht:

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

Funktioniert gut. Alles, was es tut, ist, es zu einem Set hinzuzufügen, wenn es es noch nicht hat und es eine Arraylist gibt, die zurückgegeben werden kann, sowie ein Objektarray.