Weblogism

ArrayList vs. LinkedList for Stack implementation

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 Elements:

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.