插入到ArrayList的中间是否将对象移位或引用？

Question

将元素添加到Java ArrayList的末尾应该花费O(1)时间.但是,向中间添加元素必须将右半部分移动一个以维持顺序.这应该花费O(n)时间(实际上O(n/2)简化为O(n)).

我的问题是:

在原始内存中,这个移位是移动驻留在ArrayList中的对象本身,还是只移动指向它们的引用？

无论它是什么,时间复杂度都是相同的,但开销可能会有所不同.将一堆巨大的物体移到一边为中间的一个腾出空间可能比在内存中移动一些int大小的引用要大得多.

所以:

1. 这是什么？我倾向于猜测它是被移位的引用,因为Java List保存对堆上对象的引用,这些对象可能在内存中的任何"顺序"中.

2. 我对上述所有内容的任何错误？

我问的原因纯粹是理论上的.我只是想知道内存中发生了什么,如果大量的对象被交换,或者它只是被拖拽的引用.谢谢.

(注意:这几乎是我今天早些时候提出的这个问题的后续内容.)

Answer 1

在原始内存中，这种移位是移动驻留在 ArrayList 中的对象本身，还是仅仅移动指向它们的引用？

简而言之，没有移动任何实际对象，只有引用被复制到带有新索引的 arraylist 的内部数组中。

是哪一个？我倾向于猜测是引用发生了移位，因为 Java 列表保存了对堆上对象的引用，这些对象可能在内存中处于任何“顺序”。

Arraylist 在内部使用数组。对象的引用保存在数组中。这些引用指向的对象可以位于内存中的任何位置，不一定按顺序排列。它只是 arraylist 内部数组中的引用，这有助于使用数组索引获取对象。