Implementing the difference between two sorted Lists of comparable items in java

Question

Implement a method in Java to compute the difference () between L1 and L2. L1 \ L2 = { x | x ∈ L1 and x ∉ L2 }.

This is my implementation so far:

public static <AnyType extends Comparable<? super AnyType>> 
    void difference(List<AnyType> L1, List<AnyType> L2, List<AnyType> Difference){

        if(L1 == null){
            Difference = null;
        }
        else if(L2 == null){
            Difference = L1;
        }
        else if(L1.size()==0 || L2.size()==0){
            Difference = L1;
        }
        else{
            Iterator<AnyType> it1 =L1.listIterator();
            Iterator<AnyType> it2 =L2.listIterator();

            AnyType a = it1.next();
            AnyType b = it2.next();

            while(true){
                if(a.compareTo(b)>0){
                    if(it2.hasNext()){
                        b = it2.next();
                    }
                    else{
                        Difference.add(a);
                        while(it1.hasNext()){
                            a = it1.next();
                            Difference.add(a);
                        }
                        break;
                    }
                }
                else if(a.compareTo(b)<0){
                    Difference.add(a);
                    if(it1.hasNext()){
                        a = it1.next();
                    }
                    else break;
                }
                else {
                    if(it1.hasNext()){
                        a =it1.next();
                    }
                    else break;
                }
            }
        }
        System.out.println("Difference Set: " + Arrays.toString(Difference.toArray()));
    }

This is not the trivial solution which would be to implement two nested for loops and save to the result list the right elements, that solution is O(n^2).
Another possible solution is to search the second list using binary search, that algorithm would be O(n*Log(n))
The solution here implemented, attempts to go through the lists only once and finish in the first pass, this will be O(n) linear.
The algorithm works fine, however it feels like it could use some optimization still, it feels like spaghetti code lol. Any pointers that could help me to optimize this?

Answer 1

EDIT: I thought about this some more and as another alternative approach that is probably more optimal than my initial post you could take advantage of the hashCode method and HashMap implementation as follows:

public static <AnyType extends Comparable<? super AnyType>> 
    void difference(List<AnyType> L1, List<AnyType> L2, List<AnyType> Difference){
        HashMap<AnyType,Boolean> map = new HashMap<AnyType,Boolean>();
        for(AnyType item: L1){
            map.put(item, true);
        }
        for(AnyType item: L2){
            map.put(item, false);
        }

        Difference.clear();
        for(AnyType item: map.keySet()){
            if(map.get(item)){
                Difference.add(item);
            }
        }
    }

END EDIT

Not sure how optimized this is, but another approach would be to take advantage of the collections framework to do the heavy lifting for you if you create a wrapper class to define the equals method. I left in some System.out.println calls in case anyone wants to trace the logic.

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

public class ListDiff {

    public static void main(String[] args) {
        List<String> L1 = new ArrayList<String>();
        L1.add("item1");
        L1.add("item2");
        L1.add("item3");
        L1.add("item3"); //duplicate item intentional for demonstration
        L1.add("item5");

        List<String> L2 = new ArrayList<String>();
        L2.add("item1");
        L2.add("item3");
        L2.add("item4");

        List<String> strDiff = new ArrayList<String>();
        difference(L1,L2,strDiff);
        System.out.println("strDiff is: "+strDiff);

        List<Integer> list3 = new ArrayList<Integer>();
        list3.add(1);
        list3.add(2);
        list3.add(3);
        list3.add(3); //duplicate item intentional for demonstration
        list3.add(5);

        List<Integer> list4 = new ArrayList<Integer>();
        list4.add(1);
        list4.add(3);
        list4.add(4);

        List<Integer> intDiff = new ArrayList<Integer>();
        difference(list3,list4,intDiff);
        System.out.println("intDiff is: "+intDiff);
    }

    public static <AnyType extends Comparable<? super AnyType>> 
    void difference(List<AnyType> L1, List<AnyType> L2, List<AnyType> Difference){
        List<EqualityWrapper<AnyType>> list1 = new ArrayList<EqualityWrapper<AnyType>>();
        for(AnyType item: L1){
            EqualityWrapper<AnyType> wrappedItem = new EqualityWrapper<AnyType>(item);
            list1.add(wrappedItem);
        }

        List<EqualityWrapper<AnyType>> list2 = new ArrayList<EqualityWrapper<AnyType>>();
        for(AnyType item: L2){
            EqualityWrapper<AnyType> wrappedItem = new EqualityWrapper<AnyType>(item);
            list2.add(wrappedItem);
        }
//      System.out.println("list1: "+list1);
        List<EqualityWrapper<AnyType>> diff = new ArrayList<EqualityWrapper<AnyType>>(list1);
//      System.out.println("diff: "+diff);
//      System.out.println("list2: "+list2);
        diff.removeAll(list2);
//      System.out.println("diff: "+diff);

        Difference.clear();
        for(EqualityWrapper<AnyType> item: diff){
            AnyType unwrapped = item.getOrig();
            Difference.add(unwrapped);
        }
    }

    public static class EqualityWrapper<AnyType extends Comparable<? super AnyType>> {
        private AnyType orig;

        public EqualityWrapper(AnyType comparable){
            orig = comparable;
        }

        @Override
        public boolean equals(Object other){
            if(other instanceof EqualityWrapper){
                EqualityWrapper<AnyType> otherEqualityWrapper = (EqualityWrapper<AnyType>)other;

//              System.out.println("Comparing "+orig+" with "+otherEqualityWrapper.getOrig());
                return orig.compareTo(otherEqualityWrapper.getOrig()) == 0;
            }
//          System.out.println("returning false");
            return false;
        }

        public AnyType getOrig(){
            return orig;
        }

        @Override
        public String toString(){
            return orig.toString();
        }
    }
}

OUTPUT:

strDiff is: [item2, item5]

intDiff is: [2, 5]

Answer 2

The first thing I see is that you perform a.compareTo(b) twice for each iteration through the loop. Instead, use compareTo once and store the result for use in both if statements.

Secondly, use for a consistent naming scheme like objA and iterA instead of a and it1. It'll just make it a little easier to follow. For that matter, don't be afraid of longer names. listA than l1 might be a couple extra characters, but it's worth it for readability. (Also, don't forget that you shouldn't start a variable with a capital letter, so L1 is doubly-uncool.)

Finally, comment comment comment. I know this algorithm, so I can follow the code pretty well, but it's far from self-documenting. Comment each if statement and loop to document what the condition is, why you're checking, and what you're doing with the results.