USING ARRAYLIST AND LINKEDLIST
ArrayList and LinkedList are two Collections classes used for storing lists of object references. For example, you could have an ArrayList of Strings, or a LinkedList of Integers. 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, that is, when accessing arbitrary list elements using the get method. Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there's no fast way to access the Nth element of the list.
Consider the following example. Suppose you have a large list of sorted elements, either an ArrayList or a LinkedList. Suppose too that you do a binary search on the list. The standard binary search algorithm starts by checking the search key against the value in the middle of the list. If the middle value is too high, then the upper half of the list is eliminated. However, if the middle value is too low, then the lower half of the list is ignored. This process continues until the key is found in the list, or until the lower bound of the search becomes greater than the upper bound.
Here's a program that does a binary search on all the elements in an ArrayList or a LinkedList:
import java.util.*;
public class ListDemo1 {
static final int N = 10000;
static List values;
// make List of increasing Integer values
static {
Integer vals[] = new Integer[N];
Random rn = new Random();
for (int i = 0, currval = 0; i < N; i++) {
vals[i] = new Integer(currval);
currval += rn.nextInt(100) + 1;
}
values = Arrays.asList(vals);
}
// iterate across a list and look up every
// value in the list using binary search
static long timeList(List lst) {
long start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
// look up a value in the list
// using binary search
int indx = Collections.binarySearch(
lst, values.get(i));
// sanity check for result
// of binary search
if (indx != i) {
System.out.println(
"*** error ***\n");
}
}
return System.currentTimeMillis() - start;
}
public static void main(String args[]) {
// do lookups in an ArrayList
System.out.println("time for ArrayList = " +
timeList(new ArrayList(values)));
// do lookups in a LinkedList
System.out.println(
"time for LinkedList = " +
timeList(new LinkedList(values)));
}
}
The ListDemo1 program sets up a List of sorted Integer values. It then adds the values to an ArrayList or a LinkedList. Then Collections.binarySearch is used to search for each value in the list.
When you run this program, you should see a result that looks something like this:
time for ArrayList = 31
time for LinkedList = 4640
ArrayList is about 150 times faster than LinkedList. (Your results might differ depending on your machine characteristics, but you should see a distinct difference in the result for ArrayList as compared to that for LinkedList. The same is true for the other programs in this tip.) Clearly, LinkedList is a bad choice in this situation. The binary search algorithm inherently uses random access, and LinkedList does not support fast random access. The time to do a random access in a LinkedList is proportional to the size of the list. By comparison, random access in an ArrayList has a fixed time.
You can use the RandomAccess marker interface to check whether a List supports fast random access:
void f(List lst) {
if (lst instanceof RandomAccess) {
// supports fast random access
}
}
ArrayList implements the RandomAccess interface, and LinkedList. does not. Note that Collections.binarySearch does take advantage of the RandomAccess property, to optimize searches.
Do these results prove that ArrayList is always a better choice? Not necessarily. There are many cases where LinkedList does better. Also note that there are many situations where an algorithm can be implemented efficiently for LinkedList. An example is reversing a LinkedList using Collections.reverse. The internal algorithm does this, and gets reasonable performance, by using forward and backward iterators.
Let's look at another example. Suppose you have a list of elements, and you do a lot of element inserting and deleting to the list. In this case, LinkedList is the better choice. To demonstrate that, consider the following "worst case" scenario. In this demo, a program repeatedly inserts elements at the beginning of a list. The code looks like this:
import java.util.*;
public class ListDemo2 {
static final int N = 50000;
// time how long it takes to add
// N objects to a list
static long timeList(List lst) {
long start = System.currentTimeMillis();
Object obj = new Object();
for (int i = 0; i < N; i++) {
lst.add(0, obj);
}
return System.currentTimeMillis() - start;
}
public static void main(String args[]) {
// do timing for ArrayList
System.out.println(
"time for ArrayList = " +
timeList(new ArrayList()));
// do timing for LinkedList
System.out.println(
"time for LinkedList = " +
timeList(new LinkedList()));
}
}
When you run this program, the result should look something like this:
time for ArrayList = 4859
time for LinkedList = 125
These results are pretty much the reverse of the previous example.
When an element is added to the beginning of an ArrayList, all of the existing elements must be pushed back, which means a lot of expensive data movement and copying. By contrast, adding an element to the beginning of a LinkedList simply means allocating an internal record for the element and then adjusting a couple of links. Adding to the beginning of a LinkedList has fixed cost, but adding to the beginning of an ArrayList has a cost that's proportional to the list size.
So far, this tip has looked at speed issues, but what about space? Let's look at some internal details of how ArrayList and LinkedList are implemented in Java 2 SDK, Standard Edition v 1.4. These details are not part of the external specification of these classes, but are illustrative of how such classes work internally.
The LinkedList class has a private internal class defined like this:
private static class Entry {
Object element;
Entry next;
Entry previous;
}
Each Entry object references a list element, along with the next and previous elements in the LinkedList -- in other words, a doubly-linked list. A LinkedList of 1000 elements will have 1000 Entry objects linked together, referencing the actual list elements. There is significant space overhead in a LinkedList structure, given all these Entry objects.
An ArrayList has a backing Object array to sto
