Solved

Delete node from linked list

Posted on 2003-12-01
29
483 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
  • 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Delphi Mdi application Child forms get behind control 7 117
mapAB Challlenge 35 89
Currency Conversion? 1 39
Not needed 13 58
This article will show, step by step, how to integrate R code into a R Sweave document
This is about my first experience with programming Arduino.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

743 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now