Array or List in Java. Which is faster?

Solution 1:

I suggest that you use a profiler to test which is faster.

My personal opinion is that you should use Lists.

I work on a large codebase and a previous group of developers used arrays everywhere. It made the code very inflexible. After changing large chunks of it to Lists we noticed no difference in speed.

Solution 2:

The Java way is that you should consider what data abstraction most suits your needs. Remember that in Java a List is an abstract, not a concrete data type. You should declare the strings as a List, and then initialize it using the ArrayList implementation.

List<String> strings = new ArrayList<String>();

This separation of Abstract Data Type and specific implementation is one the key aspects of object oriented programming.

An ArrayList implements the List Abstract Data Type using an array as its underlying implementation. Access speed is virtually identical to an array, with the additional advantages of being able to add and subtract elements to a List (although this is an O(n) operation with an ArrayList) and that if you decide to change the underlying implementation later on you can. For example, if you realize you need synchronized access, you can change the implementation to a Vector without rewriting all your code.

In fact, the ArrayList was specifically designed to replace the low-level array construct in most contexts. If Java was being designed today, it's entirely possible that arrays would have been left out altogether in favor of the ArrayList construct.

Since arrays keep all the data in a contiguous chunk of memory (unlike Lists), would the use of an array to store thousands of strings cause problems ?

In Java, all collections store only references to objects, not the objects themselves. Both arrays and ArrayList will store a few thousand references in a contiguous array, so they are essentially identical. You can consider that a contiguous block of a few thousand 32-bit references will always be readily available on modern hardware. This does not guarantee that you will not run out of memory altogether, of course, just that the contiguous block of memory requirement is not difficult to fufil.

Solution 3:

Although the answers proposing to use ArrayList do make sense in most scenario, the actual question of relative performance has not really been answered.

There are a few things you can do with an array:

create it
set an item
get an item
clone/copy it

General conclusion

Although get and set operations are somewhat slower on an ArrayList (resp. 1 and 3 nanosecond per call on my machine), there is very little overhead of using an ArrayList vs. an array for any non-intensive use. There are however a few things to keep in mind:

resizing operations on a list (when calling list.add(...)) are costly and one should try to set the initial capacity at an adequate level when possible (note that the same issue arises when using an array)
when dealing with primitives, arrays can be significantly faster as they will allow one to avoid many boxing/unboxing conversions
an application that only gets/sets values in an ArrayList (not very common!) could see a performance gain of more than 25% by switching to an array

Detailed results

Here are the results I measured for those three operations using the jmh benchmarking library (times in nanoseconds) with JDK 7 on a standard x86 desktop machine. Note that ArrayList are never resized in the tests to make sure results are comparable. Benchmark code available here.

Array/ArrayList Creation

I ran 4 tests, executing the following statements:

createArray1: Integer[] array = new Integer[1];
createList1: List<Integer> list = new ArrayList<> (1);
createArray10000: Integer[] array = new Integer[10000];
createList10000: List<Integer> list = new ArrayList<> (10000);

Results (in nanoseconds per call, 95% confidence):

a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]

Conclusion: no noticeable difference.

get operations

I ran 2 tests, executing the following statements:

getList: return list.get(0);
getArray: return array[0];

Results (in nanoseconds per call, 95% confidence):

a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
a.p.g.a.ArrayVsList.getList    [3.841, 3.874]

Conclusion: getting from an array is about 25% faster than getting from an ArrayList, although the difference is only on the order of one nanosecond.

set operations

I ran 2 tests, executing the following statements:

setList: list.set(0, value);
setArray: array[0] = value;

Results (in nanoseconds per call):

a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
a.p.g.a.ArrayVsList.setList    [6.783, 6.877]

Conclusion: set operations on arrays are about 40% faster than on lists, but, as for get, each set operation takes a few nanoseconds - so for the difference to reach 1 second, one would need to set items in the list/array hundreds of millions of times!

clone/copy

ArrayList's copy constructor delegates to Arrays.copyOf so performance is identical to array copy (copying an array via clone, Arrays.copyOf or System.arrayCopy makes no material difference performance-wise).