Why ArrayList Faster than LinkedList during Random Access?
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.

Why LinkedList faster than ArrayList during Insertion/Deletion?
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.

  • LinkedList takes constant-time insertions or removals. I can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.
  • ArrayLists allows random access, so I can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if I add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
  • Iterating over both the Types is equally cheap.
  • If you have large lists, the memory usage is different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored

When should I use LinkedList?

  • When you need efficient removal in between elements or at the start.
  • When you don’t need random access to elements, but can live with iterating over them one by one

When should I use ArrayList?

  • When you need random access to elements (“get the nth. element”)
  • When you don’t need to remove elements from between others. It’s possible but it’s slower since the internal backing-up array needs to be reallocated.
  • Adding elements is amortized constant time (meaning every once in a while, you pay some performance, but overall adding is instantly done)
Operation Linked List Array List
Access O(n) O(1)
Insertion Access time + O(1) Access time + O(n)
Deletion Access time + O(1) Access time + O(n)

Leave a reply