Help with Linked list Delete function

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
Reply
1 2

•
•
Join Date: Oct 2008
Posts: 9
Reputation: dampecram is an unknown quantity at this point 
Solved Threads: 0
dampecram dampecram is offline Offline
Newbie Poster

Help with Linked list Delete function

 
0
  #1
Nov 1st, 2008
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 */

}
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 148
Reputation: devnar will become famous soon enough devnar will become famous soon enough 
Solved Threads: 16
devnar's Avatar
devnar devnar is offline Offline
Junior Poster

Re: Help with Linked list Delete function

 
1
  #2
Nov 1st, 2008
Code tags
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 148
Reputation: devnar will become famous soon enough devnar will become famous soon enough 
Solved Threads: 16
devnar's Avatar
devnar devnar is offline Offline
Junior Poster

Re: Help with Linked list Delete function

 
0
  #3
Nov 1st, 2008
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:

•
•
•
•
Originally Posted by dampecram
c Syntax (Toggle Plain Text) 
  1. previousPtr = *tailPtr;
  2. currentPtr->prevPtr = previousPtr;
What's that piece of code doing?

c Syntax (Toggle Plain Text) 
  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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 9
Reputation: dampecram is an unknown quantity at this point 
Solved Threads: 0
dampecram dampecram is offline Offline
Newbie Poster

Re: Help with Linked list Delete function

 
0
  #4
Nov 1st, 2008
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 1,647
Reputation: BestJewSinceJC is a splendid one to behold BestJewSinceJC is a splendid one to behold BestJewSinceJC is a splendid one to behold BestJewSinceJC is a splendid one to behold BestJewSinceJC is a splendid one to behold BestJewSinceJC is a splendid one to behold 
Solved Threads: 206
BestJewSinceJC BestJewSinceJC is offline Offline
Posting Virtuoso

Re: Help with Linked list Delete function

 
0
  #5
Nov 1st, 2008
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)
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 148
Reputation: devnar will become famous soon enough devnar will become famous soon enough 
Solved Threads: 16
devnar's Avatar
devnar devnar is offline Offline
Junior Poster

Re: Help with Linked list Delete function

 
0
  #6
Nov 2nd, 2008
•
•
•
•
Originally Posted by BestJewSinceJC
char delete ( ListNodePtr **sPtr, ListNodePtr **tailPtr, char value )
I believe he has his structure defined something like this:
c Syntax (Toggle Plain Text) 
  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.
•
•
•
•
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?
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 9
Reputation: dampecram is an unknown quantity at this point 
Solved Threads: 0
dampecram dampecram is offline Offline
Newbie Poster

Re: Help with Linked list Delete function

 
0
  #7
Nov 2nd, 2008
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 */
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 148
Reputation: devnar will become famous soon enough devnar will become famous soon enough 
Solved Threads: 16
devnar's Avatar
devnar devnar is offline Offline
Junior Poster

Re: Help with Linked list Delete function

 
0
  #8
Nov 2nd, 2008
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 9
Reputation: dampecram is an unknown quantity at this point 
Solved Threads: 0
dampecram dampecram is offline Offline
Newbie Poster

Re: Help with Linked list Delete function

 
0
  #9
Nov 2nd, 2008
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 )

C Syntax (Toggle Plain Text) 
  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. }

C Syntax (Toggle Plain Text) 
  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 */
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 148
Reputation: devnar will become famous soon enough devnar will become famous soon enough 
Solved Threads: 16
devnar's Avatar
devnar devnar is offline Offline
Junior Poster

Re: Help with Linked list Delete function

 
0
  #10
Nov 2nd, 2008
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].
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum


Views: 1646 | Replies: 18
Thread Tools Search this Thread



Tag cloud for C
#include * append array arrays bash binarysearch changingto char character cm command copyanyfile creafecopyofanytypeoffileinc createprocess() database directory dynamic execv feet fgets file floatingpointvalidation fork forloop framework function functions getlogicaldrivestrin givemetehcodez global grade graphics gtkwinlinux histogram homework ide include initialization input interest intmain() iso keyboard kilometer lazy license linked linkedlist linux list looping loopinsideloop. lowest matrix meter microsoft mqqueue oddnumber odf openwebfoundation overwrite pause pdf pointer posix power process program programming pyramidusingturboccodes radix read recursion recv recvblocked research reversing segmentationfault sequential single socket socketprogramming spoonfeeding standard strchr string student suggestions system test testing threads turboc unix urboc user whythiscodecausesegmentationfault win32api windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC