I have never seen any real life code where using a linked list has been beneficial. In most cases there is just no need for it and it makes the code run like a dog.
Fine, if your code spends most of it's time inserting and deleting at random points in the list. But seriously come on.
The class below compares ArrayLists and LinkedLists:
package listtest;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public final class ListTest {
private static final int TESTS = 3;
private static final int[] LIST_SIZES = new int[] {1000, 10000, 100000 };
private static final Random RANDOM = new Random();
private static long doAdds(final List<Integer> list, final int adds) {
long startAdds = System.currentTimeMillis();
for (int i = 0; i < adds; i++) {
list.add(RANDOM.nextInt(Integer.MAX_VALUE));
}
long endAdds = System.currentTimeMillis();
long time = endAdds - startAdds;
return time;
}
private static long doSequentialGets(final List<Integer> list) {
long startGets = System.currentTimeMillis();
int size = list.size();
for (int i = 0; i < size; i++) {
int x = list.get(i);
}
long endGets = System.currentTimeMillis();
long time = endGets - startGets;
return time;
}
private static long doRandomGets(final List<Integer> list) {
long startGets = System.currentTimeMillis();
int size = list.size();
for (int i = 0; i < size; i++) {
int x = list.get(RANDOM.nextInt(size));
}
long endGets = System.currentTimeMillis();
long time = endGets - startGets;
return time;
}
public static void main(String[] args) {
long[] arrayListAddTimes = new long[TESTS];
long[] arrayListSequentialGetTimes = new long[TESTS];
long[] arrayListRandomGetTimes = new long[TESTS];
long[] linkedListAddTimes = new long[TESTS];
long[] linkedListSequentialGetTimes = new long[TESTS];
long[] linkedListRandomGetTimes = new long[TESTS];
for (int listSize : LIST_SIZES) {
for (int i = 0; i < TESTS; i++) {
List<Integer> arrayList = new ArrayList<Integer>();
List<Integer> linkedList = new LinkedList<Integer>();
arrayListAddTimes[i] = doAdds(arrayList, listSize);
linkedListAddTimes[i] = doAdds(linkedList, listSize);
arrayListSequentialGetTimes[i] = doSequentialGets(arrayList);
linkedListSequentialGetTimes[i] = doSequentialGets(linkedList);
arrayListRandomGetTimes[i] = doRandomGets(arrayList);
linkedListRandomGetTimes[i] = doRandomGets(linkedList);
}
System.out.println(String.format("\n----- list size : %s -----\n", listSize));
System.out.println(String.format("Array list adds mean time: %s ms", mean(arrayListAddTimes)));
System.out.println(String.format("Linked list adds mean time: %s ms\n", mean(linkedListAddTimes)));
System.out.println(String.format("Array list sequential gets mean time: %s ms",mean(arrayListSequentialGetTimes)));
System.out.println(String.format("Linked list sequential gets mean time: %s ms\n",mean(linkedListSequentialGetTimes)));
System.out.println(String.format("Array list random gets mean time: %s ms",mean(arrayListRandomGetTimes)));
System.out.println(String.format("Linked list random gets mean time: %s ms\n",mean(linkedListRandomGetTimes)));
}
}
private static long mean(final long[] times) {
long sum = 0;
for (long x : times) {
sum = sum + x;
}
int n = times.length;
return sum / n;
}
}
The code creates a LinkedList and an ArrayList and inserts random integers. The lists are then read sequentially and then read randomly. This is done for 1000, 10000 and 100000 integer lists, each one repeated 3 times and an average time calculated for: adding, reading sequentially and reading randomly. Check out some results from running this on my machine:
----- list size : 1000 ----- Array list adds mean time: 0 ms Linked list adds mean time: 0 ms Array list sequential gets mean time: 0 ms Linked list sequential gets mean time: 0 ms Array list random gets mean time: 0 ms Linked list random gets mean time: 0 ms ----- list size : 10000 ----- Array list adds mean time: 0 ms Linked list adds mean time: 5 ms Array list sequential gets mean time: 0 ms Linked list sequential gets mean time: 119 ms Array list random gets mean time: 0 ms Linked list random gets mean time: 109 ms ----- list size : 100000 ----- Array list adds mean time: 21 ms Linked list adds mean time: 41 ms Array list sequential gets mean time: 0 ms Linked list sequential gets mean time: 14125 ms Array list random gets mean time: 15 ms Linked list random gets mean time: 15374 ms
