ArrayList v.s. LinkedList - inserting time

Question

When I run (respectively):

package containers;

import java.util.*;

    public static void main(String[] args) {

    List<Integer> arLst = new ArrayList<Integer>();
    List<Integer> lnLst = new LinkedList<Integer>();

    long start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        arLst.add(i);
    }

    System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

    start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        lnLst.add(i);
    }

    System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}

I get roughly the same executing time. I know that Adding time should be faster for LinkedList. I wonder why.. (It makes sense that both for middle insertinon and last elemnt - since arrays know in O(1) where to insert, unlike LinkedList that has to go through the whole list, as I recall).

Both lists are arraylist and you only add to the first one. Is that your real code? Assuming this is a typo, you should read [this post](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) before drawing conclusions. — assylias, Aug 22 '12 at 13:39
Why do you think that adding time should be faster for `LinkedList`? Also, mandatory reading: http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Matt Ball, Aug 22 '12 at 13:41
You should measure the time after the list creation. It is not relevant to measure how long time it takes to create them. — maba, Aug 22 '12 at 13:42
LinkedList is a doubly linked list, btw -- so inserts at the end are just as cheap as at the beginning (O(1)). — yshavit, Aug 22 '12 at 13:50
Opps - my bad. Edited, though now it inclines more to ArrayList... — user1249569, Aug 22 '12 at 13:50

score 4 · Answer 1 · answered Aug 22 '12 at 13:41

4

Both lists know where the end of the list is so insertion time is almost the same. I would have expected LinkedList to be slightly slower as it creates a node for every element and uses more memory.

I get

TIntArrayList - 141 ms
ArrayList<Integer> - 810 ms
LinkedList<Integer> - 5190 ms.

TIntArrayList doesn't create an object for each element using the cache more efficiently.

answered Aug 22 '12 at 13:41

Peter Lawrey

525,659
79
751
1,130

@assylias ArrayList suffers large hits, so its worst case is not great, but on average its faster. – Peter Lawrey Aug 22 '12 at 13:46
@assylias, it has amortized O(1) add at the end, so resizing is irrelevant, plus it's rare the ArrayList grows unbound. Linked list alike structures (but not the trees) have virtually no benefits in non-concurrent setups. Use ArrayList/ArrayDeque unless you have very strong idea why you want a Linked structure. There are corner cases but they usually do not rely on java.util, yet a notable exception is LinkedHashMap (it's a linked list w/ an index) – bestsss Aug 23 '12 at 19:37
1

@assylias. as side note, most people fail to realize that traversing linked structure both by your own code and *especially by the GC* is exceptionally expensive since it virtually leads to a cache miss on each iteration... – bestsss Aug 23 '12 at 19:39
@bestsss I had not thought of it that way - interesting. – assylias Aug 23 '12 at 19:40

score 4 · Answer 2 · answered Aug 22 '12 at 13:41

4

Both your lists are ArrayLists... If you change on of them to LinkedList you won't notice a big difference either. Building an ArrayList the way you do has amortized complexity of O(1) per insertion.

answered Aug 22 '12 at 13:41

Mathias Schwarz

7,099
23
28

Not mention that he doesn't even add anything to the second list, and times them both at the same time. – jn1kk Aug 22 '12 at 13:42
Yeah, I didn't even notice that :-) – Mathias Schwarz Aug 22 '12 at 13:43

score 3 · Accepted Answer · edited May 23 '17 at 11:49

3

Your code differs from your explanation. However, here is the answer to your question:

ArrayList Vs LinkedList

edited May 23 '17 at 11:49

Community

1
1

answered Aug 22 '12 at 13:43

Oscar Perez

345
3
9

gkuzmin · Answer 4 · 2012-08-22T13:46:30.470

2

Ammm.... Maybe this:

List<Integer> lnLst = new ArrayList<>();

should look like this:

List<Integer> lnLst = new LinkedList<>();

And I can not understand what are you trying to measure. I think that you want to measure add perfromance and then your code should look like this:

    public static void main(String[] args) {

        List<Integer> arLst = new ArrayList<Integer>();
        List<Integer> lnLst = new LinkedList<Integer>();

        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            arLst.add(i);
        }

        System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

        start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            lnLst.add(i);
        }

        System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
    }

edited Aug 22 '12 at 13:46

answered Aug 22 '12 at 13:40

gkuzmin

2,414
17
24

There we go. This is how you do it OP. – jn1kk Aug 22 '12 at 13:46
1

You have a typo yourself. Second loop is adding to `arLst` again. – maba Aug 22 '12 at 13:48
1

Not a very good benchmark - you should warm up the jvm and monitor garbage collection to avoid inconsistent numbers. – assylias Aug 22 '12 at 13:49
Thanks, maba, fixed. Yep, assylias, it will be better to perform full GC before each test and JIT should be "warmed up". – gkuzmin Aug 22 '12 at 13:52
Oh, wow, didn't know we are running enterprise software benchmarks here. -_- – jn1kk Aug 22 '12 at 14:23
Your profiling is flawed. The second for loop might benefit from the first for loop warming up the cache. You should profile each scenario in a separate JVM invocation. – Steve Kuo Aug 22 '12 at 20:18
Somehow I've got a lot of replies to my post and I decided to make it clear that I did not pretend on "enterprise" or "best know solution" prise. And I did not pretend on any other prise too. I even can not say that my code is good. **I just wanted to correct @user1249569 code to some meaningful state and nothing more.** Thanks. – gkuzmin Aug 22 '12 at 20:35

score 0 · Answer 5 · answered Aug 22 '12 at 13:52

0

...since arrays know in O(1) where to insert, unlike LinkedList that has to go through the whole list, as I recall).

This isn't correct. Arrays (not ArrayLists) do not have a constant insert time, Java's ArrayList technically doesn't either (The add operation runs in amortized constant time for an ArrayList).

Further, inserting an element into a linked list is O(1):

In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list.

If you are inserting into a sorted list, the complexity becomes O(N).

answered Aug 22 '12 at 13:52

Chris Dargis

5,891
4
39
63

if you insert in a SortedLinked list the complexity is also O(n) since you have to traverse the list, actually it's even worse as it's a cache miss per iteration. Array backed structures have lower memory footprint and significantly faster traverse b/c of how the hardware works - i.e. cache lines and prefetching... LinkedList is just hardware unfriendly structure. – bestsss Aug 23 '12 at 19:49
@bestsss: While linked lists are not cache friendly, I don't agree that a cache miss affects `BigOh` time complexity. A cache miss results in a penalty: reading a block from memory (or disk, depending on what cache we are talking about) which is a constant time operation. Granted, not all constant time operations are created equal. – Chris Dargis Aug 23 '12 at 20:22
Of course, big O stays the same, even O(16n) is the same as O(n). My wording is bad. It's *even worse* is unrelated to the Big O but to the actual performance, something like *it gets even worse in practice*. – bestsss Aug 23 '12 at 21:23

ArrayList v.s. LinkedList - inserting time

5 Answers5

Linked