Java – which runs faster, ArrayList or LinkedList?

There is already an answer to this question: > when to use LinkedList over ArrayList? 30

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 do I do on both lists? When I print out the time, ArrayList always runs faster than LinkedList Can anyone explain the time to perform better? Also let me know if there are any errors in the code thank you!

Solution

If you have to perform a lot of inserts and infrequent lookups, use LinkedList If you execute more queries than inserts, use ArrayList

The reason is as follows – ArrayList is supported by arrays with initial capacity Therefore, if you insert an item into the list, you must readjust its array capacity to accommodate the newly inserted item, and if you perform index feature insertion, you may also need to move existing items LinkedList, on the other hand, is supported by linked lists, where the creation of an item is always performed in a constant time - an item is created and assigned to the end of the list There is no readjustment here

Now to get an item from ArrayList, it always takes a fixed time, because it can easily index the background array in a constant time However, getting items from the LinkedList may cause you to traverse the entire linked list to find item nodes Therefore, in this case, its performance is lower than ArrayList

As can be seen from the above discussion, LinkedList is always better than ArrayList when you have more inserts, because the internal resizing of the latter is associated with the insert, while the former does not On the other hand, if you have infrequent inserts and frequent lookups, ArrayList will always be better than LinkedList, because the latter you may have to traverse the entire linked list structure to find the required items, while the former can quickly find your item array index in a constant time

When you work on a large number of projects, such as thousands of projects, all of the above effects will be visible and affect the performance of your application For fewer projects, the performance difference is not obvious

Now, you have some serious problems with your code For starters, you use an original type, because you lose all the types of safety provided by generic drugs, which is not good When writing new code, you should always use the generic version of the collection API 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 Project 23: do not use primitive types in new code for details

edit

It can be seen from the discussion in the comments that if you need to insert elements in the middle of the list or at random, ArrayList is better than LinkedList in performance, because the former will use memcpy to move elements very fast, and the latter must traverse the required index to insert new elements correctly, which is slow So for random insertion, ArrayList also outperforms LinkedList The only case is that LinkedList is better than ArrayList if you insert only at the end of the list and there are many of these inserts