Solved

Delete node from linked list

Posted on 2003-12-01
29
489 Views
Last Modified: 2010-04-17
I am only leaving this question out for a couple of hours...
I need to delete a node in a linked list (the node has more than one piece of data).  My current function seems to be removing this node, but damages the list, so that further deletes are not working.

bool llistBooks::deleteB(string &target)      
{
bookNoce Ptr before = head;            
bookNodePtr temp = before->next;
for (before; before != NULL; before = before->next)
  for (temp; temp != NULL; temp = temp->next)
  {
    if (temp->isbn == target)                  
  {                              
cout << temp->isbn << "temp" << endl;
cout << before->isbn << "before" << endl;
  temp = before;
  before = temp->next;
  before->next = temp->next;
cout << "BOOK DELETED" << endl;
   return true;                        
  }                              
else      
before = before->next;                  
}                  
return false;
}
0
Comment
Question by:puckerhoop
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 16
  • 12
29 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9849755
bool llistBooks::deleteB(string &target)    
{
bookNoce Ptr before = head;          
bookNodePtr temp = before->next;

 for (temp; temp != NULL; temp = temp->next)
 {
    if (temp->isbn == target)              
    {                        
        cout << temp->isbn << "temp" << endl;
        cout << before->isbn << "before" << endl;
//        temp = before;
   //     before->next = temp->next;
        before->next = temp->next;
        cout << "BOOK DELETED" << endl;
        free (temp); //if it was dynamically allocated .. else comment it out
        return true;                    
    }                        
    else    
        before = before->next;              
}              
return false;
}
0
 

Expert Comment

by:joselopesdacruz
ID: 9849760
when you delete de last node you put a NULL at the previous node ( but now the last one!)
0
 

Author Comment

by:puckerhoop
ID: 9849852
I am not necessarily deleting the last node... usually it is a MIDDLE node.
0
Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

 
LVL 45

Expert Comment

by:sunnycoder
ID: 9849891
there are a few problems with your code ....
1. What happens if your target is present in the first node ?
2. What happens if there are are 0 or 1 elements in your linked list ?

I have corrected the logical error related to deletion in my previous post ... however, I have not added/modified code for these case as this sounds like homework ...

These are the directions you need to be thinking of if you want this function to work for all cases ... The code I corrected in my previous post will work for a list with several nodes and deleting a middle node.

If you need further help, post here
0
 

Author Comment

by:puckerhoop
ID: 9849923
null case has been taken care of - just not put in post
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9849929
good ... what about when target is in first node and list has 1 element ?
0
 

Author Comment

by:puckerhoop
ID: 9849967
the cleaned up code works better, but it still cuts off my linked list at this point.
Any thoughts on how to avoid this separation would be appreciated.

full function with modifications:
-----------------------------------
bool llistBooks::deleteB(string &target)            
{
if (empty() )                        
{
cout << "List is already empty." << endl;
return false;
}
else
{
bookNodePtr before = head;            
bookNodePtr temp = before->next;            
for (temp; temp != NULL; temp = temp->next)
{
if (temp->isbn == target)                  
  {                              
  cout << temp->isbn << "temp" << endl;
  cout << before->isbn << "before" << endl;
  before = temp->next;
  cout << "BOOK DELETED" << endl;
  free(temp);
  return true;                        
  }                              
else      
before = before->next;                  
}                              
return false;
}}
0
 

Author Comment

by:puckerhoop
ID: 9849977
I did not do a case for target in the first node, as I am loading from file a whole series of nodes prior to calling this function.
It is a good point though, I will work on it.
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 500 total points
ID: 9849979
bool llistBooks::deleteB(string &target)          
{
if (empty() )                    
{
cout << "List is already empty." << endl;
return false;
}
else
{
bookNodePtr before = head;          
bookNodePtr temp = before->next;          
for (temp; temp != NULL; temp = temp->next)
{
if (temp->isbn == target)              
  {                        
  cout << temp->isbn << "temp" << endl;
 cout << before->isbn << "before" << endl;
 before->next = temp->next;          //there was error in this statement
 cout << "BOOK DELETED" << endl;
 free(temp);
 return true;                    
 }                        
else    
before = before->next;              
}                        
return false;
}}
0
 

