It depends largely on whether you know the maximum size of each list up front.

If you do, use ArrayList; it will certainly be faster.

Otherwise, you'll probably have to profile. While access to the ArrayList is O(1), creating it is not as simple, because of dynamic resizing.

Another point to consider is that the space-time trade-off is not clear cut. Each Java object has quite a bit of overhead. While an ArrayList may waste some space on surplus slots, each slot is only 4 bytes (or 8 on a 64-bit JVM). Each element of a LinkedList is probably about 50 bytes (perhaps 100 in a 64-bit JVM). So you have to have quite a few wasted slots in an ArrayList before a LinkedList actually wins its presumed space advantage. Locality of reference is also a factor, and ArrayList is preferable there too.

In practice, I almost always use ArrayList.

First Thoughts:

• Refactor your code to not need the list.
• Simplify the data down to a scalar data type, then use: int[]
• Or even just use an array of whatever object you have: Object[] - John Gardner
• Initialize the list to the full size: new ArrayList(123);

Of course, as everyone else is mentioning, do performance testing, prove your new solution is an improvement.

Note that iterating through an instance of LinkedList can be O(n^2) if done naively. Specifically:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

This is absolutely horrible in terms of efficiency due to the fact that the list must be traversed up to i twice for each iteration. If you do use LinkedList, be sure to use either an Iterator or Java 5's enhanced for-loop:

for (Object o : list) {
    // ...
}

The above code is O(n), since the list is traversed statefully in-place.

To avoid all of the above hassle, just use ArrayList. It's not always the best choice (particularly for space efficiency), but it's usually a safe bet.

遍历链表是每个元素 O(1)。

每个选项的 Big O 运行时都是相同的。由于更好的内存局部性，ArrayList 可能会更快，但您必须测量它才能确定。选择使代码最清晰的任何内容。

There is a new List implementation called GlueList which is faster than all classic List implementations.

Disclaimer: I am the author of this library

You almost certainly want an ArrayList. Both adding and reading are "amortized constant time" (i.e. O(1)) as specified in the documentation (note that this is true even if the list has to increase it's size - it's designed like that see http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ). If you know roughly the number of objects you will be storing then even the ArrayList size increase is eliminated.

Adding to the end of a linked list is O(1), but the constant multiplier is larger than ArrayList (since you are usually creating a node object every time). Reading is virtually identical to the ArrayList if you are using an iterator.

It's a good rule to always use the simplest structure you can, unless there is a good reason not to. Here there is no such reason.

The exact quote from the documentation for ArrayList is: "The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation."

I suggest benchmarking it. It's one thing reading the API, but until you try it for yourself, it'd academic.

Should be fair easy to test, just make sure you do meaningful operations, or hotspot will out-smart you and optimise it all to a NO-OP :)

I have actually begun to think that any use of data structures with non-deterministic behavior, such as ArrayList or HashMap, should be avoided, so I would say only use ArrayList if you can bound its size; any unbounded list use LinkedList. That is because I mainly code systems with near real time requirements though.

The main problem is that any memory allocation (which could happen randomly with any add operation) could also cause a garbage collection, and any garbage collection can cause you to miss a target. The larger the allocation, the more likely this is to occur, and this is also compounded if you are using CMS collector. CMS is non-compacting, so finding space for a new linked list node is generally going to be easier than finding space for a new 10,000 element array.

The more rigorous your approach to coding, the closer you can come to real time with a stock JVM. But choosing only data structures with deterministic behavior is one of the first steps you would have to take.