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

Question

ArrayList从理论上讲，从 a或 a中删除元素更有效LinkedList吗？

Answer 1

从 a 中删除它们“更容易”（即更有效）LinkedList，因为从 a 中删除ArrayList需要将所有后续元素移动到列表中的新位置 - 必须为数组的所有后续元素分配一个新值。对于链表，只有一个指针（或两个，对于双向链表）必须重新分配。

Answer 2

好吧，从（双向）列表中删除一个元素是 O(1)。但是从数组中删除需要将剩余元素在数组中向下移动一个空格，即 O(n)。

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

所以，对于实际的移除，LinkedList 会更好。这里有更多关于 Array 与 LinkedList 的信息。

Answer 3

ArrayList在内部使用动态数组来存储元素，因此使用 ArrayList 进行操作很慢，因为它在内部使用数组。

如果从数组中删除任何元素，则所有位都会在内存中移动，而LinkedList在内部使用双向链表来存储元素。

LinkedList 的操作比 ArrayList 快，因为它使用双向链表，因此不需要在内存中进行位移。