Thread: First Time Using Linked Lists, Having Trouble Replacing First Node

Hi,

This is the first time I've used linked lists before and I'm having trouble replacing the first "node" of my list. I have a function that takes a node, an old word, and a new word (both character strings). I'm able to replace every node fine unless the old word happens to be the first element.

The thing is... everything appears to be working fine in my debugger (Visual Studios 2003) when I place a breakpoint at my return statement in the function. What I mean is that all of my prev and next pointers line up. I placed another breakpoint directly outside of my function call and I can see that the linked list I pass in does not contain the same data as the one I was working on in the function.

The main thing I notice is that there are is an extra node placed behind what the linked list believes to be the first node.

I don't really understand why the linked list in the function would be different than the one in my main loop because I'm passing in the one from the main loop so I thought they're the same.

Sorry if this is confusing. I don't really know how to explain it better. I have a lot of code implemented so I don't want to post everything unless people find it necessary to answer my question.

Here is my replace_words(). I have an arrow pointing to where I believe I should be resetting the initial pointer of the linked list.

Code:

/******************************************************************************/
/*!

	Replaces all occurances of a character string in a WordNode linked list
	with another.

	\param words
		A pointer to a pointer of the first node in the list. This is a 
		linked list of words.

	\param oldword
		A character string which the function will try to find in the WordNode
		list to replace.

	\param newword
		A character string that the function will try to replace the old character
		string with.

	\return
		Returns 0 upon sucess, -1 on fail.

*/
/******************************************************************************/
int replace_words(WordNode *words, const char *oldword, const char *newword)
{
	int rVal = 0;

	WordNode *temp = find_word(words, oldword);

	/* while find_words finds occurances of oldword */
	while(temp)
	{
		/* setting up temporary nodes */
		WordNode *prev = temp->prev;
		WordNode *next = temp->next;

		/* setting the previous nodes next pointer to NULL so that we can
			add a word after it with the add_word function */
		if(prev)
			prev->next = NULL;

		rVal = add_word(&prev, newword);

		/* if add_word was unable to allocate enough memory return in a fail state */
		if(rVal != 0)
		{
			prev->next = temp;
			return ERROR;
		}

		/* disconnecting temp from main list */
		temp->next = NULL;
		temp->prev = NULL;

		/* deleting the old node */
		delete_word(&temp, oldword);

		/* connecting new nodes together */
		if(prev->next)
		{
			prev->next->next = next;
			next->prev = prev->next;
		}
		else	/* if prev will start the list */
		{
			prev->next = next;
			next->prev = prev;
			words = prev;   // <------------------------ where I reset the initial pointer
		}

		/* seeing if any more occurances of oldword exist */
		temp = find_word(words, oldword);

	} /* end while(temp) */

	return 0;
}

Here is what I'm using to test out my functionality. I Understand that you guys won't be able to run the whole thing without all of my other code so if you guys want to do that I can throw that up here as well.

Code:

void SimpleWordTest1(void)
{
  unsigned i;
  unsigned count;
  WordNode *node;
  char *word, *oldword, *newword;
  WordNode *words1 = NULL;
  char *text[] = {"two", "two", "three", "two", "four",
                  "an", "computer", "fiver", "two", "four"};

  printf("\n***** SimpleWordTest1 *****\n");
  for (i = 0; i < sizeof(text) / sizeof(*text); i++)
    add_word(&words1, text[i]);

  print_words(words1);

  add_word(&words1, "red");
  add_word(&words1, "green");
  add_word(&words1, "blue");

  print_words(words1);

  word = "computer";
  node = find_word(words1, word);
  if (node)
    printf("Found the word: '%s'\n", node->word);
  else
    printf("Did not find the word: '%s'\n", word);

  word = "DigiPen";
  node = find_word(words1, word);
  if (node)
    printf("Found the word: '%s'\n", node->word);
  else
    printf("Did not find the word: '%s'\n", word);

  oldword = "two";
  newword = "2";
  printf("Replacing %s with %s:\n", oldword, newword);
  replace_words(words1, oldword, newword);
  print_words(words1);

  word = "2";
  count = count_matching_words(words1, word);
  printf("The word '%s' appears %u time(s) in the list.\n", word, count);

  printf("Deleting all occurrences of the word '%s':\n", word);
  delete_word(&words1, word);  // <---- breaks in here because of pointer error I believe
  print_words(words1);

  word = "digipen";
  printf("Deleting all occurrences of the word '%s':\n", word);
  delete_word(&words1, word);
  print_words(words1);
 
  printf("Printing words in reverse:\n");
  print_words_reverse(words1);

  free_words(words1);
}

Because it's breaking in delete_word I'll post that just to make sure it's ok.

Code:

/******************************************************************************/
/*!

	Deletes a word from a WordNode list.

	\param words
		A pointer to a pointer of the first node in the list. This is a 
		linked list of words.

	\param word
		A character string of which every occurance in the WordNode list will 
		be deleted.

*/
/******************************************************************************/
void delete_word(WordNode **words, const char *word)
{
	/* finding if any occurances of the word exist */
	WordNode *temp = find_word(*words, word);

	/* while occurances are found */
	while(temp)
	{
		/* create temporary nodes*/
		WordNode *prev = temp->prev;
		WordNode *next = temp->next;

		/* if node is the first there will be no previous node */
		if(prev != NULL)
			prev->next = next;	/* pointing previous node at new next node */
		else
			(*words) = next; /* if word occured in first node making 
								words now point	to new first node*/

		/* if word occured in last node there will be no next */
		if(next != NULL)
			next->prev = prev; /* pointing next node at new previous node */

		/* getting rid of node with occurance of word*/
		free(temp->word);
		free(temp);

		/* if there is no next node exit the function*/
		if(next != NULL)
			temp = find_word(*words, word);
		else
			return;
	}	
}

Thanks for any help you guys could give.
-Peter

Oh yeah... definition of a WordNode.

Code:

struct WordNode
{
  char *word;
  struct WordNode *next;
  struct WordNode *prev;
};