LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

get(int index) is O(n)

add(E element) is O(1)

add(int index, E element) is O(n)

remove(int index) is O(n)

Iterator.remove() is O(1) <--- main benefit of LinkedList

ListIterator.add(E element) is O(1) <--- main benefit of LinkedList

For ArrayList

get(int index) is O(1) <--- main benefit of ArrayList

add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied

add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)

remove(int index) is O(n - index) (i.e. removing last is O(1))

Iterator.remove() is O(n - index)

ListIterator.add(E element) is O(n - index)

LinkedList

ArrayList

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.7). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

It's worth noting that Vector also implements the List interface and is almost identical to ArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.