Is it more efficient to remove elements from an ArrayList or a LinkedList?

Question

In theory, is it more efficient to remove elements from an ArrayList or a LinkedList?

Answer 1

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.

Answer 2

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.