Удаление элементов.

for (int i = 0; i <= 10000; ++i) { list.remove(10000 - i); } или так

я решил вариантом 2, но немного по-другому. for (int i = 0; i < 10000; i++) { list.remove(0); } т.е. всё время удалял нулевой элемент, чтобы не вышло за границы списка.

наверное поэтому (взято из Javadoc): Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices). Во втором варианте при удалении первого элемента происходит сдвиг всего массива влево с изменением индекса (или может даже перестроение массива, надо смотреть реализацию). Таким образом когда вы добегаете до 5000-й позиции массив уже меньше 5000 элементов, а счетчик продолжает расти и происходит выход за границы массива. В данном случае лучше 10к раз удалить 0-й элемент. В первом варианте, т.к. вы удаляете всегда последний элемент массива смещение не происходит.

а вы смотрели, что на выходе после этих циклов?