access violation error in my doubly linked list program when deleting.

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 851 Views - Last Post: 22 November 2011 - 11:19 AM Rate Topic: -----

#1 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 09:18 AM

Hi I have programmed a doubly linked list for one of my courses. The program takes a list of characters and then prints them forwards and backwards. I got those 2 parts work fine.

But my delete function is causing issues. I can delete the LAST member of the list, but whenever I try and delete any other member, I get this error:

"Access violation reading location 0xfeeefeee."

I'm guessing that means one of my pointers is screwed up. I've played around with it for a few hours but can't get past this point.

It breaks on this line:

printf( " <-- %c", currentPtr->data );


which is in my print backwards function.

The whole function is:

void printBackwards ( ListNodePtr currentPtr )
{
     ListNodePtr temp = NULL;
 
	  while ( currentPtr != NULL ) {
		 temp = currentPtr;
		 currentPtr = currentPtr->nextPtr;
		 
		 }
		 
      printf( "\nReverse List:\n" );
      printf( "NULL" );
 
		 currentPtr = temp;
		 while ( currentPtr !=  NULL) {
		 printf( " <-- %c", currentPtr->data );
		 currentPtr = currentPtr->prevPtr;
		 }
		 
		 printf("\n\n");
		 
}



Here is my delete function:

/* delete a list element */
char charDelete ( 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;
			free ( tempPtr );
			return value;
		} /* end if */
	} /* end else */
	return '\0';
} /* end function delete */



Everything looks ok. I don't see anything wrong with my logic. Could it be my compiler?

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: access violation error in my doubly linked list program when deleting.

#2 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 656
  • View blog
  • Posts: 2,247
  • Joined: 31-December 10

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 10:21 AM

