ArrayList содержит ссылки на TreeNodes, какова пространственная сложность?

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), потому что он сохраняет ссылки на отдельный блок памяти в куче. Я обсуждаю это с моими друзьями, и у них есть другое мнение, что это может иметь сложности O(n). Ребята, что вы думаете?

Answer 1

Вы сохраняете ссылки, но они все еще являются n ссылками. Я думаю, что вы действительно ищете накладные расходы памяти для хранения n объектов в ArrayList. В используемой памяти, вероятно, будут доминировать фактические объекты, но есть еще массив с поддержкой длины n, который ArrayList держит ссылки.

Answer 2

ArrayList все еще должен хранить ссылку n раз, делая ее O (n).

ArrayList опирается на Object[], если вы посмотрите на исходный код

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

Всякий раз, когда элемент добавляется он добавляется в массив поддержка объектов.