java - 插入到 ArrayList 的中间是移动对象还是引用？

Question

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

我的问题是:

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

无论是哪种，时间复杂度都是一样的，但开销可能大不相同。将一堆巨大的对象移到一边以为中间的一个对象腾出空间可能比仅在内存中移动一些 int 大小的引用要大得多。

所以:

1. 它是哪个？我倾向于猜测是引用被移动了，因为 Java List 保存对堆上对象的引用，这些对象在内存中可能处于任何“顺序”。

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

我问的原因纯粹是理论上的。我只想知道内存中发生了什么，是否正在交换大量对象，或者是否只是正在改组的引用。谢谢。

(注意:这几乎是我今天早些时候问过的 this question 的跟进。)

Answer 1

In the raw memory, does this shift move the objects themselves which reside in the ArrayList, or merely the references that point to them?

简短的回答没有真正的对象被移动，只有引用被复制到带有新索引的 arraylist 的内部数组中。

Which is it? I'm inclined to guess it's the references which are shifted, as a Java List holds references to objects on the heap which may be in any "order" in memory.

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