references:
http://www.javaperformancetuning.com/articles/randomaccess.shtml
http://*.com/questions/322715/when-to-use-linkedlist-over-arraylist
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>
-
get(int index)is O(n) -
add(E element)is O(1) -
add(int index, E element)is O(n) -
remove(int index)is O(n) -
Iterator.remove()is O(1) <--- main benefit ofLinkedList<E> -
ListIterator.add(E element)is O(1) <--- main benefit ofLinkedList<E>
For ArrayList<E>
-
get(int index)is O(1) <--- main benefit ofArrayList<E> -
add(E element)is O(1) amortized, but O(n) worst-case since the array must be resized and copied -
add(int index, E element)is O(n - index) amortized, but O(n) worst-case (as above) -
remove(int index)is O(n - index) (i.e. removing last is O(1)) -
Iterator.remove()is O(n - index) -
ListIterator.add(E element)is O(n - index)
LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.
ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)
The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).
Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.7). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.
It's worth noting that Vector also implements the List interface and is almost identical to ArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.
Thusfar, nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList is "lots more" than an ArrayList so I did some number crunching to demonstrate exactly how much both lists take up for N null references.
Since references are either 32 or 64 bits (even when null) on their relative systems, I have included 4 sets of data for 32 and 64 bit LinkedLists and ArrayLists.
Note: The sizes shown for the ArrayList lines are for trimmed lists - In practice, the capacity of the backing array in an ArrayList is generally larger than its current element count.
Note 2: (thanks BeeOnRope) As CompressedOops is default now from mid JDK6 and up, the values below for 64-bit machines will basically match their 32-bit counterparts, unless of course you specifically turn it off.
The result clearly shows that LinkedList is a whole lot more than ArrayList, especially with a very high element count. If memory is a factor, steer clear of LinkedLists.
The formulas I used follow, let me know if I have done anything wrong and I will fix it up. 'b' is either 4 or 8 for 32 or 64 bit systems, and 'n' is the number of elements. Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not.
ArrayList:
ArrayList object header + size integer + modCount integer + array reference +(array oject header + b * n)+ MOD(array oject,8)+ MOD(ArrayList object,8)==8+4+4+ b +(12+ b * n)+ MOD(12+ b * n,8)+ MOD(8+4+4+ b +(12+ b * n)+ MOD(12+ b * n,8),8)LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer +(node object overhead + reference to previous element + reference to next element + reference to element)* n)+ MOD(node object,8)* n + MOD(LinkedList object,8)==8+4+4+2* b +(8+3* b)* n + MOD(8+3* b,8)* n + MOD(8+4+4+2* b +(8+3* b)* n + MOD(8+3* b,8)* n,8)
Testing:
ArrayListLinkedListAddAll(Insert)101,167192623,29291Add(Insert-Sequentially)152,46840966,62216Add(insert-randomly)3652729193
remove (Delete)20,56,909520,45,4904
contains (Search)186,15,704189,64,981import org.junit.Assert;
import org.junit.Test; import java.util.*; public class ArrayListVsLinkedList {
private static final int MAX = 500000;
String[] strings = maxArray(); ////////////// ADD ALL ////////////////////////////////////////
@Test
public void arrayListAddAll() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX); watch.start();
arrayList.addAll(stringList);
watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
} @Test
public void linkedListAddAll() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings); watch.start();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds
} //Note: ArrayList is 26 time faster here than LinkedList for addAll() ///////////////// INSERT /////////////////////////////////////////////
@Test
public void arrayListAdd() {
Watch watch = new Watch();
List<String> arrayList = new ArrayList<String>(MAX); watch.start();
for (String string : strings)
arrayList.add(string);
watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
} @Test
public void linkedListAdd() {
Watch watch = new Watch(); List<String> linkedList = new LinkedList<String>();
watch.start();
for (String string : strings)
linkedList.add(string);
watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds
} //Note: ArrayList is 9 times faster than LinkedList for add sequentially /////////////////// INSERT IN BETWEEN /////////////////////////////////////// @Test
public void arrayListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
arrayList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40); watch.start(); arrayList.add(insertString0);
arrayList.add(insertString1);
arrayList.add(insertString2);
arrayList.add(insertString3); watch.totalTime("Array List add() = ");//
} @Test
public void linkedListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40); watch.start(); linkedList.add(insertString0);
linkedList.add(insertString1);
linkedList.add(insertString2);
linkedList.add(insertString3); watch.totalTime("Linked List add = ");//
} //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly. ////////////////// DELETE //////////////////////////////////////////////////////
@Test
public void arrayListRemove() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX); arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20); watch.start();
arrayList.remove(searchString0);
arrayList.remove(searchString1);
watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
} @Test
public void linkedListRemove() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20); watch.start();
linkedList.remove(searchString0);
linkedList.remove(searchString1);
watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
} //Note: LinkedList is 10 millisecond faster than ArrayList while removing item. ///////////////////// SEARCH ///////////////////////////////////////////
@Test
public void arrayListSearch() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX); arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20); watch.start();
arrayList.contains(searchString0);
arrayList.contains(searchString1);
watch.totalTime("Array List addAll() time = ");//186,15,704
} @Test
public void linkedListSearch() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20); watch.start();
linkedList.contains(searchString0);
linkedList.contains(searchString1);
watch.totalTime("Linked List addAll() time = ");//189,64,981
} //Note: Linked List is 500 Milliseconds faster than ArrayList class Watch {
private long startTime;
private long endTime; public void start() {
startTime = System.nanoTime();
} private void stop() {
endTime = System.nanoTime();
} public void totalTime(String s) {
stop();
System.out.println(s + (endTime - startTime));
}
} private String[] maxArray() {
String[] strings = new String[MAX];
Boolean result = Boolean.TRUE;
for (int i = 0; i < MAX; i++) {
strings[i] = getString(result, i);
result = !result;
}
return strings;
} private String getString(Boolean result, int i) {
return String.valueOf(result) + i + String.valueOf(!result);
}
}