Having a hard time with linked lists.

This is a discussion on Having a hard time with linked lists. within the C Programming forums, part of the General Programming Boards category; I am new to C and I am having a hard time with linked lists (preferred Java lists much more). ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    15

    Having a hard time with linked lists.

    I am new to C and I am having a hard time with linked lists (preferred Java lists much more).

    Anyway, this function is supposed to insert a string into the linked list if it doesnt already exist. If the string does exist in the list, increase the value by 1.

    When I run my code, I insert aaa 2 times and print the list to get...
    STRING VALUE
    aaa 2

    But inserting aaa 2 times and bbb once gives...
    STRING VALUE
    bbb 3

    I have spent an hour just rearranging code and trying different things but I am having a hard time. I got a lot of the function from my textbook.

    Code:
    int insertIt(char* string, ListNodePtr *sPtr){
    	ListNodePtr newPtr;     /*pointer to new node*/
    	ListNodePtr previousPtr;    /*pointer to previous node in list*/
    	ListNodePtr currentPtr;     /*pointer to current node*/
    	newPtr = malloc(sizeof(ListNode));  /*creates node*/
    
    
    	if(newPtr != NULL) {            /*is space available*/
    		newPtr->symbol = string;    /*place string in node*/
    		newPtr->value = 1;          /*place value in node*/
    		newPtr->nextPtr = NULL;     /*node does not link to another node*/
    		previousPtr = NULL;
    		currentPtr = *sPtr;
    
    
    		while(currentPtr != NULL) {
    			if(currentPtr->symbol == string) {   /*If symbol exists...*/
    				currentPtr->value = (currentPtr->value+1);   /*increase value by 1*/
    				break;
    			}
    			else
    				previousPtr = currentPtr;
    				currentPtr = currentPtr->nextPtr;
    		}
    			/*create new node at beginning of list*/
    			if(currentPtr == NULL) {
    				newPtr->nextPtr = *sPtr;
    				*sPtr = newPtr;
    			}
    			else if(currentPtr->symbol != string)
    			{
    				newPtr->nextPtr = *sPtr;
    				*sPtr = newPtr;
    			}
    	}
    	else
    		printf("%s not inserted.\n", string); fflush(stdout);
    	return 0;
    }/*end function insertIt*/
    I really have no idea what I am doing here.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    One problem is that you cannot assign strings across the equals sign in C. (Yeah, I know: "WTF???" but it is what it is)

    You are working in a language with absolutely no awareness of text or strings. Instead it uses character arrays and adds a null to the end of each "string". The only way to move strings around is to copy them with library functions... strcpy(), strdup() etc.

    For example:
    Code:
            newPtr->symbol = string;    /*place string in node*/
    ... simply is not going to work.

    What you end up doing is assigning your symbol pointer to the address of string... and if you are getting your input into a standard buffer, you will end up with ALL your strings pointing to the same place... thus displaying whatever text was last placed in the buffer.

    You can try this...
    Code:
    // plan A
    newPtr->symbol = strdup(string);
    
    // plan B (if you don't have strdup)
    newPtr->symbol = malloc(strlen(string) + 1);
    strcpy(newPtr->symbol,string);
    In either of these cases you will eventually have to free() the memory allocated to these strings... *before* you destroy the node struct.
    Last edited by CommonTater; 10-08-2011 at 01:59 PM.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    So how do I use free()?
    Do I just put free(string); at the end of the function?

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Nope... free() releases allocated memory. You are allocating memory twice for each node in your list... once for the node itself and once for the char array content... When deleting nodes or tearing down the list you are are going to have to walk the entire list, freeing first the string then the node ... for every node in the list.

    For every call to malloc() you must have a matching call to free()...

    I don't have enough of your code to show you how to do it, but it's not that difficult... I'm sure your books cover it anyway.

  5. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    our professor never mentioned anything about free even though he did use malloc in class. hopefully I can figure it out but I might be coming back here once I get to the delete function
    Last edited by aw1742; 10-08-2011 at 03:25 PM.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    There are quite a few tutorials about linked lists on the web... a little Google action might be in order

    You might also look up the free() function in your C Library Documetation ...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. Help! -Linked Lists, Memory Allocation, Time Steps, Debugg
    By MetallicaX in forum C Programming
    Replies: 2
    Last Post: 03-14-2009, 08:50 PM
  3. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  4. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 01:49 AM
  5. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM

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