Java Vs. C++ / C Tree implementations, what goes on under the hood

Question

So I've been reviewing my data structures and I've never understood how the java implementation of things with pointers ends up actually working when compared to languages which have pointers.

Trees or lists in java classes are implemented with a node class which has other node classes as elements say left and right nodes if it's a tree.

public class Node {
    private int data;
    private Node left;
    private Node right;
    ...
}

Does the compiler know to just use pointers or is all this being done by value and I have many different versions of the same value saved from my tree nodes?

... A reference to an object is just that, a reference to an object. — Dave Newton, Jan 23 '13 at 18:49
In short, the compiler knows to use pointers (and only pointers) for all object types. — Jochen, Jan 23 '13 at 18:49
http://stackoverflow.com/questions/7436581/what-is-the-difference-between-a-pointer-and-a-reference-variable-in-java — Mat, Jan 23 '13 at 18:50
A reference to an object is essentially a pointer that you can only dereference - does not support pointer arithmetic. — ignis, Jan 23 '13 at 18:50

score 3 · Answer 1 · answered Jan 23 '13 at 18:49

3

In Java the Node fields are references. There is no other option so there no special symbol required.

answered Jan 23 '13 at 18:49

Peter Lawrey

525,659
79
751
1,130

score 3 · Answer 2 · answered Jan 23 '13 at 18:52

Although java doesn't explicitly use pointer, it is fully pointer oriented. Without pointer java doesn't work.In java, 'this' pointer is used explicitly to access the data member associate with the object.

They are called "reference types". The references point to objects.Basically. There is no way to "take the address" of a variable. But you can copy the value of the variable into a field of a wrapper object, which then can be pointed to by a reference.

WLin · Accepted Answer · 2013-01-24T00:44:11.123

I find that confusion in this matter generally boils down to not understanding how objects are passed in Java.

With updateNodeData as demonstrated in the code below, you'll be passing a copy of the reference by value as the first argument. That node's data would then be modified (assuming data is public).

Similarly, nodeToBeChanged's leftNode would also now refer to the same node as that passed in newLeftNode. A new Node with copied values isn't cloned/created.

public void updateNodeData(Node node, int newValue){
    node.data = newValue;
}

public void setLeftNode(Node nodeToBeChanged, Node newLeftNode)
{
  nodeToBeChanged.leftNode = newLeftNode;
}

However, what is often confusing is that because it's a copy of the reference that is passed by value, you cannot do a swap of two Nodes as demonstrated below. You'll be swapping the copies and not the actual references.

public void swap(Node node1, Node node2)
{
  Node tmpNode = node1;     
  arg1 = arg2;
  arg2 = tmpNode;
}

Now to come back to the original question. If a Node tree were to be implemented with a Node such as this one:

public class Node {
    private int data;
    private Node left;
    private Node right;
    ...
}

There WILL NOT be different clones of the same Node all over the place wasting memory. It will just be a long chain of nodes and references.

Thanks for the help, this really helped my basic understanding :) As did everyone who commented/contributed thanks !! — Fatlad, Jan 29 '13 at 17:41

Java Vs. C++ / C Tree implementations, what goes on under the hood

3 Answers3