Is there a no-duplicate List implementation out there?
JavaListCollectionsDuplicatesJava Problem Overview
I know about SortedSet
, but in my case I need something that implements List
, and not Set
. So is there an implementation out there, in the API or elsewhere?
It shouldn't be hard to implement myself, but I figured why not ask people here first?
Java Solutions
Solution 1 - Java
There's no Java collection in the standard library to do this. LinkedHashSet<E>
preserves ordering similarly to a List
, though, so if you wrap your set in a List
when you want to use it as a List
you'll get the semantics you want.
Alternatively, the Commons Collections (or commons-collections4
, for the generic version) has a List
which does what you want already: SetUniqueList
/ SetUniqueList<E>
.
Solution 2 - Java
Here is what I did and it works.
Assuming I have an ArrayList
to work with the first thing I did was created a new LinkedHashMap
.
LinkedHashSet<E> hashSet = new LinkedHashSet<E>()
Then I attempt to add my new element to the LinkedHashSet
. The add method does not alter the LinkedHasSet
and returns false if the new element is a duplicate. So this becomes a condition I can test before adding to the ArrayList
.
if (hashSet.add(E)) arrayList.add(E);
This is a simple and elegant way to prevent duplicates from being added to an array list. If you want you can encapsulate it in and override of the add method in a class that extends the ArrayList
. Just remember to deal with addAll
by looping through the elements and calling the add method.
Solution 3 - Java
So here's what I did eventually. I hope this helps someone else.
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);
}
}
}
Solution 4 - Java
Why not encapsulate a set with a list, sort like:
new ArrayList( new LinkedHashSet() )
This leaves the other implementation for someone who is a real master of Collections ;-)
Solution 5 - Java
You should seriously consider dhiller's answer:
- Instead of worrying about adding your objects to a duplicate-less List, add them to a Set (any implementation), which will by nature filter out the duplicates.
- When you need to call the method that requires a List, wrap it in a
new ArrayList(set)
(or anew LinkedList(set)
, whatever).
I think that the solution you posted with the NoDuplicatesList
has some issues, mostly with the contains()
method, plus your class does not handle checking for duplicates in the Collection passed to your addAll()
method.
Solution 6 - Java
I needed something like that, so I went to the commons collections and used the SetUniqueList
, but when I ran some performance test, I found that it seems not optimized comparing to the case if I want to use a Set
and obtain an Array
using the Set.toArray()
method.
The SetUniqueTest
took 20:1 time to fill and then traverse 100,000 Strings comparing to the other implementation, which is a big deal difference.
So, if you worry about the performance, I recommend you to use the Set and Get an SetUniqueList
, unless you really need the logic of the SetUniqueList
, then you'll need to check other solutions...
Testing code main method:
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
}
Regards, Mohammed Sleem
Solution 7 - Java
NOTE: it does not take subList implementation into account.
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));
}
}
Solution 8 - Java
The documentation for collection interfaces says:
> Set — a collection that cannot contain duplicate elements.
> List — an ordered collection (sometimes called a sequence). Lists can contain duplicate elements.
So if you don't want duplicates, you probably shouldn't use a list.
Solution 9 - Java
Off the top of my head, lists allow duplicates. You could quickly implement a UniqueArrayList
and override all the add
/ insert
functions to check for contains()
before you call the inherited methods. For personal use, you could only implement the add
method you use, and override the others to throw an exception in case future programmers try to use the list in a different manner.
Solution 10 - Java
in add
method, why not using HashSet.add()
to check duplicates instead of HashSet.consist()
.
HashSet.add()
will return true
if no duplicate and false
otherwise.
Solution 11 - Java
What about this? Just check the list before adding with a contains for an already existing object
while (searchResult != null && searchResult.hasMore()) {
SearchResult nextElement = searchResult.nextElement();
Attributes attributes = nextElement.getAttributes();
String stringName = getAttributeStringValue(attributes, SearchAttribute.*attributeName*);
if(!List.contains(stringName)){
List.add(stringName);
}
}
Solution 12 - Java
I just made my own UniqueList in my own little library like this:
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;
}
}
I have a TestCollections class that looks like this:
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);
}
}
Works fine. All it does is it adds to a set if it does not have it already and there's an Arraylist that is returnable, as well as an object array.