java - 为什么从 ArrayList 开头删除元素比从末尾删除元素慢？

Question

有人告诉我

When we create an ArrayList, internally an Array of a specific size (say 50) is created. When the items being added to the list exceeds 50, a new Array of a bigger size (say 100) is created internally, and they items of the original Array are copied to this new Array.

然后有人告诉我

When we remove an item from the end of the list, all that is done internally is decrementing the size of the list internally.But removing an element which is located somewhere at the start of the ArrayList is VERY slow, because it will have to copy all the subsequent items one step back, so it is very slow.

但是，正如第一个引用中暗示的那样，ArrayList 在内部由数组表示，并且一旦分配数组就无法更改数组的大小；你必须创建一个新的数组。

• 这意味着当 ArrayList 末尾的元素被删除时，会生成一个新数组 内部创建，其大小比原始大小小一 array，第一个数组的所有元素都会复制到新数组中。
• 当从 ArrayList 的开头删除一个元素时，会生成一个新的元素 数组是在内部创建的，其大小比 原始数组，第一个数组的所有元素都被复制到 新元素，使得新元素中每个后续元素的索引位置 数组比该元素在数组中的索引位置小 1 上一个/原始数组。

我的概念正确吗？

如果是，那么我不明白为什么从数组列表开头删除元素所需的时间/步骤数会比从数组列表末尾删除元素所需的时间/步骤数慢得多。数组。

请帮我理解。

Answer 1

不，这不正确。仅当数组中没有足够的空间容纳所有元素时才会创建新数组。

包含 4 个元素(a、b、c、d)的 ArrayList 表示如下:

array: [a, b, c, d, null, null, null, null, null, null]
size: 4

从列表中删除最后一个元素会将其内容更改为

array: [a, b, c, null, null, null, null, null, null, null]
size: 3

列表所要做的就是减少大小整数，并将第四个元素设置为 null。

删除第一个元素会将其内容更改为

array: [b, c, null, null, null, null, null, null, null, null]
size: 2

列表必须减小大小，将 a 复制到第一个索引，将 b 复制到第二个索引，将第三个索引设置为 null。这是更多的工作，特别是如果列表更长的话。