12

What kind of List will automatically eliminate duplicates when they are added.

e.g. for a List if I add 1,2,3,4,5,1,2,3 = the List should just contain just 1,2,3,4,5

0

10 Answers 10

17

Have a look at LinkedHashSet

8
  • 1
    LinkedHashSet is one implementation of the Set interface... Why do you recommend this one rather than another ?
    – pgras
    Sep 24, 2010 at 7:35
  • 5
    @pgras, perhaps because the order in which elements are added is kept in tact, just as a list.
    – Bart Kiers
    Sep 24, 2010 at 7:37
  • 2
    @Wolfgang, @Bart K - the problem is that LinkedHashSet is NOT a List. It implements the Set API, and does not allow you to get, update or insert or delete elements positionally.
    – Stephen C
    Sep 24, 2010 at 7:46
  • 1
    you can use for(element e : collection) to iterate through it in the order things were added which can be important even if direct positional access isn't available
    – Brian
    Sep 24, 2010 at 8:12
  • 3
    @Wolfgang - 1) LinkedHashSet does NOT exhibit the characteristics of a real List, as my previous comment explained. 2) A better idea would be to implement a real Set/List hybrid. A wrapper for an ArrayList and a HashSet would do the job.
    – Stephen C
    Sep 24, 2010 at 9:37
15

A Set will automatically eliminate duplicates, but it is a Collection rather than a List.

I don't think there is a List that eliminates duplicates in the standard library.

The Annotated Outline of the Collections Framework page of the Java 6 SE API documentation says that "Duplicates are generally permitted."

1
  • 2
    +1 For pointing out the difference between Sets and Lits.
    – le-doude
    Aug 16, 2013 at 11:00
6

If you want to eliminate duplicates, use Set

4

Like the above poster said, there is no List with Unique handling.

Look at List (Java Platform SE 6)

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

2
  • Rare ... and costly. Throwing exceptions is expensive.
    – Stephen C
    Sep 24, 2010 at 9:42
  • expensive, true. But sometimes unavoidable. many collection methods throw UnsupportedOperationException and there is no way for client code to find out that they do in advance. RuntimeExceptions are something you have to deal with in the collections framework. Sep 24, 2010 at 16:18
4

You could extend the existing java.util.ArrayList and encapsulate a java.util.Set in it. You should override all add(...), addAll(...) and remove methods and first check if an element is in the encapsulated set (in the case of adding it to the list):

public class ListSet<E> extends ArrayList<E> {

    private Set<E> set;

    public ListSet() {
        set = new HashSet<E>();
    }

    @Override
    public boolean add(E element) {
        if(set.add(element)) {
            super.add(element);
            return true;
        }
        return false;
    }

    // other add and remove methods
}

EDIT

As @Alnitak mentioned: don't forget to sync your backing HashSet whenever an element is removed.

2
  • 1
    I like this, and it's how I would have done it. This specifically maintains all of the semantics of a List, whilst enforcing the no duplicates constraint (albeit at the cost of some memory). p.s. don't forget to sync your backing HashSet whenever an element is removed...
    – Alnitak
    Sep 24, 2010 at 10:17
  • I was thinking about doing something very similar, but I'm hung up on you would implement the add(index, E) implementation. I'd imagine that if you find a duplicate of E in the data, then you fail inserting at the position. The List<E> interface for add(index, E) returns back void, so you can't report back this failed condition.
    – C Nick
    Jan 11, 2013 at 16:55
3

You want a Set maybe, e.g. HashSet(), rather than a List? No List will eliminate duplicates, by definition Lists permit them.

2

Do not, like someone suggested, implement your own List that does duplicate check and returns false if there is a duplicate at add().

Why? Because you will BREAK the List interface contract which says:

public boolean add(E e)
[...]
Returns:
         true (as specified by Collections.add())

List.add(E e) MUST return true and add the element to the list, or throw an exception. Lists are not meant to have duplicate checks, that is what Sets are for.

1

At the time you can make your own class and @Override add method to your class. "just see my code and practice it"

import java.util.ArrayList;

import java.util.List;

class MyList extends ArrayList<Integer> {

    private static final long serialVersionUID = 1L;

    @Override
    public boolean add(Integer element) {

        if (!found(element)) {
            super.add(element);
        }
        return false;

    }
    public boolean found(Integer e) {
        return equals(e);
    }
    public boolean equals(Integer e) {

        for (int i = 0; i < super.size(); i++) {
            if (super.get(i).equals(e))
                return true;
        }

        return false;
    }

}

public class ListRemovingDuplicated {

    public static void main(String[] abd) {

        List<Integer> obj = new MyList();
        obj.add(10);
        obj.add(20);
        obj.add(10);
        obj.add(10);
        obj.add(30);
        System.out.println(obj);

    }
}
0

Here is an extension of ArrayList that rejects duplicates:

public class NoDupeList<E> extends ArrayList<E>{

    private static final long serialVersionUID = -2682691450003022201L;

    public NoDupeList(){
        super();
    }

    public NoDupeList(final Collection<? extends E> c){
        super(c instanceof Set<?> ? c : new LinkedHashSet<E>(c));
    }

    public NoDupeList(final int initialCapacity){
        super(initialCapacity);
    }

    @Override
    public boolean add(final E e){
        return !this.contains(e) && super.add(e);
    };

    @Override
    public boolean addAll(final Collection<? extends E> c){
        final List<E> intermediate = new ArrayList<E>(c);
        intermediate.removeAll(this);
        return super.addAll(intermediate);
    }

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

    @Override
    public E set(final int index, final E element){
        if(this.contains(element) && !this.get(index).equals(element)){
            throw new IllegalArgumentException("This would cause a duplicate");
        }
        return super.set(index, element);
    };

}

The only thing I can't deal with is the set() method. My solution is to throw an IllegalArgumentException if that would cause a duplicate, but perhaps one should generally let this method throw an UnsupportedOperationException instead.

Anyway, here's a test method:

@Test
public void testNoDupeList() throws Exception{
    final List<String> list =
        new NoDupeList<String>(Arrays.asList("abc", "def", "abc"));
    assertEquals(list, Arrays.asList("abc", "def"));
    list.addAll(Arrays.asList("abc", "def", "ghi"));
    assertEquals(list, Arrays.asList("abc", "def", "ghi"));
    try{
        list.set(2, "abc");
        fail("This should have caused an Exception");
    } catch(final Exception e){}
};
0

The easiest way to get an actual List that is sorted and has no duplicates would be to wrap it like this:

List<Integer> unique = 
  new ArrayList<Integer>(new TreeSet<Integer>(Arrays.asList(1, 1, 2, 2, 3, 3)));

Note that when you add to this list duplicates will not be eliminated though, but maybe this works for you.

Not the answer you're looking for? Browse other questions tagged or ask your own question.