Core JavaTM Technologies Tech Tips offers useful information using core Java technologies and APIs, such as those in JavaTM 2 Platform, Standard Edition (J2SETM).

Using ArrayList and LinkedList

ArrayList and LinkedList are two Collections classes used for storing lists of object references. This tip compares the performance of ArrayList and LinkedList, and offers some suggestions about which of these classes is the right choice in a given situation.

The first key point is that an ArrayList is backed by a primitive Object array. Because of that, an ArrayList is much faster than a LinkedList for random access.

There is code for a program that does a binary search on all the elements in an ArrayList or a LinkedList. ArrayList is about 150 times faster than LinkedList in this situation. The binary search algorithm inherently uses random access, and LinkedList does not support fast random access.

However, there are many cases where LinkedList does better. Also note that there are many situations where an algorithm can be implemented efficiently for LinkedList.

Using Zero-Length Arrays

Suppose that you are writing a Java application that involves some sort of data filtering, where the result of the filtering process is a new array of cleaned-up data. This tech tip explores the implementation of this kind of filtering method.

The filterData method does two scans of the input array. The first scan counts the number of valid data values. Then the method allocates a new array of the appropriate size, and copies the good values to it. If there are no good values, the method returns a null value for the array reference. The problem with this program is that the second call of filterData returns a null value, and the program fails to take this possibility into account.

A better approach in this example would be to comment out the block of code that tests for the possibility of no valid data values. When there is no valid data, the code will fall through to the next line, where a zero-length array is allocated.

The representation of Java arrays includes the length of the array, and it's therefore possible to tell if an array has zero length. In general, it's best not to return null from a method that returns an array type. Always returning an array, even if the array has zero length, greatly improves the generality of algorithms. If you anticipate that your methods will often return zero-length arrays, you might be concerned about the performance implications of allocating many such arrays. In this case, you can allocate a single array, and always return the same one. This array is immutable (it can't be changed), and can be shared throughout your application.

For additional technical details as well as code, please see:

http://developer.java.sun.com/developer/JDCTechTips/2002/tt0910.html [...read more...]

		fullsource
Print Email Current Profile Archive Blog Generate newsletter