Wednesday, May 19, 2010

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.

3 comments:

  1. with this "list.add(0, bob)" line instead of "list.add(bob)", all things get worse ;-)

    ReplyDelete
  2. After a pretty long day I, posted a comment saying.. you shouldn't say (0, bob) but rather (i, bob), but then came to my senses and run the code again... :) I see what you mean... add(0, bob) on ArrayList is really really really slow, and doesn't effect LinkedList at all...

    ReplyDelete
  3. LinkedList can be suitable if your insertion and deletion outnumber the access. In most of cases ArrayList is OK but if you application demands specifics where LinkedList is a better data-structure go for it. I have blogged few more difference between LinkedList and ArrayList in Java , you may find useful.

    ReplyDelete

Popular Posts

Followers