CODEWITHSUNDEEP
javaperformancememory-managementcollections
Andriy Sholokh
Andriy Sholokh

Reputation: 872

Which implementation of List to use?

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:

Operations which I need are:

Any thoughts?

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

Upvotes: 13

Views: 18921

Answers (8)

javaman
javaman

Reputation: 11

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.

Upvotes: 0

SoulWanderer
SoulWanderer

Reputation: 305

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

Upvotes: 1

whaley
whaley

Reputation: 16265

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?

Upvotes: 12

Qwerky
Qwerky

Reputation: 18445

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.

Upvotes: 0

Andre Holzner
Andre Holzner

Reputation: 18695

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.

Upvotes: 0

Michael Borgwardt
Michael Borgwardt

Reputation: 346377

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

Upvotes: 0

GregC
GregC

Reputation: 8007

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

Upvotes: 0

Maxime ARNSTAMM
Maxime ARNSTAMM

Reputation: 5314

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

Arraylist is faster for iterating

Upvotes: 0

Related Questions