ArrayList vs. LinkedList

Today a colleague of mine raised the question of why use a ArrayList? and he that personally likes the LinkedList structure... obviously depending on situation.

We then posed the question,
How often do developers actually think why they use a certain collection... the answer is probably not enough :)

So anyways to brush up again I went digging:

From the Sun Java Tutorial:

There are two general-purpose List implementations — ArrayList and LinkedList. Most of the time, you'll probably use ArrayList, which offers constant-time positional access and is just plain fast. It does not have to allocate a node object for each element in the List, and it can take advantage of System.arraycopy when it has to move multiple elements at the same time. Think of ArrayList as Vector without the synchronization overhead.
If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList. Furthermore, the constant factor for LinkedList is much worse. If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster.


So lets test that:

package bob.blog;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * The Class ArrayListVsLinkedList.
 */
public class ArrayListVsLinkedList {

 private static List< String > list;
 private static String bob = new String("bob");

 /**
  * The main method.
  * 
  * @param args
  *            the arguments
  */
 public static void main(String[] args) {
  long start = 0;
  long end = 0;
  final int iter = 2000000;
  // ArrayList
  start = System.currentTimeMillis();

  list = new ArrayList< String >();
  for (int i = 0; i < iter; i++) {
   list.add(bob);
  }
  end = System.currentTimeMillis();
  System.out.println("ArrayList: " + (end - start) + " ms");

  // LinkedList
  start = System.currentTimeMillis();

  list = new LinkedList< String >();
  for (int i = 0; i < iter; i++) {
   list.add(bob);
  }
  end = System.currentTimeMillis();
  System.out.println("LinkedList: " + (end - start) + " ms");
 }

}

The output for that on my machine:
ArrayList: 138 ms
LinkedList: 481 ms

So that is +-3.5 times faster...

I still need to come up with a nice way to compare memory size, and maybe some other operations to compare and test, but this is start.