Carlos Luis - 5 months ago 20
Java Question

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

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{
while(it1.hasNext()){
a = it1.next();
}
break;
}
}
else if(a.compareTo(b)<0){
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?

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