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?

This should really be reworded. Something like "Is it more efficient to remove elements from an ArrayList or LinkedList?" Theory has little to do with it, and 'easier' is just misleading. — AgileJon, Jun 23 '09 at 21:23
Johanna, please define what you mean by "easier". Easier for the programmer or more efficient for the CPU? — Steve Kuo, Jun 23 '09 at 22:18

score 10 · Accepted Answer · answered Jun 23 '09 at 20:54

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.

score 5 · Answer 2 · edited May 23 '17 at 12:04

5

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.

edited May 23 '17 at 12:04

Community

1
1

answered Jun 23 '09 at 20:57

GManNickG

494,350
52
494
543

Please note that `linkedList.remove(100)` is O(n). – sulai Mar 08 '13 at 13:57

score 2 · Answer 3 · answered Oct 12 '19 at 09:21

ArrayList internally uses a dynamic array to store the elements so manipulation with ArrayList is slow because it internally uses an array.

If any element is removed from the array, all the bits are shifted in memory while LinkedList internally uses a doubly linked list to store the elements.

Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.

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

3 Answers3