Thread: Storing strings in a linked list

As a side project to learn C, I'm writing a simple equation parser/evaluator. I've already written the exact same program in PHP, so it's mainly a question of manually doing all of the stuff that PHP does automatically.

I wrote a basic linked list "class" to function serve as a queue or stack when needed. Basically, I get a string from the user containing the equation, split it up into the individual tokens (still strings), and then dump all of the tokens into a linked list, which is then traversed and evaluated. It isn't until this last step that the data is stored as anything other than a string.

Initially, every time my nextToken(char * putTokenHere...) function was called, it changed all of the strings I'd already put in the list. I realized that I needed to copy the string into another array at some point before putting into the list, and I figured the best way to do that would be to leave nextToken() as it was and do the copy in my create linked list node function.

My first strategy was to declare a char array normally (ie, char * temp = [SIZE]),..use strcpy to copy the value I was inserting into temp, and then have the value pointer of the node point to temp. While that seemed to work inside the function, the value was garbled when accessed afterward (I assume the compiler went and cleaned something up or something...). So, my next strategy was to malloc a string and memcpy the data into that string.

That worked fine, except I think there's a memory leak. My llRemove() function returns a pointer to the value of the removed node, which would be the malloced string, so I can't free it when I free the rest of the node. Right now, if I want to avoid the memory leak, I have to manually free the returned value every time I remove something from the node, which seems incredibly error prone.

Thus, my questions are twofold:
1. What's the best way to store the value of a string in a linked list so that I can reuse the original sting without overwriting the existing data? Where's the best place to perform the copy?
2. If I malloc a string when creating a node, and want to return the value of the string in some form when I remove the node, how do I make sure I don't have a bunch of leaky strings running around?

The code for my linked list constructor:

Code:

NodePtr llConstructListNode(char * value, NodePtr prev, NodePtr next) {
	char * temp = (char *)malloc(sizeof(char[LL_MAX_STRING_LENGTH]));
	memcpy(temp, value, LL_MAX_STRING_LENGTH);
	NodePtr node = (NodePtr)malloc(sizeof(struct ListNode));
	node->value = temp;
	node->prev = prev;
	node->next = next;
	return node;
}

And my remove function...

Code:

char * llRemove(ListPtr list, int pos) {
	if(pos == 0) { 
		return llRemoveFront(list);
	}
	if(pos == list->length - 1) {
		return llRemoveRear(list);
	}

	NodePtr doomed = llGetNode(list, pos);
	doomed->prev->next = doomed->next;
	doomed->next->prev = doomed->prev;
	char * orphanedValue = doomed->value;
	free(doomed);
	list->length--;
	return orphanedValue;
}

Any help would be greatly appreciated. Thanks.