Performance Differences Between ArrayList and LinkedList

Question

Yes, this is an old topic, but I still have some perplexities.

In Java, people say:

• ArrayList is faster than LinkedList if I accidentally access its elements. I think random access means "give me the nth element". Why is ArrayList faster?

• LinkedList is faster than ArrayList for deletion. I understand it. ArrayList is slower because the internal backup array needs to be reallocated. Code Explanation:

  List<String> list = new ArrayList<String>(); list.add("a"); list.add("b"); list.add("c"); list.remove("b"); System.out.println(list.get(1)); //output "c" 

• LinkedList is faster than ArrayList for insertion. What does insert mean here? If this means moving some elements back and then putting the element in the middle empty space, the ArrayList should be slower than the LinkedList. If inserting means only an add operation (Object), how can it be slow?

Answer 1

ArrayList is faster than LinkedList if I accidentally access its elements. I think random access means "give me the nth element". Why is ArrayList faster?

ArrayList has direct links to each element in the list, so it can get the nth element in constant time. LinkedList has to traverse the list from the very beginning to go to the nth element.

LinkedList is faster than ArrayList for deletion. I understand it. ArrayList is slower because the internal backup array needs to be reallocated.

ArrayList is slower because it needs to copy part of the array to remove the freed slot. If the deletion is done using the ListIterator.remove() API, the LinkedList just needs to be manipulated with multiple links; if the deletion is performed by value or index, LinkedList first potentially scans the entire list to find the item (s) to be deleted.

If this means moving some elements back and then putting the element in the middle empty space, the ArrayList should be slower.

Yes, that is what it means. ArrayList really slower than LinkedList because it needs to free a slot in the middle of the array. This is due to the movement of some links around and in the worst case, the redistribution of the entire array. LinkedList just needs to manipulate some links.

Answer 2

Ignore this answer. Other answers, particularly aix, are mostly correct. In the long run, they can bet. And if you have enough data (one model on one machine, it seems, about a million records), ArrayList and LinkedList currently work as advertised. However, there are some subtleties that apply at the beginning of the XXI century.

Modern computer technology, according to my tests, gives a huge advantage to arrays. Array elements can be shifted and copied at insane speeds. As a result, arrays and ArrayList will in most practical situations outperform LinkedList in insertions and deletions, often dramatically. In other words, ArrayList will beat LinkedList in its own game.

The disadvantage of ArrayList is that it tends to hang on memory space after deletion, where LinkedList discards space when it issues records.

The larger the back of arrays and ArrayList, the more they are free from fragments and overload the garbage collector. As the ArrayList array expands, it creates new larger arrays, copies the old array to the new one, and frees the old one. The memory is filled with large adjacent pieces of free memory, which are not large enough for the next distribution. In the end, there is no suitable place for this distribution. Although 90% of the memory is free, not a single piece is large enough to do the job. The GC will work desperately to move things, but if it takes too long to rebuild the space, it will throw an OutOfMemoryException. If he does not give up, he can still slow down the program.

Worst of all, this problem is difficult to predict. Your program will work fine once. Then, with less memory, without warning, it slows down or stops.

LinkedList uses a small, graceful bit of memory and the GC loves it. It still works fine when you use 99% of the available memory.

In general, use an ArrayList for smaller datasets that are unlikely to delete most of their contents, or when you have tight control over creation and growth. (For example, creating one ArrayList that uses 90% of the memory and using it without filling it for the duration of the program is okay. Constantly creating and freeing ArrayList instances that use 10% of memory will kill you.) Otherwise, go to LinkedList (or any card if you need random access). If you have very large collections (for example, more than 100,000 items), there are no problems with the GC, as well as planning a lot of insertions and deletions and no random access, run a few benchmarks to find out which is faster.

Answer 3

The ArrayList class is a wrapper class for an array. It contains an internal array.

 public ArrayList<T> { private Object[] array; private int size; } 

