Removing elements from LinkedList with a for loop is significantly slowed than removing with iterator

I have a linked list of integer that contains elements from 0 to 100000.
I tried removing elements from far end of the list using iterator and traditional for loop. What I found is that the iterator is way faster than a for loop roughly 500 times faster. I assume the reason why for loop is significantly slower is because of the remove(item) method but not sure. What makes the iterator remove quicker?

Here is the code:

public static void iteratorRemove() {

	Iterator<Integer> iterator = list.iterator();
	while (iterator.hasNext()) {
	    int item = iterator.next();
	    if (item == 99999) {
	        iterator.remove();
	    }
	}
}

public static void linkedListRemove() {

	for(int i=0; i<list.size(); i++) {
		
		if(list.get(i)==99997) {
			list.remove(i);
		}
	}

}

The Iterator.remove() method is more efficient than LinkedList.remove(int index) or LinkedList.remove(Object o) methods because it operates directly on the node that the iterator is currently on. It doesn't need to traverse the LinkedList from the beginning to find the item to remove.

When you call iterator.remove(), the iterator already knows the location of the item to remove, because it's the last item that was returned by iterator.next(). Therefore, it can remove the item in constant time O(1), i.e., the time it takes doesn't depend on the size of the list.

On the other hand, LinkedList.remove(int index) or LinkedList.remove(Object o) methods have to first find the item to remove. In the worst case, they might need to traverse the entire list to find the item. LinkedLists don't support efficient random access to elements, so finding an item is an O(n) operation, where n is the size of the list. Once the item has been found, it can be removed in constant time, but the time-consuming part is finding the item.

This is why your code using iterator.remove() is much faster than the one using LinkedList.remove(). The former doesn't need to repeatedly traverse the list to find the items to remove.

Also, a minor point about your code using LinkedList.remove(): every time you remove an item from the list, the indexes of all the items that come after the removed item change. Therefore, the for loop might skip some items or run into a IndexOutOfBoundsException because i becomes greater than the current size of the list. A common pattern when removing items from a list during iteration is to iterate from the end to the beginning. However, in the case of LinkedList, since it doesn't support efficient random access to elements, it's best to use an Iterator to avoid having to traverse the list for each removal.

public static void linkedListRemove() {
    ListIterator<Integer> listIterator = list.listIterator(list.size());
    while (listIterator.hasPrevious()) {
        int item = listIterator.previous();
        if(item == 99997) {
            listIterator.remove();
            // break the loop if we have found and removed the item
            break;
        }
    }
}

list.get(i) has to walk from 0 to i in a LinkedList, which makes that approach take O(N^2). That is the distinction of LinkedList vs ArrayList (random access). With an Iterator you are just accessing each element once.