LinkedList vs. ArrayList
A few years ago, I was explaining to my team why we should be using LinkedList and not ArrayList. I told them that while Arrays were better for random access, nearly everything we did, which was put things in a list and then process them sequentially, would be better with LinkedList. Their eyes glazed over.
So I ran a test to demonstrate the difference, and was I ever surprised at the results. After a recent discussion on performance, I re-created my test to run against Java 8 to see if there was a change. There wasn’t.
So the point of the test was to show how much better LinkedList would perform when adding to a list, growing it, and then randomly accessing it. I created a test that would place 100,000 integers into a list, then walk the list 10, 000 times summing the numbers in it. I wrote two spock tests, one for ArrayList and one for LinkedList.
Because it takes a little while to “warm up” the JVM, I wrote another test called throwaway to run first so that it allocates memory and such and makes the later tests more consistent. Here is the spock test that I wrote:
package pizzainthecloud.pizzaplace.service
import pizzainthecloud.pizzaplace.client.to.PizzaPlaceTo
import pizzainthecloud.pizzaplace.pojo.PizzaPlace
import pizzainthecloud.pizzaplace.pojo.PizzaPlaceSpec
import spock.lang.Specification
import java.time.LocalDateTime
import java.time.temporal.ChronoUnit
class ListPerformanceSpec extends Specification {
def "Throwaway"() {
given: "A Linked List"
List<Integer> list
List<Integer> results = new LinkedList<>()
when: "Adding numbers"
Random random = new Random()
//test each list 100 times
for (int ix = 0; ix < 100; ++ix) {
list = new LinkedList<>()
LocalDateTime start = LocalDateTime.now()
for (int jx = 0; jx < 100000; ++jx) {
list.add(random.nextInt())
}
LocalDateTime end = LocalDateTime.now()
long diff = start.until(end, ChronoUnit.MILLIS)
results.add(diff)
}
then: "Should be equal"
true
}
def "Linked list"() {
given: "A Linked List"
List<Integer> list
List<Integer> results = new LinkedList<>()
when: "Adding numbers"
Random random = new Random()
//test each list 100 times
for (int ix = 0; ix < 100; ++ix) {
list = new LinkedList<>()
LocalDateTime start = LocalDateTime.now()
for (int jx = 0; jx < 100000; ++jx) {
list.add(random.nextInt())
}
long total = 0
for (int jx = 0; jx < 10000; ++jx) {
for (Integer num : list) {
total += num
}
total = 0
}
LocalDateTime end = LocalDateTime.now()
long diff = start.until(end, ChronoUnit.MILLIS)
results.add(diff)
}
then: "Print results"
System.out.println("Linked list:" + results.toString())
true
}
def "Array list"() {
given: "A Linked List"
List<Integer> list
List<Integer> results = new LinkedList<>()
when: "Adding numbers"
Random random = new Random()
//test each list 100 times
for (int ix = 0; ix < 100; ++ix) {
list = new ArrayList<>()
LocalDateTime start = LocalDateTime.now()
for (int jx = 0; jx < 100000; ++jx) {
list.add(random.nextInt())
}
long total = 0
for (int jx = 0; jx < 10000; ++jx) {
for (Integer num : list) {
total += num
}
total = 0
}
LocalDateTime end = LocalDateTime.now()
long diff = start.until(end, ChronoUnit.MILLIS)
results.add(diff)
}
then: "Print results"
System.out.println("Array list:" + results.toString())
true
}
}
LinkedList vs. ArrayList
Now for the results. The ArrayList outperformed LinkedList in this test by an average of 6,945 milliseconds, which is about 28% better than LinkedList. How can this be?
It used to annoy me that all of the documentation shows ArrayList, even when LinkedList should be better. The only reason that I can think of is that the java team spent a lot of time optimizing ArrayList and no time optimizing LinkedList.
So, if LinkedList is so much worse for the things that LinkedList should be strongest, why is there a LinkedList in the library?
Who knows? But use ArrayList.