相关疑难解决方法(0)

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

我的问题是:

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

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

所以:

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

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

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

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

在我的Data Structures类中,我们研究了Java ArrayList类,以及当用户添加更多元素时它如何增长底层数组.这是理解的.但是,当从列表中删除大量元素时,我无法弄清楚这个类究竟是如何释放内存的.查看源代码,有三种方法可以删除元素:

public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = (E) elementData[index];

 int numMoved = size - index - 1;
 if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
 elementData[--size] = null; // Let gc do its work

 return oldValue;
}

public boolean remove(Object o) {
 if (o == null) {
            for (int index = 0; index < size; index++)
  if (elementData[index] == null) {
      fastRemove(index);
      return true;
  }
 } else {
     for (int index = 0; …