Are ArrayList really slower than LinkedList?

[Barkat Mardhani]

Hello Kathy and Berts,
Quote from your book:

LinkedList A LinkedList List is ordered by index position, like ArrayList, except
that the elements are doubly-linked to one another. This linkage gives you new methods
(beyond what you get from the List interface) for adding and removing from the
beginning or end, which makes it an easy choice for implementing a stack or queue.
Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it�s a
good choice when you need fast insertion and deletion.

I am not finding that with following code. Times are noted in the comments.

import java.util.*;
class Test {
static boolean good_args = false;
static int elements ;
static Object[] a ;

public static void main(String[] args) {
if ( args.length < 2 ) feedBack(0);
else if (!( args[0].equals("List") | 
                        args[0].equals("Set" ) | 
args[0].equals("Map" ))) feedBack(1);
else try { elements  = Integer.parseInt(args[1]) ; 
good_args = true          ;  
     } catch(NumberFormatException nfe) { feedBack(3);  }

assert (good_args) ;
if (!good_args) return;

a = new Object[elements];
for (int i=0 ; i<elements ; i++) 
a[i]= new Integer(i);

if (args[0].equals("List")) {
// ArrayList  for insertion at the end ** 60 ms **
System.out.println("ArrayList for insertion at the end      : " + 
measure(new ArrayList(Arrays.asList(a) ), 0));
// LinkedList for insertion at the end ** 280 ms **
System.out.println("LinkedList for insertion at the end     : " + 
measure(new LinkedList(Arrays.asList(a)), 0));
// ArrayList  for insertion at an index ** 28180 ms **
System.out.println("ArrayList for insertion at an index     : " + 
measure(new ArrayList(Arrays.asList(a) ), 1));
// LinkedList for insertion at an index ** 70800 ms **
System.out.println("LinkedList for insertion at an index    : " + 
measure(new LinkedList(Arrays.asList(a)), 1));
// ArrayList  for remove at an index ** 6480 **
System.out.println("ArrayList for remove from an index      : " + 
measure(new ArrayList(Arrays.asList(a) ), 2));
// LinkedList for remove at an index ** 19500 ms **
System.out.println("LinkedList for remove from an index     : " + 
measure(new LinkedList(Arrays.asList(a)), 2));
// ArrayList  for getting object at an index ** 0 ms ** 
System.out.println("ArrayList for getting at an index       : " + 
measure(new ArrayList(Arrays.asList(a) ), 3));
// LinkedList for getting object at an index ** 36200 ms **
System.out.println("LinkedList for getting object at an index: " + 
measure(new LinkedList(Arrays.asList(a)), 3));
}
}
static void feedBack(int i) {
System.out.println(i);
System.out.println("Please provide appropriate arguments.");
System.out.println("java Test [ List | Set | Map ] 2000");
}

static double measure(List l, int operation) {
double start_time = System.currentTimeMillis();
// System.out.println(l);
for (int i=0 ; i<elements ; i++ ) {
switch (operation) {
case 0 : l.add   (          a[i]               ); 
   break                                  ; // add at the end
case 1 : l.add   (          i,a[i]             ); 
   break ; // add at an index
case 2 : l.remove((int)(Math.random()*l.size())); 
   break ; // remove at an index
case 3 : l.get   (                i            ); 
   break                    ; // get from an index
}
}
// System.out.println(l);
double end_time = System.currentTimeMillis();
return (end_time - start_time);
}
}

[Jim Yingst]

I'm going to move this to the Performance forum since that's what it's about. Hopefully K&B will follow...

[Jim Yingst]

For inserts and deletes: ArrayList and LinkedList are fairly comparable at the end of the List. (I think ArrayList comes out ahead, but it's generally not a big difference.) If you try insert or delete at the beginning of the List, LinkedList will be much better. The performance of ArrayList gets worse the farther you are from the end when you insert or delete; the performance of LinkedList gets worse the farther you are from the beginning or the end. So neither one is so great when you're in the middle. However, if you are traversing the list with a ListIterator, and you've already got the ListIterator at the position you need, then using add() or remove() on the ListIterator is very vast for a LinkedList, and poor for ArrayList. So if you want to do something like this:

for (ListIterator it = list.listIterator(); it.hasNext(); ) {
    Object obj = it.next();
    if (isUndesireable(obj))
        it.remove();
}

Then LinkedList will definitely do better. LinkedList is lousy at random access, but at the beginning or end, or through an iterator already in position, it's fast. ArrayList is great at random access, but lousy at inserts/deletes away from the end. For many applications, you will observe a combination of these effects, and it's useful to just try both types of List to see which works better.

[Barkat Mardhani]

Thanks Jim. I was trying to point out that statement K&B was a blanket statement. It needed the details you pointed out.
Thnks
Barkat