A LinkedList is a wrapper class for a linked list with an internal node for data management.

 public LinkedList<T> { class Node<T> { T data; Node next; Node prev; } private Node<T> first; private Node<T> last; private int size; } 

Note. This code is used to show how a class can be, and not an actual implementation. Knowing how this can be implemented, we can conduct further analysis:

ArrayList is faster than LinkedList if I accidentally access its elements. I think random access means "give me the nth element". Why is ArrayList faster?

Access time for ArrayList: O (1). Access time for LinkedList: O (n).

In an array, you can access any element using array[index] , while in a linked list you have to move through the whole list, starting with first , until you get the element you need.

LinkedList is faster than ArrayList for deletion. I understand it. ArrayList is slower because the internal backup array needs to be reallocated.

Delete time for ArrayList: access time + O (n). Delete time for LinkedList: access time + O (1).

An ArrayList must move all elements from array[index] to array[index-1] , starting with the element, to remove the index. LinkedList should go to this element and then remove this node, separating it from the list.

LinkedList is faster than ArrayList for deletion. I understand it. ArrayList is slower because the internal backup array needs to be reallocated.

Insertion time for ArrayList: O (n). Insert time for LinkedList: O (1).

Why can an ArrayList accept O (n)? Because when you insert a new element and the array is full, you need to create a new array with a large size (you can calculate a new size with a formula of size 2 * or 3 * size / 2). LinkedList just adds a new node next to the last.

This analysis takes place not only in Java, but also in other programming languages, such as C, C ++ and C #.

More details here:

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Answer 4

Both remove () and insert () methods have O (n) execution efficiency for both ArrayLists and LinkedLists. However, the reason for the linear processing time depends on two different reasons:

In ArrayList, you get to an element in O (1), but actually removing or inserting something makes it O (n), because you need to change all of the following elements.

LinkedList requires O (n) to actually go to the right element, because we have to start from the very beginning until we reach the desired index. Removing or inserting is permanent when we get there, because we only need to change 1 link for remove () and 2 links for insert ().

Which of the two is faster for insertion and deletion depends on where this happens. If we are closer to the beginning, LinkedList will be faster because we need to go through relatively few elements. If we are near the end, the ArrayList will be faster because we will get there at a constant time and only need to change the few remaining elements that follow it.

Bonus: Although there is no way to do these two O (1) methods for ArrayList, there is actually a way to do this in LinkedLists. Suppose we want to go through the entire list by deleting and inserting elements in our path. Usually you start from the very beginning for each element using a LinkedList, we can also “save” the current element that we are working with Iterator with. With Iterator we get O (1) efficiency for remove () and insert () when working in LinkedList. Being the only performance benefit, I know where LinkedList is always better than ArrayList.

Answer 5

Answer to 1: ArrayList uses an array under the hood. Accessing an object of an ArrayList object is as simple as accessing an array with the provided index, provided that the index is within the support array. LinkedList must iterate through its members in order to go to the nth element. This is O (n) for LinkedList, compared to O (1) for ArrayList.

Answer 6

In LinkedList, elements have a link to the element before and after it. In ArrayList, the data structure is just an array.

• A LinkedList must iterate over N elements to get an Nth element. ArrayList should only return element N of the support array.

• The base array must either be redistributed for the new size, or the array copied on top of each element after deleting the deleted element to fill the empty space. A LinkedList simply needs to set the previous link to the item after deletion before it was deleted, and the next link to the item before the deleted item in the item after the item to be deleted. Explain longer, but do faster.

• For the same reason as removal.

Answer 7

Arraylist

• ArrayList is the best choice if our frequent operation is a search operation.
• ArrayList is the worst choice if our operation is insertion and deletion in the middle, because several shift operations are internally performed.
• In an ArrayList, items will be stored in sequential memory cells, so the search operation becomes easy.

LinkedList: -

