When does ArrayList win over LinkedList in Java, and why is the answer almost always ArrayList?
Almost always the ArrayList, and the reason is about how the memory is laid out rather than about the theory.
The theory says that they are close. An ArrayList keeps its items in one block of memory, so getting the item at a known position is very quick. A LinkedList keeps its items in separate boxes that point at each other, so getting the item at a known position means walking along the chain from the start.
The reality is that the ArrayList wins almost all the time, for three reasons.
The first one is the memory layout. The items in an ArrayList sit next to each other, so the processor can pull several of them into its cache in one go. In a LinkedList, every item is somewhere else in memory, so the processor has to go and fetch each one separately.
The second one is the cost of adding. An ArrayList grows by doubling the size of its block of memory when it runs out of room, and it copies the items across once every so often. That is what people mean when they say that the ArrayList amortises the cost of growing. A LinkedList does not have that cost, but it does have another one.
The third one is that the LinkedList only has a fast insert when you already have the node in your hand. Finding the place to insert is still a walk along the chain, and that walk is the same cost as the walk that the ArrayList would have done to move the items across.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
// The list that you will almost always want.
List<Integer> arrayList = new ArrayList<Integer>();
// The list that is only worth it in a few special cases.
List<Integer> linkedList = new LinkedList<Integer>();
for (int index = 0; index < 100000; index++) {
arrayList.add(index);
linkedList.add(index);
}
System.out.println("array list size : " + arrayList.size());
System.out.println("linked list size : " + linkedList.size());
// Getting an item by its position is quick in the array list.
int fromArray = arrayList.get(50000);
int fromLinked = linkedList.get(50000);
System.out.println("from the array list : " + fromArray);
System.out.println("from the linked list : " + fromLinked);
}
}
So when is a LinkedList the right choice? When you are working with a queue or a stack and you are adding and removing from one end all the time. In that case the two operations are both cheap, and there is no copying. That is why the deque in the standard library is built on a linked structure rather than on an array.
The next question in this topic puts the costs in a table.