Difference between List items

Question

i have two lists ListOne and ListTwo. I have to find out all the elements of ListOne which does not exist in ListTwo. Similarly I have to find out all the elements of ListTwo which does not exist in ListOne .

My below code is working , but i am thinking there might be some better way

        List<Long> listOne=...Some valid values;
        List<Long> listTwo=...Some valid values;
        List<Long> listThree=new ArrayList<Long>();
        List<Long> listFour=new ArrayList<Long>();

    for (Long id: ListOne) {
        if(!listTwo.contains(id)){
            listThree.add(id);
        }
    }

    for (Long id: ListTwo) {
        if(!listOne.contains(id)){
            listFour.add(id);
        }
    }

Possible answer : https://stackoverflow.com/a/13718621/4994582 — Bikramjit Rajbongshi, Nov 06 '17 at 12:21
Possible duplicate of [How can I calculate the difference between two ArrayLists?](https://stackoverflow.com/questions/919387/how-can-i-calculate-the-difference-between-two-arraylists) — Kaustubh Khare, Nov 06 '17 at 12:21
Possible duplicate of [How to do union, intersect, difference and reverse data in java](https://stackoverflow.com/questions/3590677/how-to-do-union-intersect-difference-and-reverse-data-in-java) — Joe, Nov 06 '17 at 12:23
Also note that for length of first list `m` and second `n`, this will have `m*n` time complexity. If the lists are short, no problem. However, it could prove troublesome with long lists. — Vlasec, Nov 06 '17 at 12:32
You are describing an algebra of sets operation, difference. You should be using a java.util.Set implementation. If you can use Guava, com.google.common.collect.Sets is a nice class with sets utilities. — jpangamarca, Apr 22 '21 at 16:34

score 3 · Answer 1 · edited Nov 06 '17 at 12:55

3

Below should work for you

List<Long> listOne =...Some valid values;
List<Long> listTwo =...Some valid values;

List<Long> listThree = new ArrayList<>(listOne);
List<Long> listFour = new ArrayList<>(listTwo);
listThree.removeAll(listTwo);
listFour.removeAll(listOne);

From the java doc:

RemoveAll: Removes from this list all of its elements that are contained in the specified collection (optional operation).

edited Nov 06 '17 at 12:55

davidxxx

125,838
23
214
215

answered Nov 06 '17 at 12:26

Lino

19,604
6
47
65

Nice to mention both, but `removeAll` is what OP asked for. – Vlasec Nov 06 '17 at 12:35
`removeAll()` simplifies really the processing. Nicer but your code modification has a mistake. You perform the operation on `listTwo`, the existing list. – davidxxx Nov 06 '17 at 12:46
@davidxxx oh yeah i removed too much when I edited it. Thanks! – Lino Nov 06 '17 at 12:53

score 3 · Answer 2 · answered Nov 06 '17 at 12:32

3

As alternative to Lino answer, you can also rewrite your code in a functional way :

List<Long> listOneButListTwoElements = listOne.stream()
        .filter(l-> !listTwo.contains(l))
        .collect(Collectors.toList());


List<Long> listTwoButListOneElements = listTwo.stream()
        .filter(l-> !listOne.contains(l))
        .collect(Collectors.toList());

answered Nov 06 '17 at 12:32

davidxxx

125,838
23
214
215

Yea, it is nice. It is still iterating a list in every step of the cycle though. – Vlasec Nov 06 '17 at 12:35
Vlasec is right. This is O(n²). It would be a good idea to create a temporary Set from each list and use the set instead of the list in the `.contains(l)` calls. – Klitos Kyriacou Nov 06 '17 at 12:37
1

Yep, I actually wrote an answer of my own. The part with stream barely differs though, if only you could write `filterOut(setTwo::contains)` :) – Vlasec Nov 06 '17 at 12:43
@Vlasec I agree. A straight way to request a reverse filtering is really missing. – davidxxx Nov 06 '17 at 12:54
@Vlasec and Klitos Kyriacou Good point to mention. About complexity drawback, it is right but it may become a problem only if you have a list with many elements. The OP doesn't specify this point. – davidxxx Nov 06 '17 at 12:59

Vlasec · Answer 3 · 2017-11-07T16:49:10.310

3

To be really efficient, you could do something like that:

Set<Long> setOne = new HashSet<>(listOne);
Set<Long> setTwo = new HashSet<>(listTwo);

List<Long> listThree = listOne.stream()
        .filter(e -> !setTwo.contains(e))
        .collect(Collectors.toList());
List<Long> listFour = listTwo.stream()
        .filter(e -> !setOne.contains(e))
        .collect(Collectors.toList());

This way you avoid the problem with m*n complexity for list lengths m and n.

Edit: If you prefer having no intermediary variables (as @davidxxx mentioned), you could do it like:

List<Long> listThree = listOne.stream()
        .filter(not(new HashSet(listTwo)::contains))
        .collect(Collectors.toList());

There are various ways to negate a predicate. No need to cover it here, it has been answered.

edited Nov 07 '17 at 16:49

answered Nov 06 '17 at 12:39

Vlasec

5,500
3
27
30

2

for big Lists this is perfect, but for small lists I'm guessing this might be a bit overkill – Lino Nov 06 '17 at 12:45
1

Nice improvement +1. But I agree with Lino. Introducing additional intermediary variables defeats in a some way the functional programming paradigm. It should be done only if required. – davidxxx Nov 06 '17 at 12:50
I agree, it looks better if you can write it declaratively, with no extra variables. I often prefer to write code like that. Now that I think of it, what a pity there is no opposite of `filter` called `filterOut` or something, then you could just put the sets inside like `.filterOut(new HashSet<>(listOne)::contains)` :) – Vlasec Nov 06 '17 at 13:44
Wouldn't that create a new HashSet for every element in the streamed list? – Klitos Kyriacou Nov 06 '17 at 20:30
@KlitosKyriacou Not really. It would, if it was inside the lambda. But the way I wrote it, it is a method reference and it refers to method `contains` of the new object. – Vlasec Nov 07 '17 at 15:50
@Vlasec yes, it's a method reference, equivalent to `e -> new HashSet<>(listOne).contains(e)`. But this lambda would be applied (evaluated) by the `filterOut` method. When applied, it will create a new HashSet. It is applied for every element, therefore a new HashSet is created every time. – Klitos Kyriacou Nov 07 '17 at 16:04
@KlitosKyriacou The lambda would be equivalent if it was an already existing object. But this is an expression that creates one. Feel free to try out, too. – Vlasec Nov 07 '17 at 16:33
@Vlasec I see what you mean. This demonstrates that method references are not just syntactic sugar for lambdas. Thanks! – Klitos Kyriacou Nov 07 '17 at 16:39
I suppose, in absence of a `filterOut` method, you could define `static Predicate not(Predicate predicate) { return predicate.negate(); }` and then use `.filter(not(new HashSet<>(listOne)::contains))` :) – Klitos Kyriacou Nov 07 '17 at 16:43
@KlitosKyriacou Yes, such a negation method was mentioned in https://stackoverflow.com/questions/21488056/how-to-negate-a-method-reference-predicate - How to negate a method reference predicate. I know that topic quite well :) – Vlasec Nov 07 '17 at 16:44

Difference between List items

3 Answers3