Is it more efficient to remove elements from an ArrayList or a LinkedList?
-
10-07-2019 - |
Question
In theory, is it more efficient to remove elements from an ArrayList
or a LinkedList
?
Solution
It is "easier" (that is, more efficient) to remove them from a LinkedList
, because removal from an ArrayList
requires moving all subsequent elements to a new position in the list—all subsequent elements of the array must be assigned a new value. With a linked list, only one pointer (or two, with a doubly-linked list) must be re-assigned.
OTHER TIPS
Well, removal of an element from a (doubly-linked-)list is O(1). But removal from an array will require that the remaining elements are shifted down one space in the array, which is O(n).
That said, getting a specific element in a list by index is O(n), while getting a specific element in an array by index is O(1).
So, the for actual removal, LinkedList will be better. There is more info on Array's versus LinkedList here.