Compare the two ArrayLists in java which contains same objects

Question

Hi,

I have a two ArrayList given below as 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

Answer 1

I would suggest using a HashMap for the second list.

Answer 2

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++;
  }
}

Answer 3

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

Answer 4

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;
         }
      }
   }
}

Answer 5

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.