Comparison of ArrayList and LinkedList

Comparison of ArrayList and LinkedList Print Version

This comparison is based on IBM Java(tm)2 SDK, Standard Edition, v 1.3.1

I did an analysis of the source code of ArrayList and LinkedList. My findings are given under the heading "Source Analysis".

When I tried to prove my findings with real time examples, my observations were,

For add operations ArrayList is always faster than LinkedList.
There is no difference in remove operation speed.
There is no noticeable difference in iterator speed.
There is no noticeable difference in toArray method speed.

My conclusion is - Always favor using ArrayList over LinkedList. Even the worst case add operations to ArrayList are faster than add operations to LinkedList.

Source Analysis

Comparison of Add operation

Add operation appends the passed element to the end of the list.

LinkedList will always return with constant time.

ArrayList will take longer time if the maximum size of internal array has reached.

Reasons for this behavior can be understood by examining the algorithm of add operation in ArrayList and LinkedList.

Algorithm of add operation in LinkedList

add(Object newObject) {
create newnode;
newnode.value = newObject;
newnode.previous = head.previous;
newnode.next = head;

newnode.previous.next = newnode;
newnode.next.previous = newnode;
}

Algorithm of add operation in ArrayList

add(Object newObject) {
if internalArray.isFull() {
allocate new array;
copy old array values to new;
}
add newObject to internalArray;
}

Comparison of remove operation

remove operation in LinkedList have two forms,

one takes the index of the element to be removed as argument
another one takes the actual element to be removed as argument.

There is only one remove method in ArrayList,

it takes the index of the element as argument.

Comparison of remove(int index) method
Remove operations from the start or end of the LinkedList will be faster. The time taken for remove operation increases as we go to the middle of the list.

Remove operation from the start of ArrayList will take more time. The time taken for remove operation decreases as we go to the end of the list.

Reason for these observations can be understood by examining the algorithm.

Algorithm of remove(index) operation in LinkedList

remove(int index) {
if(index < size/2)
traverse from beginning of the list to reach the element at index
else
traverse from end of the list to reach the element at index

remove element at index; // constant time operation
}

Algorithm of remove(index) operation in ArrayList

remove(int index) {
Shifts any subsequent elements to the left
assign the last element to null
}

As we go to the end of the ArrayList the number of elements to be shifted decreases.

Conclusion based on source analysis

Use LinkedList when you handle a large number of objects and you can't predict the maximum size of the collection.
Use LinkedList if you need the remove(object) method.
Use LinkedList if your collection involves lot of remove operations from the start.

Source code of the test.java program used.

import java.util.*;

public class test {
    private static final int NUM_ELEMENTS = 100 * 1000;

    public static void main(String[] args) {

        // TESTING ADD METHODS.
        testAddWithSmallArrayList(); // took 62ms
        testAddWithBigArrayList(); // took 31ms

        testAddWithLinkedList(); // took 78ms

        // TESTING REMOVE METHODS.
        testRemoveFromStartingOfArrayList(); // took 0ms
        testRemoveFromEndOfArrayList(); // took 0ms

        testRemoveFromStartingOfLinkedList(); // took 0ms
        testRemoveFromEndOfLinkedList(); // took 0ms

        // TESTING THE ITERATOR SPEED.
        testArrayListIterator(); // took 0ms
        testLinkedListIterator(); // took 0ms

        // Comparison of Sort speed.
        // Sort speed depends on the speed of toArray method.
        testArrayListToArrayMethod(); // took 0ms
        testLinkedListToArrayMethod(); // took 0ms
    }

    private static void testAddWithSmallArrayList() {
        List arrayList = new ArrayList(1);
        System.out.println("*** Inside testAddWithSmallArrayList ***");
        testAdd(arrayList);
    }

    private static void testAddWithBigArrayList() {
        List arrayList = new ArrayList(NUM_ELEMENTS);
        System.out.println("*** Inside testAddWithBigArrayList ***");
        testAdd(arrayList);
    }

    private static void testAddWithLinkedList() {
        List linkedList = new LinkedList();
        System.out.println("*** Inside testAddWithLinkedList ***");
        testAdd(linkedList);
    }

    private static void testAdd(List list) {
        long time = System.currentTimeMillis();

        add(list);

        time = System.currentTimeMillis() - time;
        System.out.println(
            "Add on " + list.getClass().getSimpleName() + " took " + time);
    }

    private static void testRemoveFromStartingOfArrayList() {
        ArrayList arrayList = new ArrayList();
        add(arrayList);

        long time = System.currentTimeMillis();
        arrayList.remove(1);
        time = System.currentTimeMillis() - time;

        System.out.println("Remove from starting of ArrayList took " + time);
    }

    private static void testRemoveFromEndOfArrayList() {
        ArrayList arrayList = new ArrayList();
        add(arrayList);

        long time = System.currentTimeMillis();
        arrayList.remove(arrayList.size()-1);
        time = System.currentTimeMillis() - time;

        System.out.println("Remove from end of ArrayList took " + time);
    }

    private static void testRemoveFromStartingOfLinkedList() {
        List linkedList = new LinkedList();
        add(linkedList);

        long time = System.currentTimeMillis();
        linkedList.remove(1);
        time = System.currentTimeMillis() - time;

        System.out.println("Remove from starting of LinkedList took " + time);
    }

    private static void testRemoveFromEndOfLinkedList() {
        List linkedList = new LinkedList();
        add(linkedList);

        long time = System.currentTimeMillis();
        linkedList.remove(linkedList.size()-1);
        time = System.currentTimeMillis() - time;

        System.out.println("Remove from end of LinkedList took " + time);
    }

    private static void testArrayListIterator() {
        ArrayList arrayList = new ArrayList(NUM_ELEMENTS);
        add(arrayList);

        long time = System.currentTimeMillis();

        Iterator iterator = arrayList.iterator();
        while(iterator.hasNext()) {
            iterator.next();
        }
        time = System.currentTimeMillis() - time;
        System.out.println("ArrayList iterator took " + time);
    }

    private static void testLinkedListIterator() {
        List linkedList = new LinkedList();
        add(linkedList);

        long time = System.currentTimeMillis();

        Iterator iterator = linkedList.iterator();
        while(iterator.hasNext()) {
            iterator.next();
        }
        time = System.currentTimeMillis() - time;
        System.out.println("LinkedList iterator took " + time);
    }
    private static void testArrayListToArrayMethod() {
        ArrayList arrayList = new ArrayList(NUM_ELEMENTS);
        add(arrayList);

        long time = System.currentTimeMillis();
        arrayList.toArray();

        time = System.currentTimeMillis() - time;
        System.out.println("ArrayList toArray took " + time);
    }

    private static void testLinkedListToArrayMethod() {
        List linkedList = new LinkedList();
        add(linkedList);

        long time = System.currentTimeMillis();

        linkedList.toArray();

        time = System.currentTimeMillis() - time;
        System.out.println("LinkedList toArray took " + time);
    }

    private static void add(List list) {
        for (int i = 0; i < NUM_ELEMENTS; i++) {
            list.add(new Integer(i));
        }
    }
}