So I wanted to test ArrayList vs LinkedList remove()
method times just for fun.
I wrote code below to do it - everything is pretty self-explanatory: deleteEachNth
runs through my list and deletes every nth element it sees.
I was expecting to see LinkedList winning by a huge margin, as its remove times are constant-time operations, but my code produces opposite results: for 10000 elements ArrayList is twice as fast.
Naturally, I thought I'd written something wrong, perhaps used a get()
, which would slow LinkedList down somewhere, but it isn't the case.
Whats wrong here?
EDIT: When replacing System.currentTimeInMillis()
with System.nanoTime()
LinkedList still performs worse for my code.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.IntStream;
public class Test{
List<String> myList;
Test(List<String> someList){
myList = someList;
}
void eliminateEachNth(int n){
for (int i = 1; i < myList.size(); i++) {
if(i%(n-1)==0){
myList.remove(i);
}
}
}
public static void main(String[] args){
List<String> someList = new ArrayList<>();
IntStream.range(1, 10000).forEach(i->someList.add(Integer.toString(i)));
Test testArray = new Test(someList);
long cur = System.currentTimeMillis();
testArray.eliminateEachNth(3);
System.out.println("array list took " + (System.currentTimeMillis() - cur) + "millis");
System.out.println(someList);
List<String> anotherList = new LinkedList<>();
IntStream.range(1, 10000).forEach(i->anotherList.add(Integer.toString(i)));
Test testLinked = new Test(anotherList);
cur = System.currentTimeMillis();
testLinked.eliminateEachNth(3);
System.out.println("linked list took " + (System.currentTimeMillis() - cur) + "millis");
System.out.println(anotherList);
}
}