How to merge two lists of objects by comparing field value in the given objects in Java

Question

I have two list of objects and I want to merge them into one. the objects have two fields, "name" and "value". For a given obj2 in list2 , if we find a match of "name" field of obj1 in list1 (obj1 from list1 and obj2 from list2), then we use the "value" of the obj2 to overwrite obj1. if there is no match found, then we add obj2 to list1. The final output will be updated list1.

Is there any fast way to do this? All I can think of is to use two for loops to compare all the objects in two lists

class NameValueObj{
String name;
String value;
}

List<NameValueObj> merge(List<NameValueObj> list1, List<NameValueObj> list2){
// I want to merge two list here
}

NameValueObj is a given so I can;t modify the object source.

Here is my way of doing it.

private List<Header> mergeHeaders(List<Header> defHeaders, List<Header> ovrdHeaders) {
        List<Header> lFinal = defHeaders;
        boolean foundMatch = false;
        for (Header ovrdHeader : ovrdHeaders) {
            foundMatch = false;
            for (Header defHeader : defHeaders) {
                if (defHeader.getName().equalsIgnoreCase(ovrdHeader.getName())) {
                    defHeader.setValue(ovrdHeader.getValue());
                    foundMatch = true;
                    break;
                }
            }
            if(!foundMatch) {
                lFinal.add(ovrdHeader);
            }

        }

        return lFinal;
    }

Header has name and value field. Headers has unique names in a given list.

Answer 1

Your algorithm is O(n*n) (quadratic).

You can do it in O(n) (linear) using a temporary LinkedHashMap:

private List<Header> mergeHeaders(final List<Header> defHeaders, final List<Header> ovrdHeaders) {
    final Map<String, Header> headersMap = new LinkedHashMap<String, Header>();

    for (final Header defHeader : defHeaders) {
        headersMap.put(defHeader.getName().toLowerCase(), defHeader);
    }

    for (final Header ovrdHeader : ovrdHeaders) {
        headersMap.put(ovrdHeader.getName().toLowerCase(), ovrdHeader);
    }

    return new ArrayList<Header>(headersMap.values());
}

Note that the behavior is NOT exactly the same as the behavior of your implementation. The differences are:

• This implementation returns a new list instance instead of modifying the first list. IMO, it's a benefit, but it may depend. If needed, you can modify the first list as follows (though I'd not recommend that):

  defHeaders.clear();
  defHeaders.addAll(headersMap.values());
  return defHeaders;
  

• This implementation assumes that header names are already unique (case INsensitively) in both lists, while your one doesn't make this assumption.
  If header names are not unique, this implementation would preserve the last header from list 1 or list 2.