Consider implementing a method that returns the difference between two Lists

Introduction

In this article, I will introduce a small story about Java that I usually use at work.

Problem setting

Suppose you want to implement a method that "removes elements in one list 1 from elements in another list 2". There are several situations in which such a feature can be useful. For example, when implementing a function to recommend a user in a Web service, put the ID of the user who is a candidate for recommendation in Listing 1 and the ID of the user who should be excluded from the recommendation candidate for some reason in Listing 2, and the final user. It is used to present the recommendation results.

――Hereafter, we will proceed with the list elements as Integer type, but it is not limited to Integer type in particular, and there is no problem even if it is complicated like `List <String>`. --Each list shall not contain duplicate elements. (From a practical point of view, think of such duplication as being eliminated before the method is called.)

Collection#removeAll The first method implementation I came up with was:

1st

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    list1.removeAll(list2);
    return list1;
}

It's concise and easy to read, but it's less desirable because you've changed the arguments. It is possible to copy the list with the `` `clone``` method, but this time we will consider another method.

Another direction: Java 8 Stream API

Consider the following implementation using the Stream API introduced in Java 8. list1About the elements contained inlist2If not included in, the resultresultlistI will add it to.

2nd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2){
    final List<List<Integer>> resultList = new ArrayList<>();
    list1.stream()
        .filter(p -> {
            return (! list2.contains(p));
        })
        .forEach(p -> {
            resultList.add(p);
        });
    return resultList;
}

There are likely to be some improvements in this implementation as well.

--`new ArrayList <> (); You can pass the result of` `list1.stream ()` to resultListas it is without creating a new instance with` ``. --Calling the `` `.contains ()` `` method on a list requires processingO (n) ``` (Java 8 streams how to filter contents a List not found in another arrayList? )

Regarding the second point, in the above implementation, `list2.contains ()` is called for each element of `list1```, so in total ```O (n) ^ 2) It will be necessary to process . ([java /util/AbstractCollection.java](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractCollection.java#AbstractCollection.contains) In% 28java.lang.Object% 29), you can see that `` .contains ()` `` follows each element one by one.)

AbstractCollection.java

98     public boolean More ...contains(Object o) {
99         Iterator<E> e = iterator();
100        if (o==null) {
101            while (e.hasNext())
102                if (e.next()==null)
103                    return true;
104        } else {
105            while (e.hasNext())
106                if (o.equals(e.next()))
107                    return true;
108        }
109        return false;
110    }

Third honesty: .contains () for Set

Consider the following implementation, which improves the above points. Using `.contains ()` for Set, the process of determining whether the element of `list1``` is included in ``` list2``` is ```O (1) I was able to suppress it to `.

3rd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    final HashSet<Integer> list2Set = new HashSet<>(list2);
    final List<Integer> resultList = list1.stream()
            .filter(p -> {
                return (! list2Set.contains(p));
            })
            .collect(Collectors.toList());
    return resultList;
}

By the way

In Apache Commons Collections, [ListUtils.java](https://commons.apache.org/proper/commons- In collections / apidocs / src-html / org / apache / commons / collections4 / ListUtils.html), the `` `subtract``` method is defined as follows.

python

110    /**
111     * Subtracts all elements in the second list from the first list,
112     * placing the results in a new list.
113     * <p>
114     * This differs from {@link List#removeAll(Collection)} in that
115     * cardinality is respected; if <Code>list1</Code> contains two
116     * occurrences of <Code>null</Code> and <Code>list2</Code> only
117     * contains one occurrence, then the returned list will still contain
118     * one occurrence.
119     *
120     * @param <E> the element type
121     * @param list1  the list to subtract from
122     * @param list2  the list to subtract
123     * @return a new list containing the results
124     * @throws NullPointerException if either list is null
125     */
126    public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) {
127        final ArrayList<E> result = new ArrayList<E>();
128        final HashBag<E> bag = new HashBag<E>(list2);
129        for (final E e : list1) {
130            if (!bag.remove(e, 1)) {
131                result.add(e);
132            }
133        }
134        return result;
135    }