Which one runs faster, ArrayList or LinkedList? [duplicate]

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!

Answer 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.

Answer 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.