Iterate two lists and find matches

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

• What's the nature of the condition? Does it involve both list elements or is it unrelated? – chatton Jan 26 '18 at 7:50
• It includes elements from both lists – XtremeBaumer Jan 26 '18 at 7:51
• If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though – chatton Jan 26 '18 at 8:05
• @chatton This is sadly not an option. I think I have to iterate both lists like this – XtremeBaumer Jan 26 '18 at 8:15
• As you are dealing with lists the resulting algorithm complexity will be O(n*m). For better performance compose and return maps from findUnmatchedEntries() and use them in your names comparison mechanism. Use names as map keys and class (MyClass1 and MyClass2) objects as map values. – user23908 Jan 26 '18 at 11:10

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.

• "...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by? – Sᴀᴍ Onᴇᴌᴀ Jun 26 '18 at 14:54

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.

• The reason i named them differntly here is because htey are different classes – XtremeBaumer Jan 26 '18 at 15:49
• If name+id concatenated can be unique, then create a hashmap<string, string> or Set ? – Tanvi Jaywant Jan 26 '18 at 15:52