# Thread: Passing linked list by value.

1. ## 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. 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: 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. 3. Originally Posted by laserlight 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. 4. 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). 5. Originally Posted by laserlight 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. Originally Posted by laserlight 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. 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. 7. Originally Posted by laserlight 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. 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. 9. Originally Posted by laserlight 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. 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. 11. 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;
} else {
node variable1, variable2, x1, x2, tempNode = NULL;
resultList results = {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 == '\n') {
i--;
continue;
}
list[i] = readFile(line);
if (list[i] == NULL) {
i--;
}
numOfLists = i;
}
results = 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. 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 == '\n') {
i--;
continue;
}
list[i] = readFile(line);
if (list[i] == NULL) {
i--;
}
numOfLists = i;
}
results = 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 == '\n') {
i--;
continue;
}
list[i] = readFile(line);
if (list[i] == NULL) {
i--;
}
numOfLists = i;
}
results = 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? 13. Originally Posted by laserlight 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. Originally Posted by laserlight 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 == '\n') {
i--;
continue;
}
list[i] = readFile(line);
if (list[i] == NULL) {
i--;
}
numOfLists = i;
}
results = 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 == '\n') {
i--;
continue;
}
list[i] = readFile(line);
if (list[i] == NULL) {
i--;
}
numOfLists = i;
}
results = 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. Originally Posted by laserlight 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. 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? 15. Originally Posted by laserlight 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, y. Originally Posted by laserlight 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` Popular pages Recent additions #### Tags for this Thread

data, functions, linked, list, struct 