Today I was reviewing the Collection’s chapter for the SCJP (Sun Certified Java Programmer) and for the sake of understanding, I started playing around with ArrayList and LinkedList implementation of the java.lang.List interface. I was curious about the differences (here an interesting post) and I wrote a small piece of code to measure the time needed to perform some basic operations: add(), get(), contains(), remove().
package collection;
import java.util.*;
/**
* Created with IntelliJ IDEA.
* User: lfoppiano
* Date: 14/10/12
* Time: 16:37
* To change this template use File | Settings | File Templates.
*/
public class ListTest {
private static final int NUMBER_OF_ELEMENTS = 1000000;
public static void main(String... args) {
List arrayList = new ArrayList();
System.out.println("Array list benchmark");
BenchmarkList benchmarkList = new BenchmarkList(arrayList, NUMBER_OF_ELEMENTS);
benchmarkList.runAllTests();
List linkedList = new LinkedList();
System.out.println("Linkedlist benchmark");
benchmarkList = new BenchmarkList(linkedList, NUMBER_OF_ELEMENTS);
benchmarkList.runAllTests();
}
}
class BenchmarkList {
private List target;
private Integer numberOfElements;
BenchmarkList(List target) {
this.target = target;
}
BenchmarkList(List target, Integer numberOfElements) {
this(target);
this.numberOfElements = numberOfElements;
}
public void runAddTest() {
long start = System.currentTimeMillis();
for (int x = 0; x < numberOfElements; x++)
target.add("a");
long end = System.currentTimeMillis();
System.out.println("Insert of " + numberOfElements + " elements: " + (end - start) + " ms");
}
public void runRemoveTest() {
long start = System.currentTimeMillis();
target.removeAll(target);
long end = System.currentTimeMillis();
System.out.println("Remove of " + numberOfElements + " elements: " + (end - start) + " ms");
}
public void runAccessTest() {
long start = System.currentTimeMillis();
for (int x = 0; x < numberOfElements; x++)
target.get(x);
long end = System.currentTimeMillis();
System.out.println("Access of " + numberOfElements + " elements: " + (end - start) + " ms");
}
public void runContainsTest() {
long start = System.currentTimeMillis();
target.contains("342332432");
long end = System.currentTimeMillis();
System.out.println("Contains of " + numberOfElements + " elements: " + (end - start) + " ms");
}
public void runAllTests() {
runAddTest();
runContainsTest();
runAccessTest();
runRemoveTest();
}
}
And this is the result with a case of 100, 1000, 10000 and 100000 elements:
Some comments:
- ArrayList are fast to iterate to random access the data (get() an element). adding or removing element are more expensive, because, for the nature of an Array, the elements needs to be reorganized.
- LinkedList are faster to add() and remove() because every element is linked to the following and the previous. The access is double penalized because there is no index as in the ArrayList, but to get to the element it is required to iterate the entire list.
- ArrayList are 90% of the cases good enough, however for heavy duty operations of insertion and removal, LinkedList is a more appropriate choice. I must say that the gain on the insert/remove is counterbalanced by a huge penalty on random access, therefore the usage of LinkedList should be carefully verified, to avoid bad surprises.
- Accessing elements with an Iterator bring benefit only on LinkedList, on the other hand, we are not talking anymore about random access.
