Find objects in a list where some attributes have equal values

Question

Given a list of objects (all of the same type), how can I make sure that it contains only one element for each value of a certain attribute, even though equals() may return false for such elements due to more attributes being checked? In code:

private void example() {
    List<SomeType> listWithDuplicates = new ArrayList<SomeType>();

    /*
     * create the "duplicate" objects. Note that both attributes passed to 
     * the constructor are used in equals(), though for the purpose of this 
     * question they are considered equal if the first argument was equal
     */
    SomeType someObject1 = new SomeObject1("hello", "1");
    SomeType someObject2 = new SomeObject1("hello", "2");

    List<SomeType> listWithoutDuplicates = removeDuplicates(listWithDuplicates)
    //listWithoutDuplicates should not contain someObject2
}

private List<SomeType> removeDuplicates(List<SomeType> listWithDuplicates) {
    /*
     * remove all but the first entry in the list where the first constructor-
     * arg was the same
     */
}

Anurag · Accepted Answer · 2010-01-06T11:54:28.433

Could use a Set as an intermediary placeholder to find the duplicates as Bozho suggested. Here's a sample removeDuplicates() implementation.

private List<SomeType> removeDuplicates(List<SomeType> listWithDuplicates) {
    /* Set of all attributes seen so far */
    Set<AttributeType> attributes = new HashSet<AttributeType>();
    /* All confirmed duplicates go in here */
    List duplicates = new ArrayList<SomeType>();

    for(SomeType x : listWithDuplicates) {
        if(attributes.contains(x.firstAttribute())) {
            duplicates.add(x);
        }
        attributes.add(x.firstAttribute());
    }
    /* Clean list without any dups */
    return listWithDuplicates.removeAll(duplicates);
}

score 1 · Answer 2 · answered Jan 06 '10 at 11:40

Maybe a HashMap can be used like this:

  private List<SomeType> removeDuplicates(List<SomeType> listWithDuplicates) {
   /*
   * remove all but the first entry in the list where the first constructor-
   * arg was the same
   */
   Iterator<SomeType> iter = listWithDuplicates.iterator();
   Map<String, SomeType> map = new HashMap<String, SomeType>();
   while(iter.hasnext()){
         SomeType i = iter.next();
         if(!map.containsKey(i.getAttribute())){
             map.put(i.getAttribute(), i);
         }
   }
   //At this point the map.values() is a collection of objects that are not duplicates.



  }

Would probably work, but I would lose the ordering of the list. I'll have to check whether this is an issue in my case. — Thomas Lötzer, Jan 06 '10 at 11:58

score 0 · Answer 3 · answered Jan 06 '10 at 11:35

If equals() were suitable, I could recommend some "standard" Collections classes/methods. As it is, I think your only option will be to either

copy each element to another list after first checking all preceding elements in the original list for duplicates; or
delete from your list any element for which you've found a duplicate at a preceding location. For in-list deletion, you'd be best off with using a LinkedList, where deletion isn't so expensive.

In either case, checking for duplicates will be an O(n^2) operation, alas.

If you're going to be a lot of this kind of operation, it might be worthwhile to wrap your list elements inside another class that returns a hashcode based on your own defined criteria.

score 0 · Answer 4 · edited May 23 '17 at 11:52

0

I'd look at implementing the Comparator interface for something like this. If there's a simple attribute or two that you wish to use for your comparison, that makes it pretty straightforward.

Related question: How Best to Compare Two Collections in Java and Act on Them?

edited May 23 '17 at 11:52

Community

1
1

answered Jan 06 '10 at 12:00

Ben

7,548
31
45

Find objects in a list where some attributes have equal values

4 Answers4