Linked list pointer issue

Question

There are 2 createList functions, one prints out all the elements of the linked list whereas other doesnt why so?

/*following createList prints out fine */
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else root->next = createList(root->next , a);

    return root;
}

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

void read(node* root){
    if(root==NULL) return;
    else{
        cout << root->data << " ";
        read(root->next);
    }
}

Vlad from Moscow · Accepted Answer · 2020-02-13 09:54:37Z

2

In this function

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

its parameter root is a local variable of the function that holds a copy of the value of the argument passed to the function. So changing the copy does not influence on the original argument.

Opposite to the above function in this function

/*following createList prints out fine */
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else root->next = createList(root->next , a);
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return root;
}

there is an assignment of the original argument with the new value.

To make it more clear consider a very simple program

#include <iostream>

int f( int x )
{
    x *= 10;

    return x;
}

int main() 
{
    int x = 10;

    std::cout << "Before call of f: " << x << '\n';

    f( x );

    std::cout << "After  call of f: " << x << '\n';

    x = f( x );

    std::cout << "After  call of f: " << x << '\n';

    return 0;
}

Its output is

Before call of f: 10
After  call of f: 10
After  call of f: 100

After the first call of the function f the variable x in main was not changed because the function deals with a copy of its argument.

After the second call of the function the variable x was changed because it was reassigned by the new value.

edited Feb 13, 2020 at 9:54

answered Feb 13, 2020 at 9:46

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vlad from Moscow Over a year ago

@SayanDas I have not understood the question. What is unclear with this function? The data member data is processed by reference through a pointer root->data and the variable sum is also a pointer so it updates the pointed object.

Sayan Das Over a year ago

in that case how come the following code works void transformTreeUtil(struct Node *root, int *sum) { // Base case if (root == NULL) return; // Recur for right subtree transformTreeUtil(root->right, sum); // Update sum *sum = *sum + root->data; // Store old sum in current node root->data = *sum - root->data; // Recur for left subtree transformTreeUtil(root->left, sum); } you can refer to this link geeksforgeeks.org/transform-bst-sum-tree

Odysseus · Accepted Answer · 2020-02-13 10:35:06Z

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

This actually creates a new node but misses the linking between the former last node and the new node.

So this is effectively the same as:

node *n1 = new node(42);
node *n2 = new node(43);

There is no connection between n1 and n2 which you need to create with:

n1->next = n2;

This is done in the working version of your function by assigning root->next to the return value of the next call.

Also I would really avoid a recursive function for appending a node to your list - Calling your function with a huge list might end up in stack overflow

Landstalker · Accepted Answer · 2020-02-13 10:41:31Z

0

Your problem can be simulated by this example (int instead of node to simplify):

void createList (int *node)
{
    node = new int (2);
}

int main()
{
    int *root= new int (5);
    createList (root);

    return 0;
}

Although there is a call by address in funtion createList but the value of root remains unchanged (5). and that's exactly what happens to you with:

createList(root->next , a);

PS : ignore the problems of memory leaks ...

edited Feb 13, 2020 at 10:41

answered Feb 13, 2020 at 10:34

Landstalker

1,3688 silver badges9 bronze badges

Collectives™ on Stack Overflow

Linked list pointer issue

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related