Czy istnieje implementacja listy bez duplikatów?

Wiem o tym SortedSet, ale w moim przypadku potrzebuję czegoś, co implementuje List, a nieSet . Więc czy jest tam implementacja, w API czy gdzie indziej?

Samo wdrożenie nie powinno być trudne, ale pomyślałem, dlaczego nie zapytać najpierw ludzi tutaj?

W bibliotece standardowej nie ma kolekcji Java, która mogłaby to zrobić. LinkedHashSet<E>zachowuje jednak porządkowanie podobnie jak a List, więc jeśli zawiniesz zestaw w a, Listgdy chcesz go użyć jakoList , uzyskasz pożądaną semantykę.

Alternatywnie, kolekcje Commons (lub commons-collections4, dla wersji ogólnej) mają już plik, Listktóry robi to, co chcesz: SetUniqueList/ SetUniqueList<E>.

Oto co zrobiłem i to działa.

Zakładając, że muszę ArrayListpopracować z pierwszą rzeczą, którą zrobiłem, było stworzenie nowego LinkedHashMap.

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

Następnie próbuję dodać mój nowy element do LinkedHashSet. Metoda add nie zmienia LinkedHasSeti zwraca false, jeśli nowy element jest duplikatem. Jest to więc warunek, który mogę przetestować przed dodaniem do ArrayList.

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

Jest to prosty i elegancki sposób zapobiegania dodawaniu duplikatów do listy tablic. Jeśli chcesz, możesz go hermetyzować i przesłonić metodę add w klasie, która rozszerza ArrayList. Pamiętaj tylko, aby sobie z tym poradzić, addAllprzechodząc przez elementy i wywołując metodę add.

Oto co w końcu zrobiłem. Mam nadzieję, że to pomoże komuś innemu.

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

Dlaczego nie hermetyzować zestawu listą, posortuj jak:

new ArrayList( new LinkedHashSet() )

To pozostawia inną implementację dla kogoś, kto jest prawdziwym mistrzem Kolekcji ;-)

Powinieneś poważnie rozważyć odpowiedź dhillera:

1. Zamiast martwić się dodawaniem obiektów do listy bez duplikatów, dodaj je do zestawu (dowolnej implementacji), który z natury odfiltruje duplikaty.
2. Kiedy musisz wywołać metodę, która wymaga listy, zawiń ją w a new ArrayList(set)(lub new LinkedList(set)cokolwiek).

Myślę, że rozwiązanie, które opublikowałeś, NoDuplicatesListma pewne problemy, głównie z contains()metodą, a Twoja klasa nie obsługuje sprawdzania duplikatów w kolekcji przekazanej do addAll()metody.

Potrzebowałem czegoś takiego, więc poszedłem do wspólnych kolekcji i użyłem SetUniqueList, ale kiedy przeprowadziłem jakiś test wydajności, stwierdziłem, że wydaje się nie zoptymalizowany w porównaniu z przypadkiem, jeśli chcę użyć a Seti uzyskać ArrayużycieSet.toArray() .

SetUniqueTestWzięło 20: 1 czas wypełnić, a następnie trawers 100000 Strings porównaniu do innych realizacji, która jest duża różnica sprawa.

Tak więc, jeśli martwisz się o wydajność, polecam ci użyć Set and Get an Array zamiast używać SetUniqueList, chyba że naprawdę potrzebujesz logiki SetUniqueList, wtedy musisz sprawdzić inne rozwiązania ...

Główna metoda testowania kodu :

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

}

Pozdrawiam, Mohammed Sleem

UWAGA: nie uwzględnia implementacji subList .

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

}

Dokumentacja interfejsów zbiórki mówi:

Zestaw - zbiór, który nie może zawierać zduplikowanych elementów.
Lista - uporządkowana kolekcja (czasami nazywana sekwencją). Listy mogą zawierać zduplikowane elementy.

Więc jeśli nie chcesz duplikatów, prawdopodobnie nie powinieneś używać listy.

w addmetodzie, dlaczego nie użyć HashSet.add()do sprawdzania duplikatów zamiast HashSet.consist(). HashSet.add()zwróci, truejeśli nie ma duplikatu i falseinaczej.

Nawiasem mówiąc, listy zezwalają na duplikaty. Możesz szybko zaimplementować UniqueArrayListi przesłonić wszystkie add/ insertfunkcje, które mają być sprawdzane contains()przed wywołaniem dziedziczonych metod. Do użytku osobistego możesz zaimplementować tylko addmetodę, której używasz, i przesłonić inne, aby zgłosić wyjątek na wypadek, gdyby przyszli programiści spróbowali użyć listy w inny sposób.

Właśnie utworzyłem własną UniqueList w mojej własnej małej bibliotece w następujący sposób:

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

Mam klasę TestCollections, która wygląda następująco:

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

Działa w porządku. Wszystko, co robi, to dodaje do zestawu, jeśli jeszcze go nie ma i istnieje Arraylist, który jest zwrotny, a także tablica obiektów.