Before you delete the pointer to the node, you need to change the next pointer for the node before the node you are deleting. Either to zero (if it's the last node), or to the node after the one you're deleting.
Was This Post Helpful? 1
  • +
  • -

#3 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 11:28 AM

But I do...I am setting it as the temporary pointer at the very beginning.

Thank you
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 11:43 AM

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


Pay attention to where your program is blowing up...what are you doing at that point, and what's missing from the code above?
Was This Post Helpful? 1
  • +
  • -

#5 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 11:50 AM

It is deleting tempPtr...which is what I want it to do.
Was This Post Helpful? 0
  • +
  • -

#6 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 12:59 PM

Ok I changed my code to below and now I'm at least not getting an error. But I do throw it into an infinite loop:

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


Was This Post Helpful? 0
  • +
  • -

#7 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 02:02 PM

View PostJackOfAllTrades, on 18 November 2011 - 11:43 AM, said:

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


Pay attention to where your program is blowing up...what are you doing at that point, and what's missing from the code above?



I added this just above free (tempPtr);

previousPtr->nextPtr=previousPtr;

Was This Post Helpful? 0
  • +
  • -

#8 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 02:12 PM

Nope, you're missing the point. I'm trying to lead you to the answer.

In what function is it crashing?
On what functionality does that function depend?
What is missing from the code I highlighted below that could be causing it?

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


Was This Post Helpful? 1
  • +
  • -

#9 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 02:16 PM

It doesn't crash anymore, it just gets trapped in a loop whenever I delete a node other than the first node.

I believe the code I added, previousPtr->nextPtr=previousPtr;, is the part I was missing.

So that at least fixed the crash, but I'm not sure why it's getting trapped in a loop.

Thanks
Was This Post Helpful? 0
  • +
  • -

#10 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: access violation error in my doubly linked list program when deleting.

Posted 18 November 2011 - 02:23 PM

Sigh...

Relevant part of the function that is crashing:
while ( currentPtr !=  NULL) {
    printf( " <-- %c", currentPtr->data );
    currentPtr = currentPtr->prevPtr;
}


Your delete code:
/* delete node at currentPtr */
if ( currentPtr != NULL )
{
    tempPtr = currentPtr;
    previousPtr->nextPtr = currentPtr->nextPtr;
    free ( tempPtr );
    return value;
} /* end if */



Something is missing there in your deletion of a node from a doubly-linked list.
Was This Post Helpful? 2
  • +
  • -

#11 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 21 November 2011 - 11:51 AM

Why can't I get this?? I just can't wrap my head around it. I tried all weekend but I kept on getting the same endless loop error!

Is the flaw in my delete logic?

Thanks
Was This Post Helpful? 0
  • +
  • -

#12 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: access violation error in my doubly linked list program when deleting.

Posted 21 November 2011 - 04:47 PM

Your code that is crashing is using the nodes' prevPtr member to iterate backwards through your list, right?

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


To what does the prevPtr member of the currentPtr->nextPtr node point when this code is done?

Let's play with the variable names a little.

if (currentPtr != NULL) {
  
    /* I hate typedef'd pointers by the way. It obfuscates the 
       code simply because people get scared by the little *s */
    ListNodePtr nodeToDelete = currentPtr;
    ListNodePtr nodeBeforeDeletedNode = nodeToDelete->prevPtr;
    ListNodePtr nodeAfterDeletedNode = nodeToDelete->nextPtr;
    
    /* 
     Make node BEFORE the deleted node point to the node 
     AFTER the deleted node for the FORWARD direction
    */
    nodeBeforeDeletedNode->nextPtr = nodeAfterDeletedNode;

    /* 
     Make node AFTER the deleted node point BACK to the node
     BEFORE the deleted node for the BACKWARD direction
    */ 
    nodeAfterDeletedNode->prevPtr = nodeBeforeDeletedNode;
    
    /* Free the node */
    free(nodeToDelete);
}

Was This Post Helpful? 1
  • +
  • -

#13 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 22 November 2011 - 07:42 AM

Wow changing the names of the variables really helped.

These last 2 chapters in my C class are really hard to understand. I haven't had to search for help til now. I think it's the pointers that are really warping my brain.

So if I understand this correctly...

nodeBeforeDeletedNode is the node in front of nodeToDelete
nodeAfterDeletedNode is the node behind of nodeToDelete

So in the function, nodeBeforeDeletedNode becomes nextPtr?

And nodeAfterDeletedNode becomes prevPtr?

Forgive my immense ignorance, but I can't understand that.

The '->' means that variable points to the value stored at the pointed to memory pointer, correct?

For example

X->Y = Z


means X points to the value at Y, and changes it to Z?

Oh man, I feel petty after asking all these questions.

After modifying the code, I am still getting an access violation error at this line:

nodeAfterDeletedNode->prevPtr = nodeBeforeDeletedNode;


So for some reason, it still can't find prevPtr...or prevPtr is NULL?

I am going to do a check for NULL before and see what happens....

Thanks for your guidance thus far...


View PostJackOfAllTrades, on 21 November 2011 - 04:47 PM, said:

Your code that is crashing is using the nodes' prevPtr member to iterate backwards through your list, right?

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


To what does the prevPtr member of the currentPtr->nextPtr node point when this code is done?

Let's play with the variable names a little.

if (currentPtr != NULL) {
  
    /* I hate typedef'd pointers by the way. It obfuscates the 
       code simply because people get scared by the little *s */
    ListNodePtr nodeToDelete = currentPtr;
    ListNodePtr nodeBeforeDeletedNode = nodeToDelete->prevPtr;
    ListNodePtr nodeAfterDeletedNode = nodeToDelete->nextPtr;
    
    /* 
     Make node BEFORE the deleted node point to the node 
     AFTER the deleted node for the FORWARD direction
    */
    nodeBeforeDeletedNode->nextPtr = nodeAfterDeletedNode;

    /* 
     Make node AFTER the deleted node point BACK to the node
     BEFORE the deleted node for the BACKWARD direction
    */ 
    nodeAfterDeletedNode->prevPtr = nodeBeforeDeletedNode;
    
    /* Free the node */
    free(nodeToDelete);
}

Was This Post Helpful? 0
  • +
  • -

#14 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: access violation error in my doubly linked list program when deleting.

Posted 22 November 2011 - 08:36 AM

It's really not that hard if you just visualize it properly.

Your doubly-linked list "looks" like this, right?

Attached Image
(from Wikipedia)

So, in order to remove the node containing 99 and maintain the list's integrity in both directions, what do you need to do? You need to set the "previous" pointer on the node containing 37 to point to the node containing 12, and the "next" pointer on the node containing 12 to point to the node containing 37. Then you free the memory associated with the node containing 99. Done.

So, the "previous" pointer on the node containing 99 points to the node containing 12. Therefore, you set the "previous" pointer of the node containing 37 equal to the "previous" pointer of the node containing 99.

The "next" pointer of the node containing 99 points to the node containing 37, so you set the "next" pointer of the node containing 12 equal to the "next" pointer of the node containing 99.

I cannot explain it any more simply than that.

Using the following picture, you are moving box 2 to box 1 and moving box 4 to box 3:
Attached Image
Was This Post Helpful? 1
  • +
  • -

#15 999cm999  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 18-November 11

Re: access violation error in my doubly linked list program when deleting.

Posted 22 November 2011 - 10:30 AM

Are you actually deleting a node or just the memory pointer?

So the follow code:

			nodeBeforeDeletedNode->nextPtr = nodeAfterDeletedNode;

			nodeAfterDeletedNode->prevPtr = nodeBeforeDeletedNode;



Says:

Change the nextPtr of nodeBeforeDeltedNode to be nodeAfterDeletedNode

and

Change the prevPtr of nodeAfterDeletedNode to be the nodeBeforeDeletedNode

Correct?

Thanks!
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2