Storing strings in a linked list

This is a discussion on Storing strings in a linked list within the C Programming forums, part of the General Programming Boards category; As a side project to learn C, I'm writing a simple equation parser/evaluator. I've already written the exact same program ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    1

    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.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by dws90 View Post
    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.
    This is an unusual thing to do, so suffer the consquences. Since you have to free the malloced contents of a malloced node seperatedly from the node, you could leave it undone so you could keep the string -- if you keep the address of the string, not the node, which you do correctly but long-windedly (might be sub-optimal, you use unnecessary assignments) but it is not clear to me why from your message.

    As to the questions:
    1) Don't overwrite the data. The address only gets passed back to the compiler if you free() it (via some pointer). If you reassign a pointer without freeing the address, the memory is still protected and if you have no pointers to it left, it leaked.
    2) Keep the strings you want, free() the others.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 12:56 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21