How can I calculate the difference between two ArrayLists?

Question

I have two ArrayLists.

ArrayList A contains:

['2009-05-18','2009-05-19','2009-05-21']

ArrayList B contains:

['2009-05-18','2009-05-18','2009-05-19','2009-05-19','2009-05-20','2009-05-21','2009-05-21','2009-05-22']

I have to compare ArrayList A and ArrayList B. The result ArrayList should contain the List which does not exist in ArrayList A.

ArrayList result should be:

['2009-05-20','2009-05-22']

how to compare ?

score 200 · Accepted Answer · edited Mar 19 '16 at 23:52

200

In Java, you can use the Collection interface's removeAll method.

// Create a couple ArrayList objects and populate them
// with some delicious fruits.
Collection firstList = new ArrayList() {{
    add("apple");
    add("orange");
}};

Collection secondList = new ArrayList() {{
    add("apple");
    add("orange");
    add("banana");
    add("strawberry");
}};

// Show the "before" lists
System.out.println("First List: " + firstList);
System.out.println("Second List: " + secondList);

// Remove all elements in firstList from secondList
secondList.removeAll(firstList);

// Show the "after" list
System.out.println("Result: " + secondList);

The above code will produce the following output:

First List: [apple, orange]
Second List: [apple, orange, banana, strawberry]
Result: [banana, strawberry]

edited Mar 19 '16 at 23:52

Basil Bourque

303,325
100
852
1,154

answered May 28 '09 at 06:14

William Brendel

31,712
14
72
77

8

If your list is of a custom class, then you'll have to override the equals method of your class, right? – RTF Oct 21 '14 at 15:51
6

