Have something to say? Contribute New Article Reply to this Article
Help with Linked list Delete function
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 */
}
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:
previousPtr = *tailPtr; currentPtr->prevPtr = previousPtr;
What's that piece of code doing?
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
currentPtr->nextPtr->prevPtr = previousPtr //It's a doubly linked list, remember? so gotta assign prevPtr toopreviousPtr = *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.
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)
char delete ( ListNodePtr **sPtr, ListNodePtr **tailPtr, char value )
I believe he has his structure defined something like this:
struct node
{
char data;
struct node* nextPtr;
struct node* prevPtr;
};
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.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?
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 */
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.
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 )
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;
/* 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 */
}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 */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].
I got rid of line 12 completley, It wasn't doing any good.. I double checked to make sure i was sending my print the beginning of the list, and I am, but i'm still running into errors. I'm losing my list. When i try to delete the first character in my printbackwards.. The hole program crashes. Everything is deleting fine in in the print forwards, but not in the printbackwards. I'm guessing it has to deal with my prevPtr, but i can't figure it out.
Replace
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
currentPtr = previousPtr;
currentPtr->nextPtr->prevPtr = previousPtr;
with
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
if(currentPtr->nextPtr != NULL)
{
currentPtr = previousPtr;
currentPtr->nextPtr->prevPtr = previousPtr;
}
That should get it to work. Lemme know how it goes.
Thanks Denvar for all your help so far. I replaced the old code with the code you just typed up. It fixed that error with deleting the last node in the list now.. Now the only problem is.. When I run the program. I can delete anything from anywhere in the list without a problem, but when it comes down to delete the last character left in the list. The program crashes.
here is what I have so far.
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;
currentPtr = currentPtr->nextPtr;
} /* end while */
/* delete node at currentPtr */
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
if(currentPtr->nextPtr != NULL) {
currentPtr = previousPtr;
currentPtr->nextPtr->prevPtr = previousPtr;
}
free ( tempPtr );
return value;
} /* end if */
} /* end else */
return '\0';
} /* end function delete */Replace
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
(*sPtr)->prevPtr = NULL;
with
tempPtr = *sPtr; /* hold onto node being removed */
if((*str)->nextPtr != NULL)
{
*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
(*sPtr)->prevPtr = NULL;
}
Same problem as before. When it's the last node to be deleted, (*str)->nextPtr will be pointing to NULL. Then in line 10 of your code you are assigning that to *str (Now *str is pointing to a NULL value). In line 11 you are using (*str)->prevPtr which is like saying NULL->prevPtr which is making your program crash.
Thanks again Denvar. I placed what you said into the code. Now the program has one more error that i still don't understand. When I delete characters from the list, same as before.. I can delete from anywhere in list until there is one character left in the list. This time, instead of the program crashing right away. When i attempt to delete the last character remaining in the list. The program displays that character again and no action is made. When i try to delete the character again, same thing, and then on the third attempt the program crashes.
here is updated 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 */
if((*sPtr)->nextPtr != NULL)
{
*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;
currentPtr = currentPtr->nextPtr;
} /* end while */
/* delete node at currentPtr */
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
if(currentPtr->nextPtr != NULL) {
currentPtr = previousPtr;
currentPtr->nextPtr->prevPtr = previousPtr;
}
free ( tempPtr );
return value;
} /* end if */
} /* end else */
return '\0';
} /* end function delete */Perhaps that's cause there's no underflow check in your delete function. You are letting the user select the delete option even when there's nothing left to delete. In other terms, once the user deletes the last node and selects the delete function again, you should display an error msg such as "No more nodes left to delete". You can achieve this by having a count variable which is incremented in the insert function and decremented in the delete function. Then in the delete function if count==0 then display an error msg and return to the main function.
If you're gonna use a count, you'll have to make a special case when count==1. If you don't want to use a seperate count variable just to check if the list is empty or not, you can have three different cases in your delete function.
1. When the list is empty
2. When there's only one element left in the list.
3. When there are more than one element in the list.
This can be achieved thus:
if(*str == NULL)
{
printf("List is empty.\n");
return;
}
if((*str)->nextPtr == NULL)
{
val = (*str)->data; //declare val as a char at the start of the function
free(*str);
*str = NULL;
return val;
}
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;
That will most probably work. Lemme know how it goes.
Devnar that worked great. I did exactly what you said and everything works perfect now. The program is now completley sucessful. You helped me have achieve a better understanding on linked list as well. Thank you so much for your help!
No problem. Happy hacking! :)
P.S.: One last thing- There was no need to declare a separate 'val' variable in my last code snippet. But i guess you figured that out yourself. :)
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
