This comment made me think: how does a LinkedList fare against an ArrayList for a Stack implementation? Sure, LinkedList should be better for insertion and deletion… But is it? And when does it start to matter (i.e. how many objects)? So I have set up a little benchmark. First, a Stack interface:
public interface Stack<T> {
public void push(T element);
public T pop();
public int size();
}
In this stack, we’ll be pushing and popping =Element=s:
public class Element {
}
Our stack will allow us to pass either an ArrayList or a LinkedList as the implementation:
import java.util.List;
public class GenericStack<T, U extends List<T>> implements Stack<T> {
private U list;
public GenericStack(U list) {
this.list = list;
}
public T pop() {
if (!list.isEmpty()) {
return list.remove(0);
} else throw new IndexOutOfBoundsException("Cannot pop an empty stack");
}
public void push(T element) {
list.add(0, element);
}
public int size() {
return list.size();
}
The benchmark itself is the following main:
public static void main(String[] args) {
int values[] = {1000, 2000, 5000, 10000, 50000, 100000, 500000, 1000000};
GenericStack<Element, ArrayList<Element>> arrayListStack
= new GenericStack<Element, ArrayList<Element>>(new ArrayList<Element>());
GenericStack<Element, LinkedList<Element>> linkedListStack
= new GenericStack<Element, LinkedList<Element>>(new LinkedList<Element>());
for (int v = 0; v < values.length; v++) {
int currentSize = values[v];
System.out.println("pushing " + currentSize + " elements");
System.out.println();
long start = System.currentTimeMillis();
for (int i = 0; i < currentSize; i++) {
arrayListStack.push(new Element());
}
double time = (System.currentTimeMillis() - start) / (float) currentSize;
System.out.println("arraylist stack push: " + time);
start = System.currentTimeMillis();
for (int i = 0; i < currentSize; i++) {
linkedListStack.push(new Element());
}
time = (System.currentTimeMillis() - start) / (float) currentSize;
System.out.println("linkedlist stack push: " + time);
System.out.println("popping " + currentSize + " elements");
System.out.println();
for (int i = 0; i < currentSize; i++) {
arrayListStack.pop();
}
time = (System.currentTimeMillis() - start) / (float) currentSize;
System.out.println("arraylist stack pop: " + time);
for (int i = 0; i < currentSize; i++) {
linkedListStack.pop();
}
time = (System.currentTimeMillis() - start) / (float) currentSize;
System.out.println("linkedlist stack pop: " + time);
System.out.println();
}
}
And here are the results (in milliseconds):
pushing 1000 elements arraylist stack push: 0.0 linkedlist stack push: 0.0 popping 1000 elements arraylist stack pop: 0.0 linkedlist stack pop: 0.0 pushing 2000 elements arraylist stack push: 0.0 linkedlist stack push: 0.0 popping 2000 elements arraylist stack pop: 0.0 linkedlist stack pop: 0.0 pushing 5000 elements arraylist stack push: 0.0031999999191612005 linkedlist stack push: 0.0 popping 5000 elements arraylist stack pop: 0.003000000026077032 linkedlist stack pop: 0.003000000026077032 pushing 10000 elements arraylist stack push: 0.006300000008195639 linkedlist stack push: 0.0 popping 10000 elements arraylist stack pop: 0.004699999932199717 linkedlist stack pop: 0.004699999932199717 pushing 50000 elements arraylist stack push: 0.022180000320076942 linkedlist stack push: 0.0 popping 50000 elements arraylist stack pop: 0.022180000320076942 linkedlist stack pop: 0.022180000320076942 pushing 100000 elements arraylist stack push: 0.04374999925494194 linkedlist stack push: 3.1999999191612005E-4 popping 100000 elements arraylist stack pop: 0.04407000169157982 linkedlist stack pop: 0.04407000169157982 pushing 500000 elements arraylist stack push: 0.2210640013217926 linkedlist stack push: 4.0600000647827983E-4 popping 500000 elements arraylist stack pop: 0.22146999835968018 linkedlist stack pop: 0.2214999943971634 pushing 1000000 elements arraylist stack push: 0.4516749978065491 linkedlist stack push: 4.220000118948519E-4 popping 1000000 elements arraylist stack pop: 0.45311200618743896 linkedlist stack pop: 0.45315900444984436
So a significant difference only appears when pushing 10,000 elements, and after that, it degrades quite dramatically in favour of the LinkedList.
ArrayList that bad?
Now, it appears that we have kind of disadvantaged ArrayList here by choosing the worst case scenario for insertion: inserting at index 0, which means that the implementation will have to enlarge the internal array if needed, shift all the objects by 1, and insert the element at 0.
So let’s have more specific implementation where we’ll be "pushing" at the end (and therefore "popping" at the end too). Here is our new ArrayListStack:
import java.util.ArrayList;
public class ArrayListStack<T> implements Stack<T> {
private ArrayList<T> list = new ArrayList<T>();
public T pop() {
if (!list.isEmpty()) {
return list.remove(list.size() - 1);
} else throw new IndexOutOfBoundsException("Cannot pop an empty stack");
}
public void push(T element) {
list.add(element);
}
public int size() {
return list.size();
}
}
To be fair, let’s give LinkedList its own implementation, with getFirst() and removeFirst():
import java.util.LinkedList;
public class LinkedListStack<T> implements Stack<T> {
private LinkedList<T> list = new LinkedList<T>();
public T pop() {
if (!list.isEmpty()) {
return list.removeFirst();
} else throw new IndexOutOfBoundsException("Cannot pop an empty stack");
}
public void push(T element) {
list.addFirst(element);
}
public int size() {
return list.size();
}
}
And now you’re in for a good surprise: here are the results!
pushing 1000 elements arraylist stack push: 0.0 linkedlist stack push: 0.0 popping 1000 elements arraylist stack pop: 0.0 linkedlist stack pop: 0.0 pushing 2000 elements arraylist stack push: 0.0 linkedlist stack push: 0.007499999832361937 popping 2000 elements arraylist stack pop: 0.007499999832361937 linkedlist stack pop: 0.007499999832361937 pushing 5000 elements arraylist stack push: 0.0 linkedlist stack push: 0.0 popping 5000 elements arraylist stack pop: 0.0 linkedlist stack pop: 0.0 pushing 10000 elements arraylist stack push: 0.0 linkedlist stack push: 0.0 popping 10000 elements arraylist stack pop: 0.0 linkedlist stack pop: 0.0 pushing 50000 elements arraylist stack push: 0.0 linkedlist stack push: 3.1999999191612005E-4 popping 50000 elements arraylist stack pop: 3.1999999191612005E-4 linkedlist stack pop: 3.1999999191612005E-4 pushing 100000 elements arraylist stack push: 1.5999999595806003E-4 linkedlist stack push: 3.100000030826777E-4 popping 100000 elements arraylist stack pop: 3.100000030826777E-4 linkedlist stack pop: 3.100000030826777E-4 pushing 500000 elements arraylist stack push: 2.800000074785203E-4 linkedlist stack push: 4.3799998820759356E-4 popping 500000 elements arraylist stack pop: 4.6999999904073775E-4 linkedlist stack pop: 4.6999999904073775E-4 pushing 1000000 elements arraylist stack push: 9.40000027185306E-5 linkedlist stack push: 4.3700000969693065E-4 popping 1000000 elements arraylist stack pop: 4.529999860096723E-4 linkedlist stack pop: 4.6800001291558146E-4
In these results, ArrayList performs better, and after 1,000,000 the difference is actually stunning. And that’s even before adding the extra optimization of sizing the list at initialization (thus preventing the overhead of redimensioning the array).
The thing is, adding at the end of an ArrayList will perform better than LinkedList, so this means that for a stack implementation (where you push and pop at the same end), ArrayList is quite a good pick.