从ArrayList或LinkedList中删除元素是否更有效？

Question

从理论上讲,从a ArrayList或a中删除元素是否更有效LinkedList？

Answer 1

从a中删除它们"更容易"(即更有效)LinkedList,因为从a中删除ArrayList需要将所有后续元素移动到列表中的新位置 - 必须为数组的所有后续元素分配新值.使用链表,只能重新分配一个指针(或两个带有双向链表的指针).

Answer 2

好吧,从(双重链接)列表中删除元素是O(1).但是从数组中删除将需要将剩余的元素向下移动到数组中的一个空间,即O(n).

也就是说,通过索引获取列表中的特定元素是O(n),而通过索引获取数组中的特定元素是O(1).

所以,对于实际删除,LinkedList会更好.有对Array的与LinkedList的更多信息这里.