Thread: Passing linked list by value.

  1. #1
    Registered User
    Join Date
    Apr 2020
    Posts
    30

    Passing linked list by value.

    Hi,

    I have created a code that adds/multiplies/subtracts a file of polynomials. I have used doubly linked list (as required in the project), it works correctly as well as all functions. I'm facing a problem that I face data loss during passing the linked list to add/sub/multiply functions because in these functions I delete added values from equations to the linked list. I know that I can deeply copy the data of the linked list but it will make a big time complexity. So is there any way to pass the linked list by value?

    Here is how I defined the list.
    Code:
    typedef struct node {    double coefficient, power;
        struct node *Previous, *Next;
    } *equationList;
    NOTE: I can not show my all code since it's a project and some students will copy it.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If the linked list is represented by a pointer to the head node only, then pass a pointer to that head node. You may need to return a pointer to the resulting head node, or pass a pointer to a pointer to the head node if the operations are such that the head node itself might be changed (and not only its value).

    If the linked list is represented by a struct that contains both the head node, tail node, and possibly other data, then pass a pointer to that linked list struct object.

    In your case, it looks like the former is what you want to do.

    EDIT:
    Oh, I may have misread your question:
    Quote Originally Posted by amohammed63
    I'm facing a problem that I face data loss during passing the linked list to add/sub/multiply functions because in these functions I delete added values from equations to the linked list. I know that I can deeply copy the data of the linked list but it will make a big time complexity. So is there any way to pass the linked list by value?
    In retrospect, it sounds like you want copy by value semantics. If so, then deep copy is the way to go. Yes, you'll have to deal with the time complexity, but you have no choice: the time complexity is inherent in what you want to do. If an automatic copying by value were available, it would result in the same time complexity, merely hidden from you.
    Last edited by laserlight; 04-06-2021 at 05:30 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    If the linked list is represented by a pointer to the head node only, then pass a pointer to that head node. You may need to return a pointer to the resulting head node, or pass a pointer to a pointer to the head node if the operations are such that the head node itself might be changed (and not only its value).

    If the linked list is represented by a struct that contains both the head node, tail node, and possibly other data, then pass a pointer to that linked list struct object.

    In your case, it looks like the former is what you want to do.

    EDIT:
    Oh, I may have misread your question:

    In retrospect, it sounds like you want copy by value semantics. If so, then deep copy is the way to go. Yes, you'll have to deal with the time complexity, but you have no choice: the time complexity is inherent in what you want to do. If an automatic copying by value were available, it would result in the same time complexity, merely hidden from you.
    Firstly, I'm doing my best to skip deep copying. In my code, I have an array of linked lists that is passed to the addition function for example, I tried many ways to send it by value it and I failed.
    I was wrote a code in order to try to pass the linked list by value, and here is the code:
    Code:
    struct node {    double coefficient, power;
        struct node *Previous, *Next;
    };
    void test (struct node *L){
        struct node* temp = L;
    temp->coefficient =555;
    }
    int main() {
        struct node *L = (struct node *)malloc(sizeof(struct node*));
    L->Next = NULL;
    L->coefficient = 50;
    test(L);
    }
    But even though it's passed by reference, I tried many ways but I'm getting many errors or warnings or the code doesn't response.
    Last edited by amohammed63; 04-07-2021 at 01:16 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    This is wrong:
    Code:
    struct node *L = (struct node *)malloc(sizeof(struct node*));
    It should be:
    Code:
    struct node *L = malloc(sizeof(*L));
    That is, you were allocating space for a pointer when you want to allocate space for a node.

    Anyway, the code doesn't "pass a linked list by value". What it does is pass a pointer to a node by value, which means that it effectively passes the node by reference (but of course the actual parameter passing mechanism is still call by value).
    Last edited by laserlight; 04-07-2021 at 01:34 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    It should be:
    Code:
    struct node *L = malloc(sizeof(*L));
    That is, you were allocating space for a pointer when you want to allocate space for a node.
    I have tried this, but also it changes the list in created in the main.

    Quote Originally Posted by laserlight View Post
    Anyway, the code doesn't "pass a linked list by value". What it does is pass a pointer to a node by value, which means that it effectively passes the node by reference (but of course the actual parameter passing mechanism is still call by value).
    I know that but I really don't know how to deal with it since my data are lost during the pass between functions. I'm also lost.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by amohammed63
    I have tried this, but also it changes the list in created in the main.
    So, you want to pass the linked list to a function and modify it while keeping it unmodified in the caller. This means that you must make a copy of the linked list so that you can modify the copy, i.e., you need to do deep copying.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    So, you want to pass the linked list to a function and modify it while keeping it unmodified in the caller. This means that you must make a copy of the linked list so that you can modify the copy, i.e., you need to do deep copying.
    I have three functions calls, is not hard to copy the linked list three times?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by amohammed63
    I have three functions calls, is not hard to copy the linked list three times?
    Maybe, maybe not. It depends on your requirements. For example, suppose that you want to operate on a linked list, thereby changing it, but you also want to retain the original state of the linked list. This would suggest that your functions should change the linked list without making a copy. Rather, you do the copying once: in the main function before you call the other functions.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    Maybe, maybe not. It depends on your requirements. For example, suppose that you want to operate on a linked list, thereby changing it, but you also want to retain the original state of the linked list. This would suggest that your functions should change the linked list without making a copy. Rather, you do the copying once: in the main function before you call the other functions.
    Can I show you few parts of my code and decide with me if I can change something in it or go to copying function?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Sure, but you'll have to post the code here.

    I don't see what's so difficult though. You already have an idea of how identify whether you need to copy, i.e., ask yourself if you need the original state after calling a function that changes the state of the linked list.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Code:
    typedef struct node {    double coefficient, power;
        struct node *Previous, *Next;
    } *equationList;
    
    typedef equationList node;
    typedef equationList resultList;
    
    
    
    void insert(equationList list, node *P, double power, double coefficient) {
        node temp = NULL;
    temp = MakeEmpty(temp);
    node te = NULL;
        if (list->Next == NULL) {
            list->Next = temp;
    temp->Previous = list;
    temp->power = power;
    temp->coefficient = coefficient;
    *P = temp;
    } else {
            te = *P;
    te->Next = temp;
    temp->Previous = te;
    temp->power = power;
    temp->coefficient = coefficient;
    temp->Next = NULL;
    *P = temp;
    }
    
    
    node find(double X, equationList equation2) {
        node P = equation2, temp = P;
        while (P != NULL) {
            if (P->power == X) {
                temp = P;
                break;
    }
            P = P->Next;
    temp = NULL;
    }
        P = temp;
        return P;
    }
    
    
    resultList addition(equationList equation[], int numOfEquations) {
        if (numOfEquations == 1) {
            return equation[0];
    } else {
            node variable1, variable2, x1, x2, tempNode = NULL;
    resultList results[9999] = {0};
            int numOfResults = 0;
    tempNode = MakeEmpty(tempNode);
            for (int i = 0; i < numOfEquations; i += 2, numOfResults++) {
                if (i == numOfEquations - 1) {
                    results[numOfResults] = equation[i];
                    continue;
    }
                results[numOfResults] = MakeEmpty(results[numOfResults]);
    variable1 = equation[i]->Next;
    variable2 = equation[i + 1]->Next;
    variable1->Previous = NULL, variable2->Previous = NULL;
                while (variable1 != NULL || variable2 != NULL) {
                    if (variable1 != NULL)
                        x1 = find(variable1->power, variable2);
                    if (variable2 != NULL)
                        x2 = find(variable2->power, variable1);
                    else
    x2 = NULL;
                    if (x1 == NULL && x2 == NULL) {
                        if (variable1 != NULL) {
                            insert(results[numOfResults], &tempNode, variable1->power, variable1->coefficient);
    }
                        if (variable2 != NULL) {
                            insert(results[numOfResults], &tempNode, variable2->power, variable2->coefficient);
    }
                        variable1 = delete(variable1, variable1);
    variable2 = delete(variable2, variable2);
                        continue;
    }
                }
    
            }
            return addition(results, numOfResults);
    }
    }
    
    
    int main(){for (int i = 0; !feof(inFile); i++) {
        fgets(line, 50, inFile);
        if (line[0] == '\n') {
            i--;
            continue;
    }
        list[i] = readFile(line);
        if (list[i] == NULL) {
            i--;
    }
        numOfLists = i;
    }
    results[0] = addition(list, numOfLists + 1);}
    Here's a part of it, in addition I'm searching for equivalent exponent, once it's found both are deleted from the list, maybe this cases the data loss but I have no other way.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The first thing that I suggest is for you to get rid of those typedefs, i.e., this:
    Code:
    typedef struct node {    double coefficient, power;
        struct node *Previous, *Next;
    } *equationList;
    
    typedef equationList node;
    typedef equationList resultList;
    Really should just be this:
    Code:
    typedef struct node {
        double coefficient, power;
        struct node *Previous, *Next;
    } node;
    The reason is that when you typedef a non-opaque pointer type, you effectively hide the fact that it is a pointer type, and yet you will use objects of that type as pointers, with pointer notation. This can make it harder to reason about your program, e.g., it looks like a function returns a node object when it actually returns a pointer to a node.

    You will find real world examples where pointer typedefs are used, but in such cases they are typically opaque pointers, i.e., they serve as handles to resources that you access and control purely through a library interface of functions. You usually do not directly use pointer notation with them, so while they are pointers, the fact that they are pointers is incidental to how they are used, whereas in your program the fact that they are pointers is essential to how they are used.

    Related to this, I suggest that instead of using list as a parameter name, use head. The reason is that while you are dealing with a linked list, you are dealing with it through a pointer to its head node rather than through a linked list object. So it becomes clear what you mean when you write head->Next, whereas list->Next makes it sound as if you're accessing the next linked list rather than the next node after the head node of the linked list.

    Another thing you need to do is to indent your code properly. For example, this is a mess:
    Code:
    int main(){for (int i = 0; !feof(inFile); i++) {
        fgets(line, 50, inFile);
        if (line[0] == '\n') {
            i--;
            continue;
    }
        list[i] = readFile(line);
        if (list[i] == NULL) {
            i--;
    }
        numOfLists = i;
    }
    results[0] = addition(list, numOfLists + 1);}
    Properly indented, it should look something like this:
    Code:
    int main() {
        for (int i = 0; !feof(inFile); i++) {
            fgets(line, 50, inFile);
            if (line[0] == '\n') {
                i--;
                continue;
            }
            list[i] = readFile(line);
            if (list[i] == NULL) {
                i--;
            }
            numOfLists = i;
        }
        results[0] = addition(list, numOfLists + 1);
    }
    Now, it is easy to see the structure of the code, i.e., that you have those if statements within a for loop, and where those control structures begin and end. I presume that in your actual code you have declared those variables to be local variables that you omitted for brevity; if they are global variables then you should make them local.

    Also, you should not use feof to control the loop in this way. Rather, make use of the return value of fgets.

    As for your question about whether to copy or not: your abbreviated code doesn't really help, methinks. You need to explain it because you've omitted so much that it is not clear what is going on, e.g., it looks like you only call addition once, and you don't make use of any original state, so why do you need to copy?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    The first thing that I suggest is for you to get rid of those typedefs, i.e., this:
    Code:
    typedef struct node {    double coefficient, power;
        struct node *Previous, *Next;
    } *equationList;
    
    typedef equationList node;
    typedef equationList resultList;
    Really should just be this:
    Code:
    typedef struct node {
        double coefficient, power;
        struct node *Previous, *Next;
    } node;
    The reason is that when you typedef a non-opaque pointer type, you effectively hide the fact that it is a pointer type, and yet you will use objects of that type as pointers, with pointer notation. This can make it harder to reason about your program, e.g., it looks like a function returns a node object when it actually returns a pointer to a node.

    You will find real world examples where pointer typedefs are used, but in such cases they are typically opaque pointers, i.e., they serve as handles to resources that you access and control purely through a library interface of functions. You usually do not directly use pointer notation with them, so while they are pointers, the fact that they are pointers is incidental to how they are used, whereas in your program the fact that they are pointers is essential to how they are used.

    Related to this, I suggest that instead of using list as a parameter name, use head. The reason is that while you are dealing with a linked list, you are dealing with it through a pointer to its head node rather than through a linked list object. So it becomes clear what you mean when you write head->Next, whereas list->Next makes it sound as if you're accessing the next linked list rather than the next node after the head node of the linked list.
    First of all, thank you for helping and guiding. I'll change all variables and lists with proper name. My aim was only to run the code firstly.


    Quote Originally Posted by laserlight View Post
    Another thing you need to do is to indent your code properly. For example, this is a mess:
    Code:
    int main(){for (int i = 0; !feof(inFile); i++) {
        fgets(line, 50, inFile);
        if (line[0] == '\n') {
            i--;
            continue;
    }
        list[i] = readFile(line);
        if (list[i] == NULL) {
            i--;
    }
        numOfLists = i;
    }
    results[0] = addition(list, numOfLists + 1);}
    Properly indented, it should look something like this:
    Code:
    int main() {
        for (int i = 0; !feof(inFile); i++) {
            fgets(line, 50, inFile);
            if (line[0] == '\n') {
                i--;
                continue;
            }
            list[i] = readFile(line);
            if (list[i] == NULL) {
                i--;
            }
            numOfLists = i;
        }
        results[0] = addition(list, numOfLists + 1);
    }
    The code is well arranged but when I copied it I deleted many segments so that's why it looks like that and it is not documented yet.


    Quote Originally Posted by laserlight View Post
    Now, it is easy to see the structure of the code, i.e., that you have those if statements within a for loop, and where those control structures begin and end. I presume that in your actual code you have declared those variables to be local variables that you omitted for brevity; if they are global variables then you should make them local.

    Also, you should not use feof to control the loop in this way. Rather, make use of the return value of fgets.

    As for your question about whether to copy or not: your abbreviated code doesn't really help, methinks. You need to explain it because you've omitted so much that it is not clear what is going on, e.g., it looks like you only call addition once, and you don't make use of any original state, so why do you need to copy?
    I'll change it to fgets once I'm finished with the whole code.
    According to last part, I show you here a small segment of the code, my code performs addition, subtraction and multiplication on the array of linked list which I forgot to mention in the code. When I perform addition, the result is correct. Once I perform multiplication after addition, the output is wrong. I was following the linked list data using debugger I noticed that some of the data are lost. And, in addition I'm using variable1 and variable2 which are pointers to the original equations, and I'm stuck in that point and I don't know how to skip it.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by amohammed63
    When I perform addition, the result is correct. Once I perform multiplication after addition, the output is wrong.
    Great, that's good information to work with. Let's simplify and imagine that you're dealing with this number type:
    Code:
    typedef struct number
    {
        int value;
    } number;
    
    number *add(number *x, number *y);
    number *multiply(number *x, number *y);
    How would you implement the add and multiply functions? Show the code.

    Next, perform multiplication after addition in the same way as you tested with your original code. Show the code. Is the output wrong?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    Quote Originally Posted by laserlight View Post
    Great, that's good information to work with. Let's simplify and imagine that you're dealing with this number type:
    Code:
    typedef struct number
    {
        int value;
    } number;
    
    number *add(number *x, number *y);
    number *multiply(number *x, number *y);
    How would you implement the add and multiply functions? Show the code.
    Code:
    typedef struct number {    int value;
    } number;
    
    number *add(number *x, number *y);
    
    number *multiply(number *x, number *y);
    
    int main() {
        number x, y;
    x.value = 50;
    y.value = 60;
    number *t = malloc(sizeof (*t));
    t = add(&x, &y);
        return 0;
    }
    
    number *add(number *x, number *y) {
        (*x).value = 55;//to check if the data is changed or not
    number *t = malloc(sizeof (*t));
    (*t).value = (*x).value + (*y).value;
        return t;
    }
    Here how I can implement it, I know it's wrong but that's how can I do it all. Also, in my case, i have for example number x[50], y[50].

    Quote Originally Posted by laserlight View Post

    Next, perform multiplication after addition in the same way as you tested with your original code. Show the code. Is the output wrong?
    Yeah, the data is affected even though after performing multiplication firstly. Also, the output of multiplication in this case is correct, but the output of addition is not.

    Code:
    HIDDEN BECAUSE IT IS PROJECT
    Last edited by amohammed63; 04-07-2021 at 04:41 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 08-08-2014, 02:52 PM
  2. passing 3D array to a linked list.
    By satty in forum C Programming
    Replies: 8
    Last Post: 08-21-2010, 09:36 AM
  3. Passing a linked list to a function
    By esmeco in forum C Programming
    Replies: 6
    Last Post: 06-09-2010, 01:58 AM
  4. Passing an array to linked list
    By bar338 in forum C Programming
    Replies: 7
    Last Post: 04-08-2009, 09:15 PM
  5. Passing an array to a linked list
    By henry_kay in forum C Programming
    Replies: 7
    Last Post: 10-04-2007, 02:21 AM

Tags for this Thread