The Performance of Java's Lists

Additionally, the ArrayList generates only a few extra objects for garbage collection, i.e. the internal array object which holds the elements, and one extra internal array object each time the ArrayList capacity is exhausted and the ArrayList needs to be grown. The LinkedList generates one node object for every insertion, irrespective of any deletions that might take place. Consequently, LinkedLists can make considerably more work for the garbage collector. Taking these added factors into account, my inclination would be to use an ArrayList rather than a LinkedList for any small to medium sized collection.

Moving into the range of larger sized collections, we can see from table 2 that we begin to get a severe performance penalty when we encounter large insertion overheads. The worst case for LinkedList is, as we predicted from the analysis of the implementation, inserting to the middle of the collection. We can also see that this has worse performance than the ArrayList worst case of insertion to the start of the collection. Insertion to the middle of the ArrayList has significantly better performance than those two worst cases.

Overall, ArrayList again gives better performance for most cases, including index insertion to random locations. If you always need to insert toward the beginning of the collection, LinkedList provides a better performance but you can achieve even better performance using a reversed ArrayList, i.e. either with a dedicated implementation or by flipping indexes using a [size-index] mapping.

Table 3, showing the results for very large collections, indicates conclusions very similar to those of table 2. However table 3 serves to emphasize that very large collections need particularly close matches between data, collection types, and data manipulation algorithms. Otherwise you can end up with performance that is essentially unusable. For optimum performance you should build a dedicated collection class implementation specific to the problem. For very large collections, it is often necessary to do this just in order to obtain adequate performance.

Querying performance

Querying is most efficiently achieved by implementing the query inside the class (see the two articles about optimizing queries, listed in the resources). The time needed to iterate over all the elements is the limiting factor for queries on these lists. A query implemented in the ArrayList/Vector classes will iterate over the array elements. The following example counts the number of null elements:

int count = 0;

for (int i = 0; i < size; i++)

  if(elementData[i] == null)

    count++;

A query implemented in the LinkedList class will traverse all the nodes. The following example counts the number of null elements:

node = header.next;

count = 0;

for (int i = 0; i < repeat; i++, node = node.next)

  if (node.element == null)

    count++;

Table 4 shows the ArrayList providing significantly superior performance to that of the LinkedList, once again indicating that ArrayList is the recommended class to use. Table 5 shows the time taken to iterate over all the elements using a ListIterator object obtained from the List.listIterator(int) method. These iterators would be necessary if the query could not be implemented in the List class. Once again, ArrayList shows superior performance, though not as dramatically as with table 4. Note that the absolute times in table 5 are about ten times longer than the absolute times in table 4, i.e. ArrayList internal traversal is about ten times faster than ArrayList iteration using a ListIterator.

Conclusions

The measurements and the other factors we've considered clearly indicate that ArrayLists and Vectors usually provides better performance than LinkedLists and synchronized wrapped LinkedLists. Even in cases where you might have thought that the LinkedList would provide better performance, you may be able to coax superior performance from ArrayList by altering how elements are added, for example by reversing the collection order.

There are situations where LinkedLists will provide better performance; with, for example, very large collections where many elements need to be added to both the beginning and end of the collection. But in general, I recommend using ArrayList/Vector as the default and using LinkedList only where there is an identified performance problem in which a LinkedList improves the performance.

Further resources

• The source code Test.java
• The Java Performance Tuning website
• Java Performance Tuning, O'Reilly
• Optimizing Collection queries
• Optimizing Map queries

Jack Shirazi is the author of Java Performance Tuning. He was an early adopter of Java, and for the last few years has consulted mainly for the financial sector, focusing on Java performance.

Return to ONJava.com.