List difference in java

Question

I have two ArrayList<Integer> as follows:

original: 12, 16, 17, 19, 101

selected: 16, 19, 107, 108, 109

I want to do difference on these lists such that in the end I have two lists:

Add: 108,109,107

remove: 12, 17, 101

Length of original and selected lists varies and one can be greater/smaller than the other

Answer 1

As an alternative, you could use CollectionUtils from Apache commons library. It has static intersection, union and subtract methods suitable for your case.

Answer 2

List<Integer> original = Arrays.asList(12,16,17,19,101);
List<Integer> selected = Arrays.asList(16,19,107,108,109);

ArrayList<Integer> add = new ArrayList<Integer>(selected);
add.removeAll(original);
System.out.println("Add: " + add);

ArrayList<Integer> remove = new ArrayList<Integer>(original);
remove.removeAll(selected);
System.out.println("Remove: " + remove);

Output:

Add: [107, 108, 109]
Remove: [12, 17, 101]

Uses Collection's removeAll method. See javadocs.

Answer 3

Intersection: original.retainAll(selected).

After that original will contain only elements present in both collections. Returns true if anything changed.

WARNING: This method is very slow for large collections

Answer 4

For intersection and union operations the natural collection type is a Set rather than a List, its also more efficient to use.

Answer 5

Using Guava library:

List<Integer> listA = Lists.newArrayList(12,16,17,19,101);
List<Integer> listB = Lists.newArrayList(16,19,107,108,109);
Set<Integer> intersection = Sets.intersection(Sets.newHashSet(listA), Sets.newHashSet(listB));
listA.removeAll(intersection);
listB.removeAll(intersection);

Answer 6

 List<Integer> original;
 List<Integer> selected;

 List<Integer> add = new ArrayList<Integer>(selected);
 add.removeAll(original);

 List<Integer> remove = new ArrayList<Integer>(original);
 remove.removeAll(selected);

Be careful with border cases around duplicate elements. Should cardinality be respected? As in, if I had 5, 6 originally and 5, 5, 6 after, should add be 5? The above works better with Sets, since they don't have duplicates (plus contains() lookups are faster since they are indexed by the data they contain).

Answer 7

Use this method if you want to get intersection of a list of lists

List<Address> resultsIntersectionSet( List<Set<Address>> inputListOfLists )
{
    Set<Address> intersection = new HashSet<>();

    if ( !inputListOfLists.isEmpty() )
        intersection = inputListOfLists.get( 0 );

    for ( Set<Address> filterResultList : inputListOfLists )
    {
        intersection.retainAll( filterResultList );
    }

    return new ArrayList<>( intersection );
}

Answer 8

There is a new library available underscore-java. It can do difference and intersection for lists and arrays. Live example.

Code example:

List<Integer> original = Arrays.asList(12, 16, 17, 19, 101);
List<Integer> selected = Arrays.asList(16, 19, 107, 108, 109);
List<Integer> add = U.difference(selected, U.intersection(original, selected));
List<Integer> remove = U.difference(original, selected);

Answer 9

package LAB8Pack;
import java.util.HashSet; 
import java.util.Iterator;
import java.lang.StringBuilder; 


public class HashSetDemo {

    public static void main(String[] args) {
        HashSet<String> round = new HashSet<String> (); 
        HashSet<String> green = new HashSet<String> (); 


        // Add elements to 'round' and 'green' sets 
        //----------------------------------------------------
        round.add("peas"); 
        green.add("peas");
        round.add("watermelon"); 
        green.add("watermelon");
        round.add("basketball"); 
        green.add("chameleon");
        round.add("chameleon"); 
        green.add("grass");
        round.add("eyes"); 
        green.add("book");

        // Create 'setUnion' and 'setInter'  
        // ---------------------------------------------------
        HashSet<String> setUnion = new HashSet<String>();   

        // Use this to find the intersection
        HashSet<String> SETINTER = new HashSet<String>();   


        HashSet<String> setInter1 = new HashSet<String>(round);
        HashSet<String> setInter2 = new HashSet<String>(green);



        // Add all the elements to one set
        setUnion.addAll(round);
        setUnion.addAll(green);
        SETINTER.addAll(setUnion);



        // Create an intersection
        setInter1.removeAll(green); // Get unique items in round
        setInter2.removeAll(round); // Get unique items in green
        SETINTER.removeAll(setInter2); // Remove items that are unique to green
        SETINTER.removeAll(setInter1); // Remove items that are unique to round
        //----------------------------------------------------


        // DISPLAY RESULTS 
        // ===================================================
        System.out.println("Content of set round"); 
        System.out.println("-----------------------");
        System.out.println(OutputSet(round));

        System.out.println("Content of set green");
        System.out.println("-----------------------");
        System.out.println(OutputSet(green)); 

        System.out.println("Content of set Union");
        System.out.println("-----------------------");
        System.out.println(OutputSet(setUnion));



        System.out.println("Content of set Intersection"); 
        System.out.println("-----------------------");
        System.out.println(OutputSet(SETINTER));
    }




    // METHODS 
    // =======================================================
    static StringBuilder OutputSet (HashSet<String> args) {
        Iterator iterator = args.iterator();
        StringBuilder sB = new StringBuilder (); 

        while (iterator.hasNext()) {
            sB.append(iterator.next() + " \n");
        }
        return sB; 
    }  
}

Answer 10

Here is a function to find intersection of various collections (more than 2) -

public static <T, C extends Collection<T>> C findIntersection(C newCollection,
                                                            Collection<T>... collections) {
  boolean first = true;
  for (Collection<T> collection : collections) {
      if (first) {
          newCollection.addAll(collection);
          first = false;
      } else {
          newCollection.retainAll(collection);
      }
  }
  return newCollection;
}

Usage -

public static void main(String[] args) {
  List<Integer> l1 = List.of(1, 3, 5, 7, 9, 11, 13);
  List<Integer> l2 = List.of(1, 2, 3, 5, 8, 13);
  List<Integer> l3 = List.of(2, 3, 5, 7, 11, 13);
  Set<Integer> intersection = findIntersection(new HashSet<>(), l1, l2, l3);
  System.out.println(intersection);
 }

Answer 11

Using Java 8+ streams:

List<Integer> result = original.stream()
  .distinct()
  .filter(selected::contains)
  .collect(Collectors.toList());