java - 在 ArrayList 或 Map 中添加树/图的 n 个节点的空间复杂度

Question

假设我们有一棵二叉树

class node {
   int data;
   node left;
   node right;
}

现在假设我创建一个 ArrayList<node>并在其中添加所有 n 个节点，它的空间复杂度是常数还是 n ？

我的困惑是，因为 node不是原始数据结构而是对象，它必须使用 CALL BY REFERENCE ，因此它不应该使用额外的空间来更改节点的类实例中的某些数据，从而在 ArrayList<> 中进行更改

此外，我推测 ArrayList<type> abc = xyz; //another arraylist of same type使用 CALL BY REFERENCE因此它使用常量空间，但是 ArrayList<type> abc = new ArrayList<>(xyz)创建一个新实例，因此它应该使用额外的空间。

现在，当我在 ArrayList<node> 中添加类实例时我必须用 new 初始化数组列表关键词，ArrayList<node> abc = new ArrayList<>();在我将实例添加到列表之前。所以它应该使用额外的空间，但由于我们使用的是已经在树中定义的类实例，并且树中的任何更改也会反射(reflect)在列表中，因此它应该使用常量空间。以上哪项是正确的，我哪里错了？

编辑:我知道即使引用也会占用一些空间，但它不会比对象最初占用的实际内存空间少很多吗？

Answer 1

node is not a primitive data structure but an object

Java 中没有对象变量/字段。只有原始变量和引用变量。

it must use CALL BY REFERENCE

Java 只能按值调用。原语按值传递，引用按值传递。

when I am adding class instances in ArrayList

这在 Java 中不受支持。您只能添加引用。

So it should use extra space

只有添加的引用才会使用额外的空间。不复制对象。