包含对 TreeNode 的引用的 ArrayList，space 复杂度是多少？

Question

   TreeNode root = new TreeNode(5);
    ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
    for(int i = 0; i < n; i++){
        arr.add(root);
    }

在上面的代码中，单个 TreeNode 对象被添加到 ArrayList<TreeNode> arr 中 n 次。我认为 arr 的 space 复杂度应该是 O(1)，因为它在堆上保存对单个内存块的引用。我正在和我的朋友讨论这个问题，他们有不同的看法，认为它可能具有 O(n) 的复杂性。大家怎么看？

Answer 1

ArrayList还需要存储n次引用，复杂度为O(n)。

ArrayList 由 Object[] 支持，如果您查看源代码

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

每当添加元素时，它都会添加到后备对象数组中。

Answer 2

您正在保存引用，但它们仍然是 n 个引用。我认为您实际上是在寻找将 n 个对象存储在 ArrayList 中的内存开销。使用的内存可能主要由实际对象支配，但仍然有一个长度为 n 的数组支持 ArrayList 保存引用。

包含对 TreeNode 的引用的 ArrayList，space 复杂度是多少？

ArrayList containing references to TreeNodes, what is the space complexity?

java

object

arraylist

space-complexity