Which one runs faster, ArrayList or LinkedList?

Question

List li = new LinkedList();

for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1-start1;

System.out.println("Time taken by LinkedList = "+diff1);

List al = new ArrayList();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

What ever operations I perform on both the lists, when I print out the time taken, ArrayList always runs faster than LinkedList. Can somebody explain which performs better in terms of time taken? Also let me know if there is something wrong in the code. Thanks!

Solution 1

If you have to perform lots of inserts and not-so-frequent lookup, use a LinkedList. Use ArrayList if you perform more lookup than inserts.

The reason is as follows - ArrayList is backed by an array which has an initial capacity. So, if you keep inserting items into the list, at one point it will have to re-adjust its array capacity to accommodate newly inserted items, and it may also have to shift the existing items if you perform an index-spcific inserts. On the other hand, LinkedList is backed by a linked list, where creating an item always executes in a constant time - create an item and assign it to the end of the list. No re-adjustment occurs here.

Now to fetch an item from the ArrayList, it will always take a constant amount of time since it can easily index the backing array in a constant time. But fetching an item from the LinkedList may cause you to traverse the entire linked list to find the item node. As a result, it performs less than ArrayList in this case.

From the above discussion, you can see that when you have more inserts to do, LinkedList will always outperform ArrayList because the latter has an internal resize cost associated with inserts while the former doesn't. On the other hand, if you have infrequent inserts and frequent lookups, ArrayList will always outperform LinkedList because for the latter you may have to traverse the entire linked list structure to find the desired item, while the former will be able to quickly find your items with array indexing in constant times.

All of the above effects will be visible and affect your application's performance when you are dealing with a lots of items (say, thousands of items). For a fewer items, the performance difference is not quite visible.

Now, about your code, you have some serious problems with it. For starter, you are using a raw type, which is bad as you lose all the type safety that generics have to offer. You should always use the generic version of the Collection API when you write new code. So, change your code as follows -

List<Integer> li = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1 - start1;

System.out.println("Time taken by LinkedList = "+diff1);

List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

See Effective Java, Item 23: Don't use raw types in new code for a detailed explanation.

EDIT

From the discussion in the comments, it should be obvious to you that if you need to insert elements in the middle of the list or at a random position, then ArrayList outperforms LinkedList in terms of performance, because the former will use memcpy to shift the elements which is extremely fast, and the latter will have to traverse up to the desired index to properly insert the new element, which is slower. So for random insertions ArrayList also outperforms LinkedList. The only case LinkedList outperforms ArrayList is if you only inserts at the end of your list, and there are lots of these inserts.

Solution 2

Array List will be always faster than Linked list in terms of read. ArrayList is basically array implementation and the memory allocated for an array is sequentially so read is faster. But when you using list which requires insertion or delete in between the list then Linked List is faster . Because it just had to add the links in between nodes. In these two cases array list will be slower.Usage can be :

ArrayList - Faster read operation, insertion,deletion between the list is slower. Linked List - Read operation slow compared to Array List but insertion,deletion between the list is faster.

Solution 3

ArrayList is backed by array and LinkedList backed Node's linked with refernece.

So operation on ArrayList is actaully evalute operation on array. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

and on LinkedList all of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

read more on documentation -

• ArrayList
• LinkedList

Comments

[Nandkumar Tekale]

did you check stackoverflow.com/questions/322715/… ? This link is the first in Related questions

[Vaibhav Desai]

For a loop of 100, the difference is negligible. Try a loop of 10 million or more.

[Jules]

duplicate of stackoverflow.com/questions/322715/… and stackoverflow.com/questions/10656471/…

[Jayaram]

programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector javarevisited.blogspot.in/2012/02/… link might help you

[Anjan Baradwaj]

@VaibhavDesai - That worked! I increased the number of elements to be added to the list, and now i can see that insertion at a random index is better in LinkedList than in ArrayList

[Sean Patrick Floyd]

"If you have to perform lots of inserts and not-so-frequent lookup, use a LinkedList" I'm wondering if that's true for inserts near the end of a large list. LinkedList would have to iterate almost the entire way before inserting, whereas ArrayList can rely on System.arrayCopy() which is a native operation and should be sufficiently fast. There has got to be a magic threshold number of elements here that makes ArrayList more effective (at least in this specific scenario)

[MD Sayem Ahmed]

@SeanPatrickFloyd: If the underlying linked list of LinkedList is implemented using a double-pointer-strategy, which means if it keeps pointers for both the start and the end of the linked list, then it won't have to traverse the entire structure. I have seen people to implement a linked list in this way for efficient insertion, the memory cost is just one extra pointer.

[Sean Patrick Floyd]

which is exactly what java.util.LinkedList does (just checked the code). I stand corrected. Or rather: now insertion near the middle is the extreme case :-)

[Anjan Baradwaj]

So, get(index) operation is faster in ArrayList and slower in LinkedList, and add(index,object) is faster in LinkedList and slower in ArrayList, correct?

[MD Sayem Ahmed]

@AnjanBaradwaj: yes, get is faster on ArrayList in this way, but for LinkedList, add(index, object) costs the same as ArrayList in the worst case, because then it too may have to shift items if you insert in the middle.

[Anjan Baradwaj]

As a conclusion, are there any specific cases as to which one is recommended to be used?

[MD Sayem Ahmed]

@AnjanBaradwaj: If you use add(object) on LinkedList (I am talking with respect to OpenJDK implementation, see the link in my previous comment), then it will perform better than ArrayList's add(object).

[MD Sayem Ahmed]

@AnjanBaradwaj: Yes, simple add(object) is faster on LinkedList, and simple get(index) is faster on ArrayList. Use LinkedList for frequent insertion, and use ArrayList for frequent look up.

[Sean Patrick Floyd]

@Sayem perhaps you misunderstood me, as I actually agreed with you (I checked the sun version which has a double pointer strategy, which it needs, since LinkedList implements Deque).

[yshavit]

It's a bit more subtle than that, actually. Firstly, inserting to the end of an ArrayList is in amortized constant time, so "on average" (that is, over a lot of inserts) it'll have the same growth as LinkedList. The worst-case is slower, but that's probably not as interesting if you're not working on a realtime-esq project (e.g. a game where you have to be done in time for the next frame). Plus, even if the asymptotic growth is larger, you have to account for the coefficients; memcpy is pretty darn fast. ArrayList might beat out LinkedList even in non-append inserts for small lists etc

[MD Sayem Ahmed]

@SeanPatrickFloyd: Yup, sorry, I got that after reading the comments again :P.