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
• Productivity

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:

• http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist
• http://stackoverflow.com/questions/1713144/java-lists-does-linkedlist-really-perform-so-poorly-vs-arraylist-and-treelist

Answer 1

Linked list is faster for adding/removing inside elements (ie not head or tail)

Arraylist is faster for iterating

Answer 2

It's a classic tradeoff between insert vs. retrieve optimization. Common choice for the task as you describe it is the ArrayList.

Answer 3

ArrayList is fine for your (and most other) purposes. It has a very small memory overhead and has good amortized performance for most operations. The cases where it is not ideal are relatively rare:

• The list ist very large
• You frequently need to do one of these operations:
  • Add/remove items during iteration
  • Remove items from the beginning of the list

Answer 4

If you're only adding at the end of the list, ArrayList should be ok. From the documentation of ArrayList:

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost

and ArrayList should also use less memory than a linked list as you don't need to use space for the links.

Answer 5

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: http://stackoverflow.com/questions/1713144/java-lists-does-linkedlist-really-perform-so-poorly-vs-arraylist-and-treelist

Answer 6

It depends on your usage profile.

Do you add to the end of the list? Both are fine for this. Do you add to the start of the list? LinkedList is better for this. Do you require random access (will you ever call get(n) on it)? ArrayList is better for this.

Both are good at iterating, both Iterator implementations are O(1) for next().

If in doubt, test your own app with each implementation and make your own choice.

Answer 7

I know I'm late but, maybe, this page can help you, not only now, but in the future...

Answer 8

I guess this would be a good start: http://www.odi.ch/prog/design/newbies.php#26 It shows differences in performance of different implementations of List.

Answer 9

Given your criteria, you should be using the LinkedList.

LinkedList implements the Deque interface which means that it can add to the start or end of the list in constant time (1). In addition, both the ArrayList and LinkedList will iterate in (N) time.

You should NOT use the ArrayList simply because the cost of adding an element when the list is full. In this case, adding the element would be (N) because of the new array being created and copying all elements from one array to the other.

Also, the ArrayList will take up more memory because the size of your backing array might not be completely filled.