Игорь Рыбаков Игорь Рыбаков - 5 months ago 5x
Java Question

Best way to remove one arraylist elements from another arraylist

What is the best performance method in Java (7,8) to eliminate integer elements of one arraylist from another. All the elements are unique in the first and second lists.

At the moment i know the API method removeall and use it this way:


The problem appear when i operate with arraylists with more then 10000 elements. For example when I remove 65000 elements, the delay appears to be about 2 seconds. But i need to opperate with even more large lists with more then 1000000 elements.

What is the strategy for this issue?

Maybe something with new Stream API should solve it?


Well, since removeAll checks for each element of tempList whether it appears in tempList2, the running time is proportional to the size of the first list multiplied by the size of the second list, which means O(N^2) unless one of the two lists is very small and can be considered as "constant size".

If, on the other hand, you pre-sort the lists, and then iterate over both lists with a single iteration (similar to the merge step in merge sort), the sorting will take O(NlogN) and the iteration O(N), giving you a total running time of O(NlogN). Here N is the size of the larger of the two lists.

If you can replace the lists by a sorted structure (perhaps a TreeSet, since you said the elements are unique), you can implement removeAll in linear time, since you won't have to do any sorting.

I haven't tested it, but something like this can work (assuming both tempList and tempList2 are sorted) :

Iterator<Integer> iter1 = tempList.iterator();
Iterator<Integer> iter2 = tempList2.iterator();
Integer current = null;
Integer current2 = null;
boolean advance = true;
while (iter1.hasNext() && iter2.hasNext()) {
    if (advance) {
        current = iter1.next();
        advance = false;
    if (current2 == null || current > current2) {
        current2 = iter2.next();
    if (current <= current2) {
        advance = true;
        if (current == current2)