ArrayList algorithm complexity, performance and gotchas

This piece of advice is about the Java ArrayList and LinkedList. It is not a insight about a general not specified List algorithm.

ArrayList is a random access data store.

LinkedList is sequential access data store.

There are these very important performance issues to know:

  • Remove: ArrayList remove(E ) is painful slow. Please consider LinkedList if this operation is used often in your application. Also the ArrayList positional remove(index) is painful bad. These operations require constant-time in a LinkedList and linear-time in an ArrayList. (*)
  • Use ArrayList constructor that take a size argument. You can measure by your self the defference when using large lists.
  • List Interface : Iterating over the elements in a list is preferable to indexing through it if the caller does not know the implementation.
  • Remember that you have the method addAll() for bulk operations.
  • Add positional add(index) is painful O(n) on ArrayList and O(1) in LinkedList (*)
  • Set positional set(index) is painful O(n) on LinkedList and O(1) in ArrayList¬†¬† (*)

(*) Also the outline of the Collections Framework states that LinkedList is better than ArrayList for accessing in the middle of the list.

Also:

Do not do this:

 int a1[] = { -23, 12, 21 };
 
for (int v : a1)
           myarraylist.add(new Integer(v));

prefer this instead:

myarrayList.addAll(Arrays.asList(23,12,21)

Also

Arrays.asList

for translating arrays to strings is obsolete. Use this instead:

System.out.println(Arrays.toString(myArray));

Leave a Reply

Your email address will not be published. Required fields are marked *