Removing duplicates from one list compared to another list

Question

I have two lists of objects, and I would like to remove instances from one list, which is in another list.

eg. I have the following two lists and assume that each letter represents an object.

ListA List = {A, B, C, D, E, F, G, H, I, J}

ListB = {D, G, K, P, Z}

Now, it’s clear that listB has D and G, which are in listA too, so I want listA to be like that

listA = {A, B, C, E, F, H, I, J}

Can you guys suggest what solution would be for this with O (n) or less than O (n2).

I can iterate over both lists and remove duplicate instances by comparison, but I want to have something more efficient.

Answer 1

If the lists are unsorted and are ArrayLists or other similar implementations of the list with the O (n) method, then you must create a HashSet with listB elements to perform the deletion. If the elements do not fit in the set, then you will get O (n ^ 2) performance.

The easiest way to do what you need:

listA.removeAll(new HashSet(listB)); 

ArrayList.removeAll(Collection) will not put items into a set for you (at least in the JDK versions 1.6 and 1.7, which I checked), so you need to create a HashSet yourself in the above.

The removeAll method will copy the elements that you want to keep at the beginning of the list when it traverses it, avoiding compaction of the array each time it is deleted, so using it against a past in a HashSet, as shown, is quite optimal and is O (n).

Answer 2

You can add both list items to Set.

To remove items from one list from another, try listA.removeAll(listB);

Answer 3

Like ssantos, you can use Set.

Alternatively, if the lists are sorted, you can iterate over them one by one. Iterate through ListA until you reach an element that is larger than the current ListB, then iterate through ListB until you reach an element that is larger than the current ListA, etc.

Answer 4

The following is some pseudo-C for solving in expected time O(n) .

 lenA = length pf listA lenB = length of listB shortList = (lenA <= lenB) ? A : B longList = (shortList == A) ? B : A create hash table hashTab with elements of shortList for each element e in longList: is e present in hashTab: remove e from longList now, longList contains the merged duplicate-free elements