Thread: Memory Allocation for self made Linked List

Hello,
I am a student in a data structures programming class. Our current assignment is to create a linked list in C. I have written and rewritten the code many times and each time I recieve the same series of errors.

In my add function, that adds a node to the list, I allocate memory using malloc but in the end every value stored in the list contains the same value.

Ex:I enter, Red, Is, House (Insert at front of list, should print House is Red. My print statement says.
There are three list values: House House House (Instead of House is Red).

Another problem is after my print function, all the values of the list are empty. I don't assign anything so I'm not sure what is happening.

Any help would be appreciated. I've been beating my head against this for the past two days. I've arranged the code in a way that should be easier to read, the order is correct in my program though.

Code:

int main(void){
	List *list = NULL;
	listNode *newNode;
	
	list = (List *)malloc( sizeof(List) );
	newNode = (listNode *)malloc( sizeof(listNode) );	
	
	listInitialize(list);
	
	testAdd(list);
	printf("Values are %s , %s , %s \n",list->head->data.str,list->head->next->data.str,list->head->next->next->data.str);
	print(list);
	printf("Values are %s , %s , %s \n",list->head->data.str,list->head->next->data.str,list->head->next->next->data.str);
}

typedef struct {
	//int len;
	char *str;
} String;

typedef struct listNode {
	String data;
	struct listNode *next;
} listNode;

typedef struct list {
	listNode *head;
	int length;
} List;

void add(List *list, String Item){
				
		int i = 0;
		
		listNode *NewNode;
		NewNode = (listNode *)malloc( sizeof(listNode) );
	
		NewNode->data.str = (char *)malloc( sizeof(char[50]));
		
		char newPrompt[50] = "\nPlease Enter Value: ";
		promptUser(newPrompt);
		Item.str = newPrompt;	
		NewNode->data = Item;
		
		insertFirst(list, NewNode);
		printf("Value in add is: %s\n",list->head->data.str);
}

void print(List *list) {

	listNode *temp = list->head;
	//printf("There are %d numbers in the list!\n", list->length);

	while( temp ) {
		printf("%s ", temp->data.str);
		temp = temp->next;
	}
	printf("\n");
}
void testAdd(List *list){
	
	String temp1,temp2,temp3;
	temp1.str = (char *)malloc( sizeof(char) * 50);
	temp2.str = (char *)malloc( sizeof(char) * 50);
	temp3.str = (char *)malloc( sizeof(char) * 50);
		
	add(list, temp1);
	printf("Value in main is %s\n",list->head->data.str);
	add(list, temp2);
	printf("Value in main of head is %s\n",list->head->data.str);
	printf("Value in main of head->next is %s\n",list->head->next->data.str);
	add(list, temp3);
	printf("Value in main of head is %s\n",list->head->data.str);
	printf("Value in main of head->next is %s\n",list->head->next->data.str);

}

I'm sorry there is so much code, I'm so lost as to what is causing the problem. The output from running this program would present an user input, then state what it is inside of the add function, then the value in the main function. It would then proceed to do the same twice more, but this time also show the value of the second node(which is always the same as the first )

listInitialize sets head to null. And String is defined that way because my teacher is making us do it that way. Thank you soo much for your time anyone who can help!

The following isn't code, it is a sample output from a test I ran.

Code:

Please Enter Value:  : One      // This is what I entered: One
Value in add is: One
Value in main is One


Please Enter Value:  : Two     // This is what I entered: Two
Value in add is: Two
Value in main of head is Two
Value in main of head->next is Two


Please Enter Value:  : Three     // This is what I entered: Three
Value in add is: Three
Value in main of head is Three
Value in main of head->next is Three
Values are Three , Three , Three
Three Three Three
Values are  ,  ,                        // The values here are all blank and I'm speachless

Thanks again!

You seem to be using a C++ compiler to compile C code.
> you cast malloc a lot
> you have mixed declarations and statements - char newPrompt[50] = "\nPlease Enter Value: ";

> listInitialize(list);
Where's the code?

> testAdd(list);
The most likely problem is that you append your list to a copy of this pointer, so when the function returns, all your work is lost.

Anything which potentially modifies the list should really be written as
testAdd(&list);
or
list = testAdd(list);

> Item.str = newPrompt;
You're assigning a pointer to a local variable.
When this function returns, your pointer is meaningless.
Use memory allocation and strcpy to make an actual copy of the string.

I wanted to thank you for your reply. It appears the immediate problem was the strcpy problem. I would never have found thank, Thank you!

In regards to your other comments,

You seem to be using a C++ compiler to compile C code.
> you cast malloc a lot
> you have mixed declarations and statements - char newPrompt[50] = "\nPlease Enter Value: ";

I use gcc to compile my code, is something wrong with that? I program on linux, and that was simply what they showed us in class. I do cast malloc alot, and I'll try to restructure that now that I know how to keep my values inside of the add function.

Because my teacher makes us use the definition she provides for String, I found if the string wasn't limited to 50 places, one I put something in it that had a limitation.. I would get errors 50% of the time. But that may also be because I was incorrectly copying the string.

Anything which potentially modifies the list should really be written as
testAdd(&list);

Is it possible to pass a pointer like that? My lists are constructed like so:
List *List;
Would I later be able to pass the list with the &List?

Again, thanks a ton for your help!

> I use gcc to compile my code, is something wrong with that?
Sounds good to me - but beware that without extra options, it defaults into 'extended C' mode (lots of GNU-ism's).
gcc -W -Wall -ansi -pedantic -O2 prog.c
Should make sure your code is pretty close to being ANSI-C.

> I found if the string wasn't limited to 50 places,
There is nothing inherently limiting about the string provided. So long as you're accurate in allocating the right amount of memory, then the length doesn't matter.
NewNode->data.str = malloc( strlen(someString) + 1 );
strcpy( NewNode->data.str, someString );

I've been working further on my list and I've come across another problem I can't seem to figure out. I've introduced a reverse list and a delete list function.

My problem is I can't run reverse twice, ex
:
When I enter, Three, Two, One... all being placed at the first of the list. It prints as follows
Three>Two>One with Three being the head of my list. Which is correct

After reverse I get
One>Two>Three which is correct. Operations such as add, delete, find still work with no problem. If I attempt to reverse the list again I recieve a segmentation fault. I'm very confused.

I made a test function that simply assigned values to see what was happening. First I went through a loop and assigned every node to a temp node. No problems. I tried writing to nodes that were already in place. No problems.

I believe the problem lies in the delete function not the reverse. If the delete line is commented out I have no problems. I look at the logic of my freeList function and it makes sense to me, and matches an online code snipet.

Code:

void freeList(listNode *head) {
	listNode *temp;

    while (head != NULL) {
      free(head->data.str);     /* Don't forget to free memory within the list! */
      temp = head->next;
      free(head);
      head = temp;
    }
}

The usage would be, I create a new list to reverse the first. Then delete the first, which should just delete the nodes inside List, then change the pointer of head to the new lists head. Any ideas? Thanks for your time!

> free(head->data.str);
Are you calling malloc for ALL your strings, or do you still have one of these?

> Item.str = newPrompt;

You can only free what you malloced.


Also, for debugging, I would upgrade the print() function to do this
printf("%p: %p %s ", (void*)temp, (void*)temp->next, temp->data.str);
To get maximal information out.
Use it as a way of debugging your code