Which list<Object> implementation will be the fastest for one pass write, read, then destroy?

Question

What is the fastest list implementation (in java) in a scenario where the list will be created one element at a time then at a later point be read one element at a time? The reads will be done with an iterator and then the list will then be destroyed.
I know that the Big O notation for get is O(1) and add is O(1) for an ArrayList, while LinkedList is O(n) for get and O(1) for add. Does the iterator behave with the same Big O notation?

Solution 1

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.

Solution 2

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.

Solution 3

Iterating through a linked list is O(1) per element.

The Big O runtime for each option is the same. Probably the ArrayList will be faster because of better memory locality, but you'd have to measure it to know for sure. Pick whatever makes the code clearest.

Solution 4

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.

Solution 5

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

Disclaimer: I am the author of this library

View more solutions