Author Comment

by:puckerhoop
ID: 9850023
before->next needs to point to what temp->next was pointing to... got it.
yet, somehow it is still cutting of my list?!  
i don't get it!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850045
>yet, somehow it is still cutting of my list?!
thats strange ... try printing temp->next in each iteration (print the address) ... it needs to be NULL in the last iteration to cut off the list ..

check if you are deleting the last element of the list
0
 

Author Comment

by:puckerhoop
ID: 9850093
as I walk thru it step by step and put outputs to display, I see that I am now attaching properly, but am somehow dropping the node that is AFTER the new attachment.  How can this be?
0
 

Author Comment

by:puckerhoop
ID: 9850100
I am not deleting the last element... i am deleting the 3rd from the last.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850107
> but am somehow dropping the node that is AFTER the new attachment.  How can this be?
you drop it inside this function or outside it ? My guess is outside it ... stuff in this function looks ok
0
 

Author Comment

by:puckerhoop
ID: 9850137
As I walk thru with "temp" immediately in the function.  It does seem to be working properly, but when I output all to screen, the last one is droppoing off.
When I call delete again.... I get garbage.
I am still working on it.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850142
could be a problem with your display function
0
 

Author Comment

by:puckerhoop
ID: 9850163
could it possibly have to do with "temp"... I use this in other functions... should it be freed or not freed at the end of each function.  I had 'deleted' it at the end of some functions.
0
 

Author Comment

by:puckerhoop
ID: 9850170
i have tested my display function as a solo function and it works fine.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850172
If it is local variable then other functions have no effect ... However, if you have declared it globally, then you need to be very very careful

better approach is to keep temporary variables local
0
 

Author Comment

by:puckerhoop
ID: 9850184
would it be best to use the same temporary node name in each function?  As I comment out the deletes & frees, the program runs better.
0
 

Author Comment

by:puckerhoop
ID: 9850190
i had thought that I had set it up as a temporary.  I have been calling bookNodePtr in all functions, just like you saw in this function.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850193
>would it be best to use the same temporary node name in each function?
does not matter at all as long as they are local ... for the compiler it is nothing more than a symbol representing a variable

>As I comment out the deletes & frees, the program runs better.
you mean speed up ?
0
 

Author Comment

by:puckerhoop
ID: 9850196
the only global is "head" which is declared as private in my llistBooks class.
0
 

Author Comment

by:puckerhoop
ID: 9850202
bookNodePtr is a typedef for bookNode (which is the struct).
0
 

Author Comment

by:puckerhoop
ID: 9850212
taking out the deletes and frees from the end of the function:
  it does not speed it up, the program runs cleaner... i don't get kicked out as often.
ie.  if I have freed "temp", I am getting kicked out of compiler after the function runs.  If I comment it out, it will go on to the next function.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850213
then it should be just fine ... there is some logical error in one of your functions ...

call all your functions one by one and print the values in between ... you will get garbage after erroneous function ... else try stepping through the code and locate the function/statement where you get an error and then try to backtrace to the origin of the error
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850233
>if I have freed "temp", I am getting kicked out of compiler after the function runs
use free/delete if and only if the nodes were added dynamically (using malloc or new) ...

try commenting all free() and then run it ... if it runs perrfectly, then try uncommenting them one by one until you get an error ...
looks like you may be freeing a valid node .. or freeing without copying/changing addresses
0
 

Author Comment

by:puckerhoop
ID: 9850256
Actually, I think I have found the problem... it is another function that is called after delete.  I thought it was working fine, but it seems that it was not.
Thank you!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9850290
cheers :o)
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Progress
Starting up a Project

623 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question