Which implementation of List to use?

Question

In my program I often use collections to store lists of objects. Currently I use ArrayList to store objects. My question is: is this a best choice? May be its better to use LinkedList? Or something else?

Criteria to consider are:

• Memory usage
• Performance

Operations which I need are:

• Add element to collection
• Iterate through the elements

Any thoughts?

Update: my choice is : ArrayList :) Basing on this discussion as well as the following ones:

• When to use LinkedList over ArrayList?
• List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Solution

I always default to ArrayList, and would in your case as well, except when

• I need thread safety (in which case I start looking at List implementations in java.util.concurrent)
• I know I'm going to be doing lots of insertion and manipulation to the List or profiling reveals my usage of an ArrayList to be a problem (very rare)

As to what to pick in that second case, this SO.com thread has some useful insights: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Comments

[Dirk]

Hm. Maybe it's faster when iterating, though I don't expect this to be more than marginal. The real benefit should be with accessing elements in random order...

[GregC]

To elaborate on this point: ArrayList's iterator will throw an exception if it detects change while iterating. Also, remove from the beginning a-la queue is better accomplished via linked list for obvious reasons.

[Qwerky]

As I understand both have O(n) iteration.

[GregC]

It's fast to iterate over whole collection, and there's less memory footprint since links in a linked list have to be stored somewhere.

[GregC]

O(n) iteration over N elements. Linked list iterator will not throw if you read here and change way over there...

[Andriy Sholokh]

Thank you for the link to a very interesting discussion!

[hansvb]

@GregC: A LinkedList's iterator does not throw exceptions when there are concurrent modifications? If so, why is that good?

[whaley]

@Thilo - I never said it was. I said I default to ArrayList unless I need thread safety. Just to make it crystal clear, I'll modify my answer to say I go to the List implementations in java.util.concurrent.

[GregC]

It appears I am wrong... Will have to try it.... quoting: "The iterators returned by the this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. "

[GregC]

My thoughts were... If somebody is modifying the list, and they aren't changing anything just to the left or right of the element being iterated over, then there is no problem.

[Michael Borgwardt]

@GregC: that sounds logical at first glance, but race conditions aren't that simple. You misunderstood my point though: the Iterator (and ListIterator) interfaces themselves have add/remove methods that can be used safely to modify the list during iteration (and efficiently so, for LinkedList)

[Andriy Sholokh]

My colleague has just wrote a simple test - adding elements to lists of different size in different places. And here is the result: Have made my own unpretentious test. Here are result: - Simple adding ( List.add(“A”)): ArrayList faster than LinkedList 3-5 time on range of size from 1 to 100 000.

[Andriy Sholokh]

Adding to the head of list (List.add(0, “A”): At size 1 the time is equal; At size 100 LinkedList faster ~2 times; At size 1000 LinkedList faster ~10 times; At size 10000 LiskedList faster ~50 times; At size 50000 LinkedList faster ~80 times

[Andriy Sholokh]

Random adding (List.add(Math.random(list.size()), “A”)): ArrayList faster than LinkedList 2 times on the same range (1 to 100 000)

[Andriy Sholokh]

So, @rrlichwa, unfortunately, I can't agree with you regarding productivity :(

[Andriy Sholokh]

regarding memory usage, I believe ArrayList uses memory more compactly, as it does not save any internal service stuff (like link to the next element in LinkedList)