0

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);
        }
    }
user2555212
  • 165
  • 1
  • 14
  • 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
  • 2
    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

3 Answers3

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).

davidxxx
  • 125,838
  • 23
  • 214
  • 215
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
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());
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
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.

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