Iterate two lists and find matches

Question

I have 2 lists with varying length. Both lists contain data which has to be matched with entries from the other list. Currently I am iterating both lists with a nested for-loop.

List<MyClass1> list2 = myClass1dao.findUnmatchedEntries();
List<MyClass2> list1 = myClass2dao.findUnmatchedEntries();

for (MyClass2 list1entry : list1) {
    for (MyClass1 list2entry : list2) {
        if (list1entry.getName().equals(list2entry.getName())
            && list1entry.getID().equals(list2entry.getID())) {
            //update entries
            myClass2dao.update(list1entry);
            myClass1dao.update(list2entry);
            break;
        }
    }
}

I know that this takes exponentially longer the more elements each list has.

So my question is, how can this code be improved?

Note: I am on a java 7 code base so answers to java 7 are preferred, but java 8 is okay as well

Answer 1

I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.

Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.

Answer 2

I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.

In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.

This can reduce your time complexity.