• LinkedList is the best choice if inserting and deleting in the middle is our common operation.
• LinkedList is the worst choice, our frequent operation is the search operation.
• In LinkedList, items will not be stored in a sequential memory location, and therefore the search operation will be complicated.

Now let's get to your questions:

1) ArrayList stores data according to indexes and implements the RandomAccess interface, which is a marker interface that allows random retrieval in ArrayList, but LinkedList does not implement the RandomAccess interface, so ArrayList is faster than LinkedList.

2) The basic data structure for LinkedList is a doubly linked list, so inserting and deleting in the middle is very simple in LinkedList, since it does not need to move every element for every delete and insert operation, like ArrayList (which is not recommended if our operation is insert and delete in the middle, because several shift operations are performed inside).
Source

Answer 8

ArrayList : ArrayList has a structure similar to an array, it has a direct link to each element. Thus, access to Rendom is quickly performed in ArrayList.

LinkedList In LinkedList, to get the nth element you need to go through the whole list, it takes time compared to ArrayList. Each item has a link to its previous item and socket item, so deletion is quick.

Answer 9

ArrayList: The ArrayList class extends AbstractList and implements the List and RandomAccess (marker interface) interface. ArrayList supports dynamic arrays that can grow as needed. It gives us the first iteration on the elements.

LinkedList: LinkedList is sorted by index position, such as ArrayList, except that the elements are double-linked. This binding gives you new methods (besides what you get from the List interface) for adding and removing from the very beginning or the end, which makes it an easy choice for implementing a stack or queue. Keep in mind that LinkedList can iterate more slowly than ArrayList , but it's a good choice when you need quick insert and delete. . With Java 5, the LinkedList class has been extended to implement java. util.Queue. Thus, it now supports common queue methods: peek (), poll (), and offer ().

Answer 10

I want to add more information about the difference in performance to her.

We already know that due to the fact that the ArrayList implementation is supported by Object[] it supports random access and dynamic resizing, while the LinkedList implementation uses links to head and tail to navigate it. It does not have random access, but it also supports dynamic resizing.

First, with ArrayList you can immediately access the index, while with LinkedList you have iteration over the chain of objects.

Secondly, inserting into an ArrayList usually happens more slowly because it needs to grow as soon as you reach its borders. He will have to create a new larger array and copy the data from the original.

But the interesting thing is that when you create an ArrayList that is already large enough to accommodate all your inserts, it obviously will not include any array copy operations. Adding to it will be even faster than with LinkedList, because LinkedList will deal with its pointers, while the huge ArrayList simply sets the value at the given index.

Check out more differences between ArrayList and LinkedList .

Answer 11

Even they seem identical (the same implemented inteface List is non thread-safe), they give different results in terms of add / remove performance, search time and memory consumption (LinkedList consumes more).

LinkedLists can be used if you use a high degree of insert / delete with O (1) performance. ArrayLists can be used if you use direct access operations with O (1) performance

This code may exclude these comments, and you can try to understand the results of the work. (Sorry for the boiler plate code)

 public class Test { private static Random rnd; static { rnd = new Random(); } static List<String> testArrayList; static List<String> testLinkedList; public static final int COUNT_OBJ = 2000000; public static void main(String[] args) { testArrayList = new ArrayList<>(); testLinkedList = new LinkedList<>(); insertSomeDummyData(testLinkedList); insertSomeDummyData(testArrayList); checkInsertionPerformance(testLinkedList); //O(1) checkInsertionPerformance(testArrayList); //O(1) -> O(n) checkPerformanceForFinding(testArrayList); // O(1) checkPerformanceForFinding(testLinkedList); // O(n) } public static void insertSomeDummyData(List<String> list) { for (int i = COUNT_OBJ; i-- > 0; ) { list.add(new String("" + i)); } } public static void checkInsertionPerformance(List<String> list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.add(rndIndex, "test"); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } public static void checkPerformanceForFinding(List<String> list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.get(rndIndex); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } }