saltandwater saltandwater - 5 months ago 9
Java Question

Does Tree implementation in Java hold the entire next Node v/s just holding address in C

Notice how in the C version, only the address of the node, that is, Node* is saved, whereas, in the Java version, the entire Node is saved.

Does this mean that the Java code to run occupies more memory as compared to the C code?

C version

#include <stdio.h>
#include <malloc.h>

typedef struct node
{
int data;
struct node* left;
struct node* right;
}Node;
Node* root;

void inorder(Node* node)
{
if(node == NULL)
return;

inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}

void insert(int data)
{
printf("inside insert, data == %d",data);

Node* node = malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;

if(root == NULL)
{
printf("inserting %d as root",node->data);
root = node;
}
else
{
Node* trav = root;
Node* pretrav = root;
while(trav != NULL)
{
pretrav = trav;
if(node->data < trav->data)
trav = trav->left;
else
trav = trav->right;
}

if(node->data < pretrav->data)
{
printf("inserting %d to the left of %d",node->data, pretrav->data);
pretrav->left = node;
}
else
{
printf("inserting %d to the right of %d",node->data, pretrav->data);
pretrav->right = node;
}
}
}

int main(void)
{
int a[] = {10,5,15,1,20,100};
int i = 0;

for(i = 0;i<sizeof(a)/sizeof(a[0]);i++)
{
insert(a[i]);
printf("\n");
}

inorder(root);

return 0;
}


Java version

package lastcommon;

public class TreeExample {

public static void main(String[] args) {
// TODO Auto-generated method stub

Tree tree = new Tree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(1);
tree.insert(20);
tree.insert(100);

System.out.println("Printing inorder... ");
tree.inorder(tree.root);
}

}

class Node
{
int data;
Node left;
Node right;

public Node() {
// TODO Auto-generated constructor stub
left = right = null;
}
}

class Tree
{
Node root;

public Tree() {
// TODO Auto-generated constructor stub
root = null;
}

void inorder(Node node)
{
if(node == null)
return;

inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}

void preorder(Node node)
{
if(node == null)
return;

System.out.println(node.data);
preorder(node.left);
preorder(node.right);
}

void postorder(Node node)
{
if(node == null)
return;

postorder(node.left);
postorder(node.right);
System.out.println(node.data);
}

void insert(int data)
{
Node node = new Node();
node.data = data;

if(root == null)
{
root = node;
return;
}

Node trav = root;
Node pretrav = root;
while( trav != null )
{
pretrav = trav;
if(node.data < trav.data)
{
trav = trav.left;
}
else
{
trav = trav.right;
}
}

if(node.data < pretrav.data)
pretrav.left = node;
else
pretrav.right = node;
}
}

Answer

Java uses references in very much the same way that C uses pointers. They are related but you cannot manipulate references like you can manipulate pointers, making them safer to use (your program less likely to crash).

A reference is created every time new is invoked. Look inside the insert method and you can see that new Node(...) is called there, creating a new object and returns a reference to the new object.

Whenever you use such a reference in your own code, it is only the "pointer" and not the whole object which is saved in the variable.