Thread: Delete Function in Doubly Linked List

Hello, I am having trouble with my doubly linked list program. My insert function seems to work fine, but where I'm having trouble is the delete function.. Problem is when i try to delete from the beginning or end of the list, the program crashes in the printbackwards. Depending on the order I try to delete, I can delete the middle characters first and then the program crashes after I try to delete the first and last characters. It seems to be a problem with my prevPtr, but I cannot see where I'm going wrong. Here are my insert/delete/printbackwards functions

Code:

void insert ( ListNodePtr *sPtr, char value)
{
	ListNodePtr newPtr;       /* pointer to a new node */
    ListNodePtr previousPtr;  /* pointer to previous node in list */
    ListNodePtr currentPtr;  /* pointer to current node on list */
    
	newPtr = malloc( sizeof( ListNode )); /* create node */

	if ( newPtr != NULL ) { /* is space available */
		newPtr->data = value; /*place value in node */
		newPtr->nextPtr = NULL; /*node does not link to another node */
		newPtr->prevPtr = NULL;

		previousPtr = NULL;
		currentPtr = *sPtr;
	
		/* loop to find the correct location in the list */
		while (currentPtr != NULL && value > currentPtr->data ) {
	
            previousPtr = currentPtr;          /* walk to...*/
			currentPtr = currentPtr->nextPtr;  /* .....next node */ 	
		} /* end while */
		/* insert new node at begining of list */
		if ( previousPtr == NULL ) {
			newPtr->nextPtr = *sPtr;
			
            if(*sPtr != NULL)
              (*sPtr)->prevPtr = newPtr;
              
            *sPtr = newPtr;
            
		} /* end if */
		else { /* insert new node between previousPtr and currentPtr */
			
			newPtr->prevPtr = previousPtr;

            previousPtr->nextPtr = newPtr;
            newPtr->nextPtr = currentPtr;
            
            if (currentPtr != NULL)
              currentPtr->prevPtr = newPtr;	
              	 
		} /* end else */
	} /* end if */
	else {
		printf( "%c not inserted. No memory available.\n", value );
	} /* end else */	
} /* end function insert */

char delete ( ListNodePtr *sPtr, char value )
{
	ListNodePtr previousPtr; /* pointer to previous node on list */
    ListNodePtr currentPtr;  /* pointer to current node on list */
    ListNodePtr tempPtr;     /* temperary node pointer */
    
	/* delete first node */
	if (value == ( *sPtr )->data) {
		tempPtr = *sPtr; /* hold onto node being removed */
        *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
        
		free( tempPtr ); /* free the de-threaded node */
		return value;
	} /* end if */
	else {
	
    	previousPtr = *sPtr;
		currentPtr = ( *sPtr )->nextPtr;

		/* loop to find correct location on list */
		while ( currentPtr != NULL && currentPtr->data != value )  {
			previousPtr = currentPtr;            /* walk to ....*/
			currentPtr = currentPtr->nextPtr;    /*....next node*/
		} /* end while */

		/* delete node at currentPtr */
		if ( currentPtr != NULL ) {
             
			tempPtr = currentPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			currentPtr = previousPtr;		
			currentPtr->nextPtr->prevPtr = previousPtr;
			
			free ( tempPtr );
			return value;
		} /* end if */
	} /* end else */
	return '\0';
} /* end function delete */

void printBackwards ( ListNodePtr currentPtr )
{
     ListNodePtr temp = NULL;
 
	  while ( currentPtr != NULL ) {
		 temp = currentPtr;
		 currentPtr = currentPtr->nextPtr;
		 }
		 
      printf( "\nThe list in reverse is:\n" );
      printf( "NULL" );
 
		 currentPtr = temp;
		 while ( currentPtr !=  NULL) {
		 printf( " <-- %c", currentPtr->data );
		 currentPtr = currentPtr->prevPtr;
		 }
         	 
		 printf("\n\n");
		 
} /* end function printBackwards */

When you try to delete the head node, you need to set the previous pointer of the new head to NULL. (Otherwise going backwards you will try to visit the now-deallocated node.)

Follow tabstop's advice and revisit the code for /* delete first node */ section.

Thanks alot, doing what you said worked great.. my only problem im running into now is
Example: say I enter in the name Carl
printforward: a -> c -> l -> r is displayed
printbackward: r <- l <- c <- a is displayed

Every character is deleted sucessfully except the letter 'r' .. when I try to delete 'r' my program crashes.

Code:

char delete ( ListNodePtr *sPtr, char value )
{
	ListNodePtr previousPtr; /* pointer to previous node on list */
    ListNodePtr currentPtr;  /* pointer to current node on list */
    ListNodePtr tempPtr;     /* temperary node pointer */
    
	/* delete first node */
	if (value == ( *sPtr )->data) {
		tempPtr = *sPtr; /* hold onto node being removed */
        *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
       (*sPtr)->prevPtr = NULL;
        
		free( tempPtr ); /* free the de-threaded node */
		return value;
	} /* end if */
	else {
	
    	        previousPtr = *sPtr;
		currentPtr = ( *sPtr )->nextPtr;

		/* loop to find correct location on list */
		while ( currentPtr != NULL && currentPtr->data != value )  {
			previousPtr = currentPtr;            /* walk to ....*/
			currentPtr = currentPtr->nextPtr;    /*....next node*/
		} /* end while */

		/* delete node at currentPtr */
		if ( currentPtr != NULL ) {
             
			tempPtr = currentPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			currentPtr = previousPtr;		
			currentPtr->nextPtr->prevPtr = previousPtr;
			
			free ( tempPtr );
			return value;
		} /* end if */
	} /* end else */
	return '\0';
} /* end function delete */

Thank you for pointing me in the right direction. It works perfectly now.