CODEWITHSUNDEEP
javaooparraylistspace-complexity
Bugs Buggy
Bugs Buggy

Reputation: 1546

Space complexity of adding n nodes of a tree / graph in an ArrayList or Map

Suppose we have a binary tree where we have

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

Now suppose I create an ArrayList<node> and add all n nodes in it, will it be in constant space complexity or in n?

My confusion was, since node is not a primitive data structure but an object, it must use CALL BY REFERENCE, hence it should not be using extra space as changing some data in a class instance of node, makes the change in the ArrayList<> as well.

Also, I presumed ArrayList<type> abc = xyz; //another arraylist of same type uses CALL BY REFERENCE hence it uses constant space, but ArrayList<type> abc = new ArrayList<>(xyz) creates a new instance hence it should be using extra space.

Now, when I am adding class instances in ArrayList<node> I do have to initialize the array list with new keyword, ArrayList<node> abc = new ArrayList<>(); before I add instances to the list. So it should use extra space but since we are using class instances which were already defined in the tree and any changes in the tree would reflect on the list as well, hence it should be using constant space. Which of the above is correct and where am I wrong?

EDIT : I understand that even references will take up some space, but would it not be much less than the actual memory space taken by objects originally?

Upvotes: 1

Views: 309

Answers (2)

Leo Aso
Leo Aso

Reputation: 12493

The space complexity will of course be a function of n and not constant. This is because even though the ArrayList only contains references to the tree objects, those references themselves take up space (I'm not a JVM expert so I'm not sure the exact amount, but it's just a few bytes). Of course the space taken up by the reference will be significantly smaller than that taken up by the object itself, but it still takes up space.

EDIT:

To be clear, if you are asking whether the ArrayList takes up less space than the objects themselves, then yes it does, but that is not what space complexity means. Space complexity is not about how much space is required to store data, its about how that space requirement multiplies as the data grows. When I say space complexity is O(n) or linear, I mean that the ArrayList size increases proportionally with the number of objects. Twice as many objects make the ArrayList twice the size, five times as many makes the ArrayList five times as large, and so on. Constant or O(1) complexity means that, even if you might need extra space, the amount of space you need stays the same and does not increase as you add items.

I believe what you are really asking is "Will adding an ArrayList double my space requirements, or will it require no extra space?" and my answer to both is no. It will not double the space requirements, because it only uses references, but it will require some extra space to store those references. That has nothing to do with space complexity.

TLDR: Space requirements ≠ Space complexity.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533670

node is not a primitive data structure but an object

There is no object variables/fields in Java. Only primitive and reference variable.

it must use CALL BY REFERENCE

Java is call by value only. Primitives are passed by value and references are passed by value.

when I am adding class instances in ArrayList

This is not supported in Java. You can only add references.

So it should use extra space

Only the references added use extra space. The objects are not copied.

Upvotes: 2

Related Questions