0

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);

    }
}
sæe
  • 13
  • 5
  • 2
    Step 0: Read [this question and its answers](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). Step 1: don't use `System.currentTimeMillis()`, but `System.nanoTime()`. Step 2: when writing microbenchmarks, use the [Java Microbenchmark Harness](http://openjdk.java.net/projects/code-tools/jmh/). – Turing85 Apr 22 '18 at 19:04
  • Interesting. I ran similar code and found the `ArrayList` removal ran ten-fold faster. I suspect the reason is that each call to `List::remove` is passing an index, and indexing into a `LinkedList` is sequential whereas an `ArrayList` can skip directly to the indexed element. Per the `LinkedList` doc: *Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.* A linked-list is optimal when inserting/deleting elements while already traversed, whereas arrays are optimal when jumping around the elements. – Basil Bourque Apr 23 '18 at 07:36

0 Answers0