943,525 Members | Top Members by Rank

Software Development > C > Help with Linked list Delete function
Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 2161
  • C RSS
You are currently viewing page 1 of this multi-page discussion thread
Permalink
Nov 1st, 2008
0

Help with Linked list Delete function

Expand Post »
Hello, I'm in the middle of writing a doubly linked list, I have the print in reverse working fine and my insert function working fine, I just can't seem to find what I'm doing wrong with the delete function.. WHen i try to delete the last letter in the node.. The reverse will display the list as empty, and as of right now only the first character will delete correctly, I just can't seem to figure out what to add into my function
Here's what I have so far:

char delete ( ListNodePtr *sPtr, ListNodePtr *tailPtr, 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 */

*tailPtr = ( *tailPtr)->prevPtr;

free( tempPtr ); /* free the de-threaded node */
return value;
} /* end if */
else {

previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;

previousPtr = *tailPtr;
currentPtr->prevPtr = previousPtr;

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

free ( tempPtr );
return value;
} /* end if */

}
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
dampecram is offline Offline
9 posts
since Oct 2008
Permalink
Nov 1st, 2008
1

Re: Help with Linked list Delete function

Code tags
Reputation Points: 124
Solved Threads: 18
Junior Poster
devnar is offline Offline
148 posts
since Sep 2008
Permalink
Nov 1st, 2008
0

Re: Help with Linked list Delete function

Wouldn't it be simpler to just use a pointer to structure instead of a pointer to a pointer to a structure?

I think your problem lies here:

Quote originally posted by dampecram ... 
  1. previousPtr = *tailPtr;
  2. currentPtr->prevPtr = previousPtr;
What's that piece of code doing?

  1. tempPtr = currentPtr;
  2. previousPtr->nextPtr = currentPtr->nextPtr;
  3. currentPtr->nextPtr->prevPtr = previousPtr //It's a doubly linked list, remember? so gotta assign prevPtr too
Last edited by devnar; Nov 1st, 2008 at 4:09 am.
Reputation Points: 124
Solved Threads: 18
Junior Poster
devnar is offline Offline
148 posts
since Sep 2008
Permalink
Nov 1st, 2008
0

Re: Help with Linked list Delete function

previousPtr = *tailPtr;
currentPtr->prevPtr = previousPtr;

that line oringinally when in my code deleted the last character i thought when i printed the list out in reverse, i just messed around with that code and it ended up not doing any good at all, so you were right., When i put your line in the code.. You can delete from the middle of the list which is working great.. but now I'm having trouble delting the first and last node of the list when i go to print the list out in reverse. That line i had just gives an error so I don't think its needed in the code anymore, I got rid of it.
Last edited by dampecram; Nov 1st, 2008 at 1:16 pm.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
dampecram is offline Offline
9 posts
since Oct 2008
Permalink
Nov 1st, 2008
0

Re: Help with Linked list Delete function

Wait until someone verifies this advice, but back in the day, I did a doubly linked list program. I made the delete function somewhat like you did, and my program didn't work correctly. I think it should be declared as

char delete ( ListNodePtr **sPtr, ListNodePtr **tailPtr, char value )


Anyone... verify or contradict that suggestion?

