Need help in List

[Chethan C Gowda]

I want to compare List A and List B and list down all the elements which are present only in List A not in List B.
One way i can do this using contains() method of List interface and other by sorting the List B and then apply binary search on each element.
Among these to which one will be faster or there any other logic where this comaprision can be performed efficiently???

[Kelvin Chenhao Lim]

Hi Chethan,

If you maintain both List A and List B in sorted order, there's a simple linear-time algorithm for doing what you want. It's easier to demonstrate it than to explain it in words:

import java.util.*;
 
class Foo {
  /** Returns list of all elements in list1 that are not in list2.
   *  Both list1 and list2 must be non-null and sorted, and their elements must implement Comparable.
   **/
  public static <T extends Comparable<T>> List<T> getListDiff(List<T> list1, List<T> list2) {    
    List<T> diff = new ArrayList<T>();
    
    int list2Size = list2.size();
    int list2Idx = 0;    
    
    for (T item1 : list1) {
      for ( ; list2Idx < list2Size; list2Idx++) {
        T item2 = list2.get(list2Idx);
        int compareResult = item2.compareTo(item1);
        if (compareResult > 0) {
          diff.add(item1);
        }
        if (compareResult >= 0) {
          break;
        }
      }
      if (list2Idx >= list2Size) {
        diff.add(item1);
      }
    }   
    
    return diff;
  }
  
  public static void main(String... args) {
    List<String> list1 = Arrays.asList(new String[] { 
        "canary", "banana", "banana", "fog", "fog", "golf", "apple", "zebra" });
    Collections.sort(list1);
    
    List<String> list2 = Arrays.asList(new String[] { 
        "canary", "canary", "yam", "ant", "dish", "fog" });
    Collections.sort(list2);
 
    // Other code goes here.  
    // Assume that any other code will maintain list1 and list2 in sorted order.
    // ...
    
    List<String> diff = getListDiff(list1, list2);
    
    System.out.println("List1: " + list1);
    System.out.println("List2: " + list2);
    System.out.println("Diff:  " + diff);
  }
}

If your program can guarantee that both lists will always be kept in sorted order, then this algorithm should yield faster asymptotic performance than the algorithms you described. However, if you can't guarantee that, then you'll need to sort both lists before using this algorithm, in which case this may or may not be faster than your algorithms. It also won't work if your list elements aren't Comparable.
[ December 06, 2007: Message edited by: Kelvin Lim ]

[Chethan C Gowda]

Hi Kelvin,
The list which i have is unsorted, as you said i dont think ill get better performance if i sort two lists and then applying comapreTo().
Im iterating one list by comparing its element against other list using contains().
Thanks for your reply