Skip to content

remove (and count) duplicates from a list

Is it possible to iterate between two iterators of a same list and remove an item within the nested iterator?

Version 1 (does not work):

var i = all.iterator();
while (i.hasNext()) {
    var a = i.next();
    var j = all.iterator();
    while (j.hasNext()) {
        var b = j.next();
        if (!a.shouldBRemoved(b)) {
            a.setDuplicates(a.getDuplicates + 1);
            // I want to remove the element on the fly 
            // because on each iteration the iterated elements will have a decreased size and will iterate faster (because of fewer elements)
            // However: this does NOT work because of ConcurrentModificationException:
            j.remove();  
        }
    }

}

I get a java.util.ConcurrentModificationException, because I modify an element within the same iterator..

I can solve this issue by using another list removableItems and put those items in it:

Version 2 (works):

for (var a : all) {
    for (var b : all) {
        if (!a.shouldBRemoved(b)) {
            a.setDuplicates(a.getDuplicates + 1);
            // this works, 
            // however I must use an additation list to keep track of the items to be removed
            // it's also not more performant than removing the elements on the fly 
            // because on each iteration the iterated elements has the same size
            removableItems.add(b);
        }
    }
}
all.removeAll(removableItems);
    

Is there a way to solve this without needing an intermediate list removableItems? I want to remove the element on the fly.

Answer

I found a good solution so far (Version 3):

List<Item> removeDuplicates(List<Item> all) {
        var uniqueResults = new ArrayList<Item>();
        for (var a : all) {
            for (var b : all) {
                // check if "a" and "b" is not the same instance, but have equal content
                if (!a.equals(b) && a.isDeepEqualTo(b)) {
                    if (a.duplicates == 0 && b.duplicates == 0) {
                        // "a" has duplicates: 
                        // Add only "a" and discard "b" for the rest of the loops.
                        uniqueResults.add(a);
                    }
                    // count the number of duplicates
                    a.duplicates = a.duplicates + 1;
                }
            }
            // "a" has no duplicates, add it.
            if (a.duplicates == 0 && !uniqueResults.contains(a)) {
                uniqueResults.add(a);
            }
        }
        return uniqueResults;
}

It works so far – I don’t see any edge cases where this would wrongly (not) remove.

It’s also better than using version 2 (with its removableItems()-list) as this is more performant (especially for huge lists) because we do not use remove or removAll, we only add items (which has O(1)).