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

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

  • 2
    \$\begingroup\$ What's the nature of the condition? Does it involve both list elements or is it unrelated? \$\endgroup\$
    – chatton
    Commented Jan 26, 2018 at 7:50
  • \$\begingroup\$ It includes elements from both lists \$\endgroup\$ Commented Jan 26, 2018 at 7:51
  • \$\begingroup\$ 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 \$\endgroup\$
    – chatton
    Commented Jan 26, 2018 at 8:05
  • \$\begingroup\$ @chatton This is sadly not an option. I think I have to iterate both lists like this \$\endgroup\$ Commented Jan 26, 2018 at 8:15
  • \$\begingroup\$ 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. \$\endgroup\$
    – user23908
    Commented Jan 26, 2018 at 11:10

2 Answers 2


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.

  • \$\begingroup\$ "...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by? \$\endgroup\$ Commented Jun 26, 2018 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.

  • 1
    \$\begingroup\$ The reason i named them differntly here is because htey are different classes \$\endgroup\$ Commented Jan 26, 2018 at 15:49
  • \$\begingroup\$ If name+id concatenated can be unique, then create a hashmap<string, string> or Set ? \$\endgroup\$ Commented Jan 26, 2018 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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