dimanche 29 mars 2015

Linked List in c add to front



So I'm really confused. I am trying to write a c method that allows me to add a new "node" to the front of a linked list. I have done this before in c++ and no problem. I am getting frustrated because after writing code I was pretty sure was right I went and looked around and basically everywhere I find tells me to do the same thing I am all ready doing...I'll provide code and step by step addresses and values of the variables. Here is the code:


The real function in question is:



void addToBeginning(int value, struct node* root){
struct node* newNode;
newNode = malloc( sizeof(struct node));
newNode->value = value;
newNode->next = root;
root = newNode;
}


But here is the complete code. I removed some things to make it more concise (things that aren't necessary to answer this question like getLength(...) and addToPos(...))



#include <stdio.h>
#include <stdlib.h>

struct node {
int value;
struct node* next;
};

void printLinkedList(struct node* root);

void addToEnd(int value, struct node* root);

void addToBeginning(int value, struct node* root);

void addToPos(int pos, int value, struct node* root);

int getLength(struct node* root);


int main(){
/**
TESTING addToBeginning (I know addToEnd works)
**/

struct node *root2;
root2 = malloc( sizeof(struct node));
root2->value = 4;
root2->next = NULL;

/*
root2 = 4 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0
*/
i = 0;
while (i < 5){
addToEnd(0,root2);
i++;
}

printLinkedList(root2);
//printf("Length : %d\n",getLength(root2));

/*
expected root2 = 2 -> 4 -> 0 -> 0 -> 0 -> 0 -> 0
*/
addToBeginning(2, root2);
printLinkedList(root2);
/*
obtained root2 = 4 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0
*/
//printf("Length : %d\n",getLength(root2));

return(0);
}

void printLinkedList(struct node* root){
while(root != NULL){
if (root->next != NULL){
printf("%d, ",root->value);
root=root->next;
} else {
printf("%d\n",root->value);
root=root->next;
}
}

}

void addToEnd(int value, struct node* root){
/*
Set up new node
*/
struct node* newNode = malloc( sizeof(struct node));
newNode->value = value;
newNode->next = NULL;

/*
Check if empty linked list first
*/
if (root->next == NULL){
root->next = newNode;
} else {
/*
Find the last node
*/
struct node* current = root;
while(current->next != NULL){
current = current->next;
}
current->next = newNode;
}
}

void addToBeginning(int value, struct node* root){
struct node* newNode;
newNode = malloc( sizeof(struct node));
newNode->value = value;
newNode->next = root;
root = newNode;
}


What is so confusing is I feel that there is a problem with aliasing at the



newNode->next = root;
root = newNode;


lines...so I am including the addresses obtained during my debug steps: So...within the addToBeginning(int value, struct node* root){...} function I'm going to go through step by step:


after execution of:



struct node* newNode;
newNode = malloc( sizeof(struct node));


the addresses and values of root and newNode are:



root = 0x0000000100103c60
root->next = 0x0000000100103c70
root->value = 4
newNode = 0x0000000100103cc0
newNode->next = NULL
newNode->value = 0


after execution of:



newNode->value = value;


the addresses and values of root and newNode are:



root = 0x0000000100103c60
root->next = 0x0000000100103c70
root->value = 4
newNode = 0x0000000100103cc0
newNode->next = NULL
newNode->value = 2


after execution of:



newNode->next = root;


the addresses and values of root and newNode are:



root = 0x0000000100103c60
root->next = 0x0000000100103c70
root->value = 4
newNode = 0x0000000100103cc0
newNode->next = 0x0000000100103c60
newNode->value = 2


after execution of:



root = newNode;


the addresses and values of root and newNode are:



root = 0x0000000100103cc0
root->next = 0x0000000100103c60
root->value = 2
newNode = 0x0000000100103cc0
newNode->next = 0x0000000100103c60
newNode->value = 2


I realize that the problem is that *root is passed by reference so what I need to do is change the value of the object stored in the location 0x0000000100103c60 so any suggestions on how to do that would be appreciated.




Aucun commentaire:

Enregistrer un commentaire