Delete Function in Doubly Linked List

This is a discussion on Delete Function in Doubly Linked List within the C Programming forums, part of the General Programming Boards category; Hello, I am having trouble with my doubly linked list program. My insert function seems to work fine, but where ...

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    8

    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 */

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    Follow tabstop's advice and revisit the code for /* delete first node */ section.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    8
    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 */

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    before deleting the first (or last) node you ought to make sure that the next pointer is meaningful ie not NULL
    revisit the /* delete first node */ section again
    Last edited by itCbitC; 11-11-2008 at 07:33 PM.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    8
    Thank you for pointing me in the right direction. It works perfectly now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 09:55 PM
  3. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-30-2005, 12:21 AM
  4. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 10:51 AM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM

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