Performance differences between ArrayList and LinkedList

Ignore this answer for now. The other answers, particularly that of aix, are mostly correct. Over the long term they're the way to bet. And if you have enough data (on one benchmark on one machine, it seemed to be about one million entries) ArrayList and LinkedList do currently work as advertized. However, there are some fine points that apply in the early 21st century.

Modern computer technology seems, by my testing, to give an enormous edge to arrays. Elements of an array can be shifted and copied at insane speeds. As a result arrays and ArrayList will, in most practical situations, outperform LinkedList on inserts and deletes, often dramatically. In other words, ArrayList will beat LinkedList at its own game.

The downside of ArrayList is it tends to hang onto memory space after deletions, where LinkedList gives up space as it gives up entries.

The bigger downside of arrays and ArrayList is they fragment free memory and overwork the garbage collector. As an ArrayList expands, it creates new, bigger arrays, copies the old array to the new one, and frees the old one. Memory fills with big contiguous chunks of free memory that are not big enough for the next allocation. Eventually there's no suitable space for that allocation. Even though 90% of memory is free, no individual piece is big enough to do the job. The GC will work frantically to move things around, but if it takes too long to rearrange the space, it will throw an OutOfMemoryException. If it doesn't give up, it can still slow your program way down.

The worst of it is this problem can be hard to predict. Your program will run fine one time. Then, with a bit less memory available, with no warning, it slows or stops.

LinkedList uses small, dainty bits of memory and GC's love it. It still runs fine when you're using 99% of your available memory.

So in general, use ArrayList for smaller sets of data that are not likely to have most of their contents deleted, or when you have tight control over creation and growth. (For instance, creating one ArrayList that uses 90% of memory and using it without filling it for the duration of the program is fine. Continually creating and freeing ArrayList instances that use 10% of memory will kill you.) Otherwise, go with LinkedList (or a Map of some sort if you need random access). If you have very large collections (say over 100,000 elements), no concerns about the GC, and plan lots of inserts and deletes and no random access, run a few benchmarks to see what's fastest.

ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.

ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.

If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.

Yes, this is what it means. ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array. This involves moving some references around and in the worst case reallocating the entire array. LinkedList just has to manipulate some references.