Compare the two ArrayLists in java which contains same objects

I have a two ArrayList given below as 开发者_StackOverflow社区sample. AccVO: compareKey,Amount fields

List 1:

AccVO[001,500]                                                   
AccVO[002,600]                                                   
AccVO[003,800]                                                   

List2:

AccVO[001,100]                                                                   
AccVO[001,100]                                                                   
AccVO[001,300] 
AccVO[003,300]  
AccVO[003,300]  
AccVO[003,200]
AccVO[005,300]  
AccVO[005,300] 

I have sorted the two lists. I have to compare the two lists with the compare key and fetch the records of List2 to insert into database.

Sample Code:

for(AccVO accvo1 : List1){
    for(AccVO accvo2 : List2){
    if(accvo1.getCmpkey().equals(accvo2.getCmpkey())){     
            //insert the recs into the table            
           }        
     }
}

Since my list size will be larger i.e handling millions of records, i need some optimistic logic in looping the records.

Thanking you in advance Prasanna

Because your lists are sorted, you can use an index into both arrays and increment only the smaller key each time:

int i = 0,j = 0;

while (i < List1.size() && j < List2.size()){
  int x = List1.get(i).getCmpKey().CompareTo(List2.get(j).getCmpKey();
  if (x == 0){ 
    //add record
    j++;
  }else if(x < 0){
    i++;
  }else{
    j++;
  }
}

If your equals (and hashCode) implementation are based on getCmpkey() you can use Sets.

set1 = new HashSet(list1)
set2 = new HashSet(list2)
set2.retainAll(set1);
for(AccVO a : set2) //insert

This will have O(1) for individual removes (O(n) for n elements in set1).

I would suggest using a HashMap for the second list.

If the type of the Lists is not specified you should use Iterators to traverse them. This will give you guaranteed O(n) (linear) performance even if you use a List implementation that's not backed by an Array (assuming it you can iterate in O(n) time).

For example, if you happened to be given a LinkedList as your list class, the following implementation is still O(n) but an implementation that used get() to index into the list would be O(n^2). So if you list sizes were each 1 million, this implementation would be 1 million times faster than an indexing implementation.

Iterator i1 = list1.iterator();
Iterator i2 = list2.iterator();
if (i1.hasNext() && i2.hasNext() {
   AccVO v1 = i1.next();
   AccVO v2 = i2.next();
   while (true) {
      int i = v1.getCmpKey().compareTo(v2.getCmpKey());
      if (i == 0) {

         // insert record into DB here

         if (i2.hasNext()) {
            v2 = i2.next()
         } else {
            break;
         } 
      } else if (i < 0) {
         if (i1.hasNext()) {
            v1 = i1.next();
         } else {
            break;   
         }
      } else {
         if (i2.hasNext()) {
            v2 = i2.next();
         } else {
            break;
         }
      }
   }
}

I think I'd do something along the lines of

Set<Integer> goodKeys = new HashSet<Integer>(); 
for (AccVO a : List1) 
    goodKeys.add(a.getCmpkey());
for (AccVO a : List2)
    if (goodKeys.contains(a.getCmpkey()))
        // insert the recs into the table

I could then hang on to the list of good keys, if desired, extract the first chunk into getKeys(List<AccVO> list), extract the remainder into insertRecordsForKeys(Set<Integer> keys), etc. Easier to test, easier to debug, easier to reuse, easier to work with.