Comparison: Runtime of LinkedList addFirst() vs. ArrayList add(0, item)

Question

My partner and I are attempting to program a LinkedList data structure. We have completed the data structure, and it functions properly with all required methods. We are required to perform a comparative test of the runtimes of our addFirst() method in our LinkedList class vs. the add(0, item) method of Java's ArrayList structure. The expected complexity of the addFirst() method for our LinkedList data structure is O(1) constant. This held true in our test. In timing the ArrayList add() method, we expected a complexity of O(N), but we again received a complexity of approximately O(1) constant. This appeared to be a strange discrepancy since we are utilizing Java's ArrayList. We thought there may be an issue in our timing structure, and we would be most appreciative if any one could help us identify our problem. Our Java code for the timing of both methods is listed below:

public class timingAnalysis {

public static void main(String[] args) {

    //timeAddFirst();
    timeAddArray();

}

public static void timeAddFirst()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    MyLinkedList<Long> linkedList = new MyLinkedList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        linkedList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            linkedList.addFirst(i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

public static void timeAddArray()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    ArrayList<Long> testList = new ArrayList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        testList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            testList.add(0, i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

}

score 2 · Accepted Answer · answered Jun 20 '13 at 01:21

2

You want to test for different inputSize, but you perform the operation to test timesToLoop times, which is constant. So of course, it takes the same time. You should use:

for (long i = 0; i < inputSize; i++)
    testList.add(0, i);

answered Jun 20 '13 at 01:21

Boris Dalstein

7,015
4
30
59

score -1 · Answer 2 · answered Jun 20 '13 at 01:18

-1

As per my knowledge, Arraylist add operaion runs in O(1) time, so the results of your experiment are correct. I think the constant time for arrayList add method is amortized constant time.

As per java doc : adding n elements require O(N) time so that is why the amortized constant time for adding.

answered Jun 20 '13 at 01:18

voidMainReturn

3,339
6
38
66

2

Nope, add(index,value) is linear, not amortized constant: http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#add(int, E). Only add(value) is amortized constant, by adding the element at the end. – Boris Dalstein Jun 20 '13 at 01:22
@Makoto: `void add(int index, E element) Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).` – Boris Dalstein Jun 20 '13 at 01:28
Must've missed that line in a hurry. Thanks for that clarification. – Makoto Jun 20 '13 at 01:29
@Makoto actually, I have to say that the Java documentation is unclear. It indeed says that `add` (without any precision) is amortized constant, and it -may- be possible to implemented a add(int,E) in amortized constant too ("shifting any subsequent elements to the right" could be implicit, not performing an operation on each of them), especially for the special case index=0. But not the way Java has implemented [get(int)](http://stackoverflow.com/questions/2182597/time-complexity-for-java-arraylist) – Boris Dalstein Jun 20 '13 at 01:45
@Boris : yes actually thats what I thought when I read java doc, hence this answer. But from the explanation they have of add(index,E) it looks like it must be O(N) operation. I was thinking how, if it is, might it be constant time operation. – voidMainReturn Jun 20 '13 at 03:13
@Makoto Yes, since they do use an actual array for their implementation, it is O(n). But you can do smarter things that guarantees amortized constant insertion everywhere, if you are willing to loose the constant O(1) for access, (don't think it is possible to have both amortized constant for insertion and access, but I think, without being sure, that you can have amortized constant insertion and logarithmic access.) – Boris Dalstein Jun 20 '13 at 03:22
@Makoto I couldn't find the answer for what is in my last comment, so I actually posted a question here http://stackoverflow.com/questions/17204849/list-with-amortized-constant-or-logarithmic-insertion-how-fast-can-possibly-be – Boris Dalstein Jun 20 '13 at 03:41

Comparison: Runtime of LinkedList addFirst() vs. ArrayList add(0, item)

2 Answers2