Compare two different arraylists and get differences java

Question

I've got two arraylists, and I'm looking for an efficient way to count the number of different values.

Some example lists:

List<String> list = new ArrayList<String>();
    list.add("String A");
    list.add("String B");
    list.add("String C");

List<String> anotherlist = new ArrayList<String>();
    list.add("String B");
    list.add("String A");
    list.add("String D");

You could do something to check for each item (because the order should not matter) if it is the same or not (pure conceptual):

    for(int i=0;i<list.size();i++)
    {
             for(int j=0;j<anotherlist.size();j++)
             {
                   if (item.get(i) == item.get(j)){
                       intDifferent = intDifferent+1;
                   } else {
                       intSame = intSame+1;
                   }
                   intTotal = intTotal+1
             }
    }

    //Some calculations with intdifferent en inttotal to find out how many different 
    //values we actually have  between the lists, in the case of the example, it 
    //should output 1

Is there a more efficient way to do this? Or is there a sample or post available on how to accomplish this?

score 0 · Answer 1 · answered Apr 01 '14 at 18:49

0

You should look at using Sets for this.

Drop all the items from one array into a HashSet and then loop over the other array checking if it is contained in the Set.

This will be much faster than looping over an ArrayList each time.

answered Apr 01 '14 at 18:49

Tim B

40,716
16
83
128

Please tell him also to compare strings via equals. – Seelenvirtuose Apr 01 '14 at 18:52
@Seelenvirtuose you are correct of course but using my suggestion he doesn't do any comparison himself at all :) – Tim B Apr 01 '14 at 19:06
I know. Hash data structures at its best. :-) – Seelenvirtuose Apr 01 '14 at 19:10

score 0 · Answer 2 · answered Apr 01 '14 at 18:59

The following algorithm worst case complexity is O(n* log(n))

    // worst case O(nLog(n))
    Collections.sort(l1);
    // worst case O(nLog(n))
    Collections.sort(l2);

    // pointer for l1 list
    int p = 0;

    // pointer for l2 list
    int q = 0;

    int diffCounter = 0;
    // worst case N
    while (true) {

        if (p == l1.size() -1 ) {
            // remainig items in l2 list are diff
            diffCounter += (l2.size() -1) - q;
            break;
        }
        if (q == l2.size() -1 ) {
            diffCounter += (l1.size() - 1) - p;
        }

        int compareResult = l1.get(p).compareTo(l2.get(q));
        if (compareResult > 0) {
            p++;
            diffCounter++;
        } else if (compareResult < 0 ) {
            q++;
            diffCounter++;
        }

`

Compare two different arraylists and get differences java

2 Answers2