joustlog

Mate,

LinkedLists are only to be used where you are doing inserts (rather than adds). Inserts into the middle of an arraylist means that you need to copy the rest of the array (move it by one).

With linked lists, it is a constant operation.

Try arrays with millions of elements to see the difference.

Yeah, I understand that part. I'm talking about lists where I only add to the end, and then iterate. I use these when building arrays. I'll update the entry to make that clearer.

The size of the array counts.

In an ArrayList, the default size is 10 elements. Whenever it needs to grow, it doubles (from memory); I'm not sure when it shrinks.

Every time it changes size, it needs to copy all the elements of the underlying array to the new one. This takes time. However, if it doesn't need to grow, then adding an element is nice and fast; it's just an array allocation.

If you have to build the array from scratch, without knowing the length in advance, AND the list is long (in the millions), the linked list will be faster. But, by and large, growing an array list will normally be faster, especially if you can pre-size it.

(BTW, if your major use is to turn the ArrayList into an array, I suggest you check out the toArray() method on the List interface, rather than iterating)

>If you have to build the array from scratch, without knowing the length in advance, AND the list is long (in the millions), the linked list will be faster. But, by and large, growing an array list will normally be faster, especially if you can pre-size it.

WRONG!!

Even if you build the array from scratch, it is still likely to be faster than using the linked list. First, both arraylists and linked list adds are constant-time; second, array usually considerably less memory without the minimum 12-byte object overhead for each linked list node; third, array entries are localized and thus easier on the cache; linked lists caused the garbage collection to do far more object tracking.

First of all, although a single add operation can take time proportional to the number of elements, overall when you amortize the cost of the add operation over the lifetime of the array, the add operation takes on average constant time. If you have taken a data structures class, you know that a dynamic array is only twice as slow as a preallocated array, because when you finally add n elements, the maximum number of copies you will have made is n.

Jim Gray has a good article where he analyzed the performance of linked lists and arrays; and showed that arraylists were much faster for larger number of elements because of locality.

Also, the default capacity of an arraylist is 16 objects. The ArrayList never shrinks, so you must call TrimToSize to explicit shrink the list.

Wesner: Not quite. From the J2SE javadocs for ArrayList:

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.

Adding to an ArrayList can never be considered constant time, because eventually the underlying array must grow. This is where the "amortized" comes in. You pay a single high cost when the array needs to grow, while the other inserts are low cost O(1). Ultimately, the average cost of adding to an ArrayList, as Sun states, is O(n).

LinkedList, however, is guaranteed to be O(1) for adds and something similarly small for inserts (maybe O(log n)?). The point to keep in mind is that for small lists, LinkedList's O(1) is going to be larger than ArrayList's O(n) because LinkedList has much more object creation overhead. For large lists, however, adding the millionth element to an ArrayList with an array of 999,999 slots is going to be far slower than adding the same millionth element to a LinkedList.

That's not what my benchmarks found, Charles. LinkedList's performance decreased as N increased, possibly due to the fact that it allocates so much more memory than ArrayList does.

There's a fine line between genius and insanity. I have erased this line.

A person never tells you anything until contradicted.

what do you mean?

I can't understand why a person will take a year to write a novel when he can easily buy one for a few dollars.

NUDE PHOTOS

Hello!

My Tests showed, that adding elements to a LinkedList results in better performance compared to ArrayList. (by factor 1.5). This comes clear when looking to to add() operation of both classes:

Addin in LinkedList:
private Entry addBefore(Object o, Entry e) {
Entry newEntry = new Entry(o, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

Adding in ArrayList:

modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = (Object[])ExtendedSystem.resizeArray(newCapacity,
elementData,
0,
size); /*SHIRAZ*/
}
elementData[size++] = o;