java - ArrayList 包含对 TreeNode 的引用，空间复杂度是多少？

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空间复杂度应为 O(1)因为它正在保存对堆上单个内存块的引用。我正在和我的 friend 讨论这个问题，他们有不同的看法，认为它可能有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;
}

每当添加一个元素时，它就会添加到支持对象数组中。