(Don't take this advice until someone experienced elaborates)
Reputation Points: 874
Solved Threads: 352
Posting Maven
BestJewSinceJC is offline Offline
2,758 posts
since Sep 2008
Permalink
Nov 2nd, 2008
0

Re: Help with Linked list Delete function

Quote originally posted by BestJewSinceJC ...
char delete ( ListNodePtr **sPtr, ListNodePtr **tailPtr, char value )
I believe he has his structure defined something like this:
  1. struct node
  2. {
  3. char data;
  4. struct node* nextPtr;
  5. struct node* prevPtr;
  6. };
  7. typedef struct node* ListNodePtr;
So when the function is defined your way, sPtr becomes a pointer to a pointer to a pointer to a structure, which is quite unnecessary.
Quote originally posted by dampecram ...
but now I'm having trouble delting the first and last node of the list when i go to print the list out in reverse.
I'm not sure i understand what you're saying. How does deleting a node disrupt displaying the list in reverse?
Reputation Points: 124
Solved Threads: 18
Junior Poster
devnar is offline Offline
148 posts
since Sep 2008
Permalink
Nov 2nd, 2008
0

Re: Help with Linked list Delete function

yes that's how my structure is defined, and deleting is disrupting how my list is displayed because I'm missing a link to my prevPtr. My prevPtr works fine for deleting from the middle of the list, but when i try to delete the first node or last node in the list.. When my list goes to display in reverse, I get an error.

here is my printbackwards
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 */
Reputation Points: 10
Solved Threads: 0
Newbie Poster
dampecram is offline Offline
9 posts
since Oct 2008
Permalink
Nov 2nd, 2008
0

Re: Help with Linked list Delete function

I don't see any fault in your code, but make sure you've assigned the prevPtr of the first node to null while inserting for the first time. Maybe someone more experienced would take a look at your code if you had used the freakin CODE TAGS the second time at least.
Reputation Points: 124
Solved Threads: 18
Junior Poster
devnar is offline Offline
148 posts
since Sep 2008
Permalink
Nov 2nd, 2008
0

Re: Help with Linked list Delete function

I made sure that prevPtr was assigned to NULL in the insert function. The problem now is when I delete the first node in the list. When the list is printed out in reverse after I choose to delete the first node in the list.. The list comes up empty.. and when I try to delete the last node in the list.. The program freezes. but the program works fine when i delete from anywhere in the middle of the list.

here is my delete and print backwards function again ( sorry about previous post without code tags )

  1. char delete ( ListNodePtr *sPtr, ListNodePtr *tailPtr, char value )
  2. {
  3. ListNodePtr previousPtr; /* pointer to previous node on list */
  4. ListNodePtr currentPtr; /* pointer to current node on list */
  5. ListNodePtr tempPtr; /* temperary node pointer */
  6.  
  7. /* delete first node */
  8. if (value == ( *sPtr )->data) {
  9. tempPtr = *sPtr; /* hold onto node being removed */
  10. *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
  11.  
  12. *tailPtr = ( *tailPtr)->prevPtr;
  13.  
  14. free( tempPtr ); /* free the de-threaded node */
  15. return value;
  16. } /* end if */
  17. else {
  18.  
  19. previousPtr = *sPtr;
  20. currentPtr = ( *sPtr )->nextPtr;
  21.  
  22. /* loop to find correct location on list */
  23. while ( currentPtr != NULL && currentPtr->data != value ) {
  24. previousPtr = currentPtr; /* walk to ....*/
  25. currentPtr = currentPtr->nextPtr; /*....next node*/
  26. } /* end while */
  27.  
  28. /* delete node at currentPtr */
  29. if ( currentPtr != NULL ) {
  30.  
  31. tempPtr = currentPtr;
  32. previousPtr->nextPtr = currentPtr->nextPtr;
  33. currentPtr = previousPtr;
  34. currentPtr->nextPtr->prevPtr = previousPtr;
  35.  
  36. free ( tempPtr );
  37. return value;
  38. } /* end if */
  39. }

  1. void printBackwards ( ListNodePtr currentPtr )
  2. {
  3. ListNodePtr temp = NULL;
  4.  
  5. while ( currentPtr != NULL ) {
  6. temp = currentPtr;
  7. currentPtr = currentPtr->nextPtr;
  8. }
  9.  
  10. printf( "\nThe list in reverse is:\n" );
  11. printf( "NULL" );
  12.  
  13. currentPtr = temp;
  14. while ( currentPtr != NULL) {
  15. printf( " <-- %c", currentPtr->data );
  16. currentPtr = currentPtr->prevPtr;
  17. }
  18.  
  19. printf("\n\n");
  20.  
  21. } /* end function printBackwards */
Reputation Points: 10
Solved Threads: 0
Newbie Poster
dampecram is offline Offline
9 posts
since Oct 2008
Permalink
Nov 2nd, 2008
0

Re: Help with Linked list Delete function

In your delete function what does the code in line 12 do? That looks like trouble. In the printBackwards function, currentPtr points to the starting node when you call the function, right? If you've forgotten to assign that, it'll cause trouble. Other than that, it looks to work fine to me.

On another note, when using code tags, it's [CODE=C], not [CODE=SYNTAX].
Reputation Points: 124
Solved Threads: 18
Junior Poster
devnar is offline Offline
148 posts
since Sep 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: please explain
Next Thread in C Forum Timeline: Vector Calculator issues (I got the code)





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC