CODEWITHSUNDEEP
javalistarraylist
aran
aran

Reputation: 11830

Remove NOT duplicated objects from two lists

Well, I've read a lot about removing duplicated values from lists, but nothing about maintaining those that are in fact duplicated in another list. I'll try to explain my problem:

I have to read some values from a DB and save every entry (integer entry) that matches my searching criterias. This operation is done n times, since it's a loop operation. The returning object must be a List (or ArrayList, or whatever list implementation is the most adequate for my purpose).

To make it clear, some pseudocode:

for (int i=0; i<nElements; i++) {

    tempList = getEntriesFromDb(i);

    if (i==0)
     result=tempList;

    else 
     //this is where I should maintain those entries that are in fact duplicated
     // in both tempList and result
     result = maintainDuplicates(result,tempList);

    }

retun result;

I would like to know some proposals for my problem. The question is, I could do it making a new loop that extracts every single entry from the lists, create a (third!!) temporal list to save them there, etc.. But I am really aware that this will cause a bottleneck in my implementation.

Any help would be appreciated, thanks in advance.

Upvotes: 1

Views: 281

Answers (4)

Sachin Pathade
Sachin Pathade

Reputation: 31

You should use sorted collection like TreeSet or TreeMap so that you will have sorted collection to compare. Then in sorted order, you can iterate through 2 collections as its sorted it will help you to find duplicate elements in 2n time that is o(n) time.

e.g. If you have DB result as 1,3,5,7,9,11,13,15 and tempList as 2 5 8 11 then

You can start iterating DB result and tempList at same time. Start with first element 1-2 So 1 is not present in tempList so 1 is not duplicate and so on. So comparisons and results will be like this.

1-2 Remove 1. Because DB result element less than tempList element, get next DB result ele

3-2 No remove. tempList element less than DB result element, get next tempList element so on

3-5 Remove 3. Because DB result element less than tempList element, get next DB result ele

5-5 Both are same so move to next element in both.

7-8 Because DB result element less than tempList element, get next DB result ele

9-8 No remove. tempList element less than DB result element, get next tempList element so on

9-11 Remove 9. Because DB result element less than tempList element, get next DB result ele

11-11 Both are same so move to next element in both.

So this is how you will get 5,11 as result.

Upvotes: 1

Ankur Lathi
Ankur Lathi

Reputation: 7836

Use this:

result.retainAll(tempList);

Upvotes: 0

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

The key operation here is looking up each element of one list in the other. That can be a slow operation. If the lists can be long, I suggest creating a HashSet workingHash that contains all elements of one list, and then doing a retainAll(workingHash) on the other.

Upvotes: 3

user529543
user529543

Reputation:

You can start iterate list1 elements and the current element need to verify in list2 ( index = list2.indexOf(curElementInList1) if index is > -1 than you add it to the result (the list3).

This is the slowest method, but simplest to understand.

Upvotes: 1

Related Questions