Which one is faster, ArrayList or LinkedList?

Question

List li = new LinkedList(); for (int i = 0; i &lt; 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 operations do I do on both lists, when I print the time, ArrayList always works faster than LinkedList. Can someone explain what works best in terms of time? Also let me know if something is wrong in the code. Thank!

Answer 1

If you need to perform a lot of inserts and not very frequent searches, use LinkedList . Use an ArrayList if you are doing more searches than inserts.

The reason is this: ArrayList supported by an array that has an initial capacity. Thus, if you continue to insert elements into the list, at some point he will have to re-configure his array capacity to accommodate the newly inserted elements, and may also have to move existing elements if you perform indexed inserts. On the other hand, LinkedList supported by a linked list, where the creation of an element is always performed at a constant time - create an element and assign it to the end of the list. No reconfiguration takes place here.

Now, to get an element from an ArrayList , it will always take constant time, since it can easily index the support array in constant time. But selecting an element from a LinkedList can cause you to go through the entire linked list to find the node element. As a result, in this case, it executes less than an ArrayList .

From the discussion above, you can see that when you have more attachments, LinkedList always outperforms ArrayList , because the latter has an internal resizing cost associated with the inserts, and the former does not. On the other hand, if you have rare inserts and frequently encountered queries, ArrayList always superior to LinkedList , because for the latter you may have to go through the entire structure of the linked list to find the element you need, while the former can quickly find your elements with indexing the array at constant times.

All of the above effects will be visible and will affect the performance of your application when you are dealing with a large number of items (for example, thousands of items). For fewer elements, the difference in performance is not entirely clear.

Now, about your code, you have serious problems with it. For the starter, you use a raw type, which is bad because you lose all the type safety that generics can offer. You should always use the generic version of the Collection API when writing 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 . Paragraph 23: Do not use raw types in the 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 in an arbitrary position, then ArrayList superior to LinkedList in terms of performance, since the former will use memcpy to offset elements that are extremely fast, and the latter should go to the desired index to correctly insert a new element that is slower. Thus, for random insertions, ArrayList also outperforms LinkedList . The only case of LinkedList superior to ArrayList if you only insert at the end of your list, and there are many of these inserts.

Answer 2

ArrayList supported by array and LinkedList with Node support related to refernece.

Thus, an operation on an ArrayList is an actaully evalute operation in an array. The add operation operates in amortized constant time mode, that is, adding O(n) elements takes O(n) . All other operations are performed in linear time (roughly speaking). The constant coefficient is low compared to that for the implementation of LinkedList .

and LinkedList all operations are performed as you would expect for a doubly linked list. Operations that are indexed into a list will move through the list from beginning to end, depending on which is closer to the specified index.

Read more about the documentation -

• Arraylist
• LinkedList

Answer 3

A list of arrays will always be faster than a linked list in terms of reading. ArrayList is basically an implementation of the array, and the memory allocated for the array is sequentially read faster. But when you use a list that requires insertion or deletion between the list, then the Linked List is faster. Because he just needed to add links between nodes. In these two cases, the list of arrays will be slower. Use may be:

ArrayList - faster read, insert, delete between the list is slower. A linked list is slow reading compared to an array, but inserting, deleting between lists is faster.

Answer 4

The linked list will include the creation of a new node when each element is added, while it is not in the list of arrays.

If you know the size of inital, then pass it to an ArrayList when creating, it avoids restoring the array as a new ArrayList (100);