从ArrayList或LinkedList中删除元素是否更有效?
-
10-07-2019 - |
题
理论上,从ArrayList
或LinkedList
中删除元素是否更有效?
解决方案
<!>更容易<!> (也就是说,更高效)从LinkedList
删除它们,因为从ArrayList
删除需要将所有后续元素移动到列表中的新位置<!>#8212;必须分配数组的所有后续元素一个新的价值。使用链表时,只能重新分配一个指针(或两个带有双向链表的指针)。
其他提示
好吧,从(双重链接)列表中删除元素是O(1)。但是从数组中删除将需要将剩余的元素向下移动到数组中的一个空格,即O(n)。
也就是说,按索引获取列表中的特定元素是O(n),而按索引获取数组中的特定元素是O(1)。
所以,对于实际删除,LinkedList会更好。有关Array的更多信息与LinkedList 此处。
不隶属于 StackOverflow