Menu
Yes, this is an old topic, but I still have some confusions.
In Java, people say:
ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?
LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated. A 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 insertion mean here? If it means to move some elements back and then put the element in the middle empty spot, ArrayList should be slower than LinkedList. If insertion only means an add(Object) operation, how could this be slow?
411
ArrayList is faster in storing and accessing data. LinkedList is faster in manipulation of data.
Iterating through continuous memory location is more performance efficient than random memory location, that is why we prefer ArrayList over LinkedList when searching by value.
1) ArrayList internally uses a dynamic array to store the elements. LinkedList internally uses a doubly linked list to store the elements. 2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the other elements are shifted in memory.
For ArrayList , insertion is O(1) only if added at the end. In all other cases (adding at the beginning or in the middle), complexity is O(N), because the right-hand portion of the array needs to be copied and shifted. The complexity of a LinkedList will be O(1) both for insertion at the beginning and at the end.
ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?
ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.
LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.
ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.
If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.
Yes, this is what it means. ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array. This involves moving some references around and in the worst case reallocating the entire array. LinkedList just has to manipulate some references.
108
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
