As Milkmaid mentioned this is not how you should do benchmarking, but I believe that the results you're getting are still valid.
Let's look "under the hood" and see both implementations:
ArrayList.removeAll calls batchRemove:
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
As you can see, ArrayList first "defragments" the underlying array by overriding the elements that need to be removed with the elements that come afterwards (complement is passed as false so only objects that are not null are copied):
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
The following if (r != size) handles the case that an exception was thrown from c.contains and it uses the "magic function" System.arraycopy to copy the rest of the elements from the current index till the end - this part runs by native code and should be considerably fast, which is why we can ignore it.
And in the last if: if (w != size) {...} it simply assigns nulls to the rest of the list so that objects that are eligible will be able to be collected by the GC.
The total number of operations is O(n) and each operation uses direct access to the array.
Now let's have a look at the implementation of LinkedList which is fairly shorter:
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove(); // <-- calls the iterator remove method
modified = true;
}
}
return modified;
}
As you can see, the implementation uses the iterator in order to remove the elements by calling: it.remove();
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet); // <-- this is what actually runs
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
Which in turn calls:
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset); // <-- here
this.modCount = l.modCount;
size--;
return result;
}
Which calls:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index)); // <-- here
}
which calls:
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
To sum up
Even though theoretically the remove operation in a LinkedList should be O(1) while ArrayList implementation should take O(n), when dealing with batch-removes ArrayList's implementation is more concise, doing everything in one pass by moving objects to override the ones we remove (kind of defragmentation) while LinkedList' implementation is recursively calling 5 different methods (each of which runs its own safety checks...) for each element it removes, and this ends up with the big overhead that you experienced.