@RTF Yes, you need to provide an implementation of [`equals`](http://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-) that enables your objects to be compared. Read about implementing [`hashCode`](http://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--) as well. For example, note how [`String::equals`](http://docs.oracle.com/javase/8/docs/api/java/lang/String.html#equals-java.lang.Object-) is [case-sensitive](https://en.wikipedia.org/wiki/Case_sensitivity), so "apple" and "Apple" will not be considered the same. – Basil Bourque Mar 20 '16 at 00:58
1

Actually the answer depends on what you want to do. RemoveAll will not preserve duplicates. If you add another "apple" string to your second list, it will be removed as well, which may not always be what you want. – jules testard Jun 01 '16 at 18:13
2

This is so inefficient. It's sad this is both the selected and best rated answer. `removeAll` calls `firstList.contains` on every element of `secondList`. Using a `HashSet` would prevent that and there are a few good answers lower. – Vlasec Feb 09 '18 at 22:20

score 20 · Answer 2 · edited Nov 08 '13 at 23:47

20

You already have the right answer. And if you want to make more complicated and interesting operations between Lists (collections) use apache commons collections (CollectionUtils) It allows you to make conjuction/disjunction, find intersection, check if one collection is a subset of another and other nice things.

edited Nov 08 '13 at 23:47

Kirby

15,127
10
89
104

answered May 28 '09 at 07:24

unorsk

9,371
10
36
42

Maven/Gradle: https://mvnrepository.com/artifact/org.apache.commons/commons-collections4/4.1 – Wlad Sep 12 '16 at 13:26

Vlasec · Answer 3 · 2019-09-05T12:22:06.803

13

In Java 8 with streams, it's pretty simple actually. EDIT: Can be efficient without streams, see lower.

List<String> listA = Arrays.asList("2009-05-18","2009-05-19","2009-05-21");
List<String> listB = Arrays.asList("2009-05-18","2009-05-18","2009-05-19","2009-05-19",
                                   "2009-05-20","2009-05-21","2009-05-21","2009-05-22");

List<String> result = listB.stream()
                           .filter(not(new HashSet<>(listA)::contains))
                           .collect(Collectors.toList());

Note that the hash set is only created once: The method reference is tied to its contains method. Doing the same with lambda would require having the set in a variable. Making a variable is not a bad idea, especially if you find it unsightly or harder to understand.

You can't easily negate the predicate without something like this utility method (or explicit cast), as you can't call the negate method reference directly (type inference is needed first).

private static <T> Predicate<T> not(Predicate<T> predicate) {
    return predicate.negate();
}

If streams had a filterOut method or something, it would look nicer.

Also, @Holger gave me an idea. ArrayList has its removeAll method optimized for multiple removals, it only rearranges its elements once. However, it uses the contains method provided by given collection, so we need to optimize that part if listA is anything but tiny.

With listA and listB declared previously, this solution doesn't need Java 8 and it's very efficient.

List<String> result = new ArrayList(listB);
result.removeAll(new HashSet<>(listA));

edited Sep 05 '19 at 12:22

answered Nov 07 '17 at 17:13

Vlasec

5,500
3
27
30

1

@Bax Why the edit? The original was cleaner and functionally identical. – shmosel Jan 02 '18 at 23:46
1

@Bax No, it doesn't. – shmosel Jan 03 '18 at 00:57
1

With Guava, you can do `Predicates.in(new HashSet<>(listA)).negate()`. – shmosel Jan 03 '18 at 17:43
Thanks @shmosel. Yes, I prefer declarative approach over imperative where applicable. Often even a long chain can be more readable than a broken chain with variables. – Vlasec Feb 09 '18 at 21:33
I think the way I create the predicate could be confusing to some though. It is a funny shortcut of creating a set outside, and it might be a bit unsightly. But thanks to how a method reference works, only one set will be created. This is probably the only notable case where a method reference differs from lambda - when the method is called on a result of an expression. – Vlasec Feb 09 '18 at 21:47
@Vlasec you are a beautiful person. Where can I read more about object instantiation and lambda methods in java like you mentioned? – AndrewD Oct 17 '18 at 04:30
@AndrewD I linked my other answer that is about predicate negation. I delved much deeper into lambda / method references there. – Vlasec Oct 19 '18 at 11:44
1

I just run some test and this solutions is ~10-20% faster than listB.removeAll(new HashSet<>(listA)). and Guava Sets.difference(...) si 2 times slower than streams. – telebog Jul 31 '19 at 15:30
Tests are always nice, but their results will vary greatly with list size. I'd bet on `ArrayList` where lists are very small (around 10 entries). But its `remove` has linear complexity, so `LinkedList` start beating it very shortly after with constant complexity. Anyway, all JDK lists I know have linear complexity on `contains` method where the `HashSet` method is considered (in best case) constant complexity. That means that `removeAll` has quadratic complexity on lists, but linear on a `HashSet`. In a huge collection (millions of entries) it could be more than 90% faster. – Vlasec Aug 14 '19 at 09:06
1

@Vlasec `ArrayList.remove` has linear complexity, but `ArrayList.removeAll` does not rely on `remove` but performs a linear array update operation, copying each remaining element into its final place. In contrast, the reference implementation of `LinkedList` has no optimized `removeAll` but performs a `remove` operation for each affected element, which will update up to five references each time. So, depending on the ratio between removed and remaining elements, `ArrayList`’s `removeAll` may still perform significantly better than `LinkedList`’s, even for huge lists. – Holger Aug 27 '19 at 08:41
@Holger Thanks for info, I didn't know that part. That makes `removeAll` on `ArrayList` actually quite efficient, as it only rearranges the array once. That gave me an idea and I'm updating my answer. – Vlasec Sep 04 '19 at 17:12
1

@Vlasec You can't make it a one-liner: ArrayList's [removeAll](https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#removeAll(java.util.Collection)) returns a boolean, not an ArrayList or Collection. – Avi Sep 04 '19 at 17:38

Josh · Answer 4 · 2009-05-28T06:24:34.877

EDIT: Original question did not specify language. My answer is in C#.

You should instead use HashSet for this purpose. If you must use ArrayList, you could use the following extension methods:

var a = arrayListA.Cast<DateTime>();
var b = arrayListB.Cast<DateTime>();    
var c = b.Except(a);

var arrayListC = new ArrayList(c.ToArray());

using HashSet...

var a = new HashSet<DateTime>(); // ...and fill it
var b = new HashSet<DateTime>(); // ...and fill it
b.ExceptWith(a); // removes from b items that are in a

score 8 · Answer 5 · edited May 23 '17 at 12:26

8

I have used Guava Sets.difference.

The parameters are sets and not general collections, but a handy way to create sets from any collection (with unique items) is Guava ImmutableSet.copyOf(Iterable).

(I first posted this on a related/dupe question, but I'm copying it here too since I feel it is a good option that is so far missing.)

edited May 23 '17 at 12:26

Community

1
1

answered Sep 02 '14 at 04:55

Peter Lamberg

8,151
3
55
69

score 8 · Answer 6 · edited Apr 18 '19 at 01:41

8

Although this is a very old question in Java 8 you could do something like

 List<String> a1 = Arrays.asList("2009-05-18", "2009-05-19", "2009-05-21");
 List<String> a2 = Arrays.asList("2009-05-18", "2009-05-18", "2009-05-19", "2009-05-19", "2009-05-20", "2009-05-21","2009-05-21", "2009-05-22");

 List<String> result = a2.stream().filter(elem -> !a1.contains(elem)).collect(Collectors.toList());

edited Apr 18 '19 at 01:41

Chintan Soni

24,761
25
106
174

answered Oct 11 '16 at 12:15

jesantana

1,241
2
14
27

I love Java 8, but we should still think of complexity. While lists also have `Collection`'s method `contains`, it is very inefficient. It needs to pass through the whole list if not found. Doing it for every element of `a2` can be painfully slow on larger lists, which is why I make a set out of `a1` in my answer. – Vlasec Jun 11 '18 at 11:57

score 2 · Answer 7 · answered May 28 '09 at 06:12

2

I guess you're talking about C#. If so, you can try this

    ArrayList CompareArrayList(ArrayList a, ArrayList b)
    {
        ArrayList output = new ArrayList();
        for (int i = 0; i < a.Count; i++)
        {
            string str = (string)a[i];
            if (!b.Contains(str))
            {
                if(!output.Contains(str)) // check for dupes
                    output.Add(str);
            }
        }
        return output;
    }

answered May 28 '09 at 06:12

Pavels

1,256
1
12
19

Sorry I did not mention the progrsmming language,it's ok ,but i need for java thanks for ur replay – naveen May 28 '09 at 06:25
This is correct. It is also a very inefficient way of doing it though. You'll basically cycle through the whole `b` list `a.Count` times. You could create a `HashSet` instead to use for the `Contains` or use the `RemoveAll` method on the set to get exactly the results you want. – Vlasec Feb 09 '18 at 22:05

score 1 · Answer 8 · edited Sep 24 '15 at 19:19

Hi use this class this will compare both lists and shows exactly the mismatch b/w both lists.

import java.util.ArrayList;
import java.util.List;


public class ListCompare {

    /**
     * @param args
     */
    public static void main(String[] args) {
        List<String> dbVinList;
        dbVinList = new ArrayList<String>();
        List<String> ediVinList;
        ediVinList = new ArrayList<String>();           

        dbVinList.add("A");
        dbVinList.add("B");
        dbVinList.add("C");
        dbVinList.add("D");

        ediVinList.add("A");
        ediVinList.add("C");
        ediVinList.add("E");
        ediVinList.add("F");
        /*ediVinList.add("G");
        ediVinList.add("H");
        ediVinList.add("I");
        ediVinList.add("J");*/  

        List<String> dbVinListClone = dbVinList;
        List<String> ediVinListClone = ediVinList;

        boolean flag;
        String mismatchVins = null;
        if(dbVinListClone.containsAll(ediVinListClone)){
            flag = dbVinListClone.removeAll(ediVinListClone);   
            if(flag){
                mismatchVins = getMismatchVins(dbVinListClone);
            }
        }else{
            flag = ediVinListClone.removeAll(dbVinListClone);
            if(flag){
                mismatchVins = getMismatchVins(ediVinListClone);
            }
        }
        if(mismatchVins != null){
            System.out.println("mismatch vins : "+mismatchVins);
        }       

    }

    private static String getMismatchVins(List<String> mismatchList){
        StringBuilder mismatchVins = new StringBuilder();
        int i = 0;
        for(String mismatch : mismatchList){
            i++;
            if(i < mismatchList.size() && i!=5){
                mismatchVins.append(mismatch).append(",");  
            }else{
                mismatchVins.append(mismatch);
            }
            if(i==5){               
                break;
            }
        }
        String mismatch1;
        if(mismatchVins.length() > 100){
            mismatch1 = mismatchVins.substring(0, 99);
        }else{
            mismatch1 = mismatchVins.toString();
        }       
        return mismatch1;
    }

}

Did you know that the clones are actually not clones at all? — Vlasec, Feb 09 '18 at 22:00

score 1 · Answer 9 · answered Mar 07 '16 at 15:36

THIS WORK ALSO WITH Arraylist

    // Create a couple ArrayList objects and populate them
    // with some delicious fruits.
    ArrayList<String> firstList = new ArrayList<String>() {/**
         * 
         */
        private static final long serialVersionUID = 1L;

    {
        add("apple");
        add("orange");
        add("pea");
    }};

    ArrayList<String> secondList = new ArrayList<String>() {

    /**
         * 
         */
        private static final long serialVersionUID = 1L;

    {
        add("apple");
        add("orange");
        add("banana");
        add("strawberry");
    }};

    // Show the "before" lists
    System.out.println("First List: " + firstList);
    System.out.println("Second List: " + secondList);

    // Remove all elements in firstList from secondList
    secondList.removeAll(firstList);

    // Show the "after" list
    System.out.println("Result: " + secondList);

the output: First List: [apple, orange, pippo] Second List: [apple, orange, banana, strawberry] Result: [banana, strawberry] — psycho, Mar 07 '16 at 15:45
It does. But when you say so, you shouldn't forget to note that it can be painfully slow on large lists. Bear in mind that methods like `remove` and `contains` need to search through the whole list. If called repeatedly in a cycle (which happens in `removeAll`), you get a quadratic complexity. You could however use a hash set and have it just linear. — Vlasec, Feb 09 '18 at 21:58

Demi · Answer 10 · 2009-05-28T18:42:29.353

You are just comparing strings.

Put the values in ArrayList A as keys in HashTable A.
Put the values in ArrayList B as keys in HashTable B.

Then, for each key in HashTable A, remove it from HashTable B if it exists.

What you are left with in HashTable B are the strings (keys) that were not values in ArrayList A.

C# (3.0) example added in response to request for code:

List<string> listA = new List<string>{"2009-05-18","2009-05-19","2009-05-21'"};
List<string> listB = new List<string>{"2009-05-18","2009-05-18","2009-05-19","2009-05-19","2009-05-20","2009-05-21","2009-05-21","2009-05-22"};

HashSet<string> hashA = new HashSet<string>();
HashSet<string> hashB = new HashSet<string>();

foreach (string dateStrA in listA) hashA.Add(dateStrA);
foreach (string dateStrB in listB) hashB.Add(dateStrB);

foreach (string dateStrA in hashA)
{
    if (hashB.Contains(dateStrA)) hashB.Remove(dateStrA);
}

List<string> result = hashB.ToList<string>();

In your C# code, the `hashA` variable is effectively useless. You could make a foreach with `listA` instead as `hashA` is only iterated through and `Contains` is never called. — Vlasec, Feb 09 '18 at 21:51
(Also, provided that C# has a RemoveAll method like Java does, you could avoid making your own cycle ... but again, I upvoted you as this solution is at least way more efficient than the selected one.) — Vlasec, Jun 11 '18 at 11:47

How can I calculate the difference between two ArrayLists?

10 Answers10

Linked

Related