ArrayList vs LinkedList [java]

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.
About these ads

Road to FOSDEM 2010

As most of you already know (if you don’t, never mind, I will forgive you :D), I’m going to give a lightning talk in the Free Java Dev room at FOSDEM about Groovy. The title will be “Groovy: the cool side of java” and basically it will be an hand-on speech. No slide, just code. I will start from a simple Java code and I will rewrite it in Groovy. During the demo/live I will give some basics explanation about how is groovy working and we will see the power and the value that Groovy add at the top of JVM compared with a static language like Java.

Here the code that I wrote:

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class TestJava{
   public static void main(String[] args) {
      new DoStuffs().doIt();
   }
}

class DoStuffs{

   public void doIt(){

   List al = new ArrayList();

   System.out.println("* Initial size of"+al.getClass()+" :  " + al.size() + " with elements "+al);

   al.add("this");
   al.add("is");
   al.add("just");
   al.add("test");

   System.out.println("* Final size of"+al.getClass()+" :  " + al.size() + " with elements "+al);
   System.out.println("* Let's add some stuffs");

   al.add(2,"a");
   al.add(3,"cool");

   System.out.println("* Done "+al);
   System.out.println("");

   System.out.println("- Before ordering"+al);
   Collections.sort(al);
   System.out.println("- After ordering "+al);
   System.out.println("");

   List al2 = al.subList(2,4);

   System.out.println("- Sublisting "+al2);
   System.out.println("");

   if(al.size() > 0){
      for (int i=0; i< al.size(); i++) {
         al.set(i, al.get(i)+" \\o/ ");
      }

      System.out.println("Let's show the element in the reverse order: ");
      for (int i=al.size()-1; i>=0; i--){
         System.out.println("<"+i+"> "+al.get(i));
      }
   }

   if(al != null){
      List sub = new ArrayList();

      for (int i=0; i< al.size(); i++) {
         String el = (String) al.get(i);
         if(el.contains("t")) {
            sub.add(al.get(i));
         }
      }
      System.out.println("- After grep "+ sub);
    }
  }
}

Groovy & Grails eXchange 2009

The Groovy & Grails eXchange, organized by skillsmatter, was the first international conferences about software development I’ve attended in my career. Before I was more concentrated mostly on Linux and the Fedoraproject (FOSDEM, Linux TAG for instance).

The conference was headed in London from December 9th to 10th. The first day was focuses on Groovy and the second on Grails. I went there with Raffaele and Davide, friends and colleague of mine (we work together in Holland). As the conferences last Wednesday and Thursday, we decided to get Friday off and stay in London during the week end to visit the city (I already been there almost one year ago but London is always lovely).

At the conference there were about 150 people, mostly developers (heavy twitter users), in particular freelancers and really small companies from all over the world.

I really found all the speech really interesting. Guillaume Laforge spoke about the features of Groovy 1.7 and above (we even had a brief introduction about what are they considering to include in the 1.8 release) and Graeme Rocher introduced Grails 1.2.0 and the new plug-in development approach.

Based on my work in Holland, I really appreciated the ‘Groovy code kata’  talk from Dierk Koening and the DSL speech from Verkat Subramaniam. I had a really interesting chat with him about DSLs, in particular about what we should consider more important to balance the DSL we designed and are using in our project (I swear, I’ll post about it). I found Verkat really good to make examples in order to help you to understand better complexed concepts (DSL by examples might be a suggestion for next book ;-)).

You can find some photos about the conference itself here and here.

I’m really satisfied by this conference, I met a lot of people and exchange contact with them to keep in touch and, at the end I won Grails in Action book. :-) I also met also three guys from the NLGUG (Netherland Groovy User Group): Erik, Alex and Sebastien. They were really interested to my work with groovy and they invited me to give a speech, next year, to the Groovy User Group. I already accepted because it’s cool to meet new people on topics I like and I’ll get the opportunity to get more integrated into the local groups.

I met also Alberto Brandolini (ZioBrando for most of the people), who is a trainer for skillsmatter and a expert software architect in Italy. Before, he saw only a name and a photo but fortunately I had the opportunity to spoke with him to exchange some ideas and suggestion.

After the conferences we enjoy London for three days. I can say that I love London, and it’s strange because London is chaotic and I’m not use to it, but it has a fashion and a people integration level that is difficult(may be impossible) to find in any other cities (maybe in New York, but I’ve never been there, yet).

Maybe after my project in Holland will be finished, I’ll move there for a while, who knows. But we’ll see.

From London I can say that English people are really crazy, or they drink like sponges. I really would like to know how many drink they drink: I saw people with t-shirt in the middle of the night with around 0° or below, is it possible to survive? I would like to know how can they drink English beers: for me are too warm and they have a strange bitter after-taste.

Anyway London is fantastic and beautiful.  Period.

I took some photos, you can find here.