delete end function in a single link list

[domaa]

I am having issues with trying to delete the information at the end of my list.

Here is a list of my code

// things needed in this program
// link* add_before(Link* p,Link* n,const string& s) find s in the list of p, insert n before it, return the pointer to the beginning of the revised list
// Done link* add_after(Link* p, Link* n, const string& s) find s in the list of p, insert n after it, return the pointer to the beginning of the revised list
// Link* delete_end(Link* p) remove the last link return the pointer to the beginning of the new list
// Link* delete_found(Link* p, const string& s) remove link with s as the value in the list p return the pointer to the beginning
#include "std_lib_facilities.h"

//The structure
struct Link {
string name;
Link* next;
Link(const string& n, Link* s = 0)
: name(n), next(s) { }
};
//The insert part
Link* insert(Link* p, Link* n)
{
if (n==0) return p;
if (p==0) return n;
n->next = p;
return n;
}
//Print function
void print_all(Link *p)
{
Link *current;
current = p;
while(current)
{
cout<<"Name: "<<current->name<<".\n";
current = current->next;
}
}
//The add after function
Link * add_after_find(Link *p, Link *n,const string& s )
{ Link *current = 0;
current = p;
if(p == 0)
{ cout<<"List is empty so string not found so not added after it. \n";
return 0;
}
else if(p->next == 0)
{
if(p->name == s)
{
p->next = n;
n->next = 0;
return p;
}
else
{
cout<<"String not found in link listed so not added. \n";
return p;
}
}
else
{
current = p;
while(current->next)
{
if (s == current->name)
{
n->next = current->next;
current->next = n;
return p;
}
else
{
current = current->next;
}
}
cout<<"String is not found so not add after it. \n";
return p;
}
}
//The add before function(not working)
Link * add_before_find(Link *p, Link *n,const string& s )
{ Link *current = 0;
current = p;
if(p == 0)
{ cout<<"List is empty so string not found so not added after it. \n";
return 0;
}
else if(p->next == 0)// this is at the end of the list next = 0
{
if(p->name == s)// if pointer points at a name that is equel to s then
{
p->next = n;// pointer points at next that now equels n. n is what we are adding.
n->next = 0;// n points at next that value is zero.
return p;
}
else
{
cout<<"String not found in link listed so not added. \n";
return p;
}
}
else // So we are not at the end of the list, we are not at a null list now what.
{
current = p;
while(current->next)
{
if (s == current->name)// if the current pointer points at a name that is equel to s then...
{
n->next = current->next;// n points to next that is equel to current pointing to next
current->next = n;
return p;
}
else
{
current = current->next;
}
}
cout<<"String is not found so not add after it. \n";
return p;
}
}
//The delete first element in the list
Link * delete_begin(Link *p)
{
Link *current =0;
current = p;
if(p==0) return 0;
p = p->next;
delete current;
return p;
}
//The delete end element in the list(not working)
Link * delete_end(Link *p)
{
Link *current = 0;
Link *behind_current = 0;
behind_current = p;
current = p->next;
while(current->next)
{
if (current->next == 0)// if the current pointer points at a name that is equel to s then...
{
cout<<"end values\n";
cout<<current<<"\n";
cout<<behind_current<<"\n";
return p;
}
else
{
current = current->next;
behind_current = behind_current->next;
}
}
return p;
}
//-------------------------------------------------------------------------------
int main()

{
Link* emptylist = 0;

cout<<"TEST There is no list attempt to print. \n";
emptylist= add_after_find(emptylist,new Link("Harry"),"Carol");

cout<<"\nNext set of test\n";//---------------------------------------------TEST
Link*newlist = new Link("Gwen");
cout<<"TEST One list was added attempt to print. \n";
cout<<"Printing current list.\n";
print_all(newlist);

cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"TEST Now we are goign to try and add Harry after Ned. Ned is not in list.\n";
newlist = add_after_find(newlist,new Link("Harry"),"Ned");
cout<<"Printing current list.\n";
print_all(newlist);

cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"TEST Now we are going to try and add Harry after Gwen. Gwen is in list.\n";
newlist = add_after_find(newlist,new Link("Harry"),"Gwen");
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
// cout<<"TEST IF PROGRAM WORKS WITH TWO or more links in list i.e. links are Gwen \n and Harry .\n";
cout<<"Now we are goign to look for Ned then add taren behind Ned. Ned is not in list.\n";
newlist = add_after_find(newlist,new Link("Taren"),"Ned");
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"Now we are going to look for Gwen then add Taren after. Gwen is in the list.\n";
newlist = add_after_find(newlist,new Link("Taren"),"Gwen");
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"Now we are going to look for Taren and add Milton after. Taren is in the list.\n";
newlist = add_after_find(newlist,new Link("Milton"),"Taren");
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"Now we are going to look for Taren and add Dondi before him. Taren is in the list.\n";//-------------------------------------------------
newlist = add_before_find(newlist,new Link("Dondi"),"Taren");
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"Now we are going to delete the first name in the list.\n";
newlist = delete_begin(newlist);
cout<<"Printing current list.\n";
print_all(newlist);
cout<<"\nNext set of test\n";//---------------------------------------------TEST
cout<<"Now we are going to delete the last name in the list.\n";
newlist = delete_end(newlist);
cout<<"Printing current list.\n";
print_all(newlist);
system("Pause");
return 0;
}

//------------------------------------------------------------------------------
I am having problems with my delete end element function.

I made 2 pointers the first pointer points to the list. The second pointer points to that same list but one spot behind the first pointer. Now i'm looking for the end of the list. The end of the list would be found by the first pointer finding a 0 or null element in the list. Once that is found then the second pointer gets deleted because that will be pointing at the last value. Then i want the pointer to return to the head of the list.

Also having problems with my add before function.

Thanks in advance for all help.

[D80DSL3A]

The code in the if() statement in the delete_end() will never execute because the condition contradicts the one in the while().

while(current->next != 0)// I added the !=0 part to make my point clearer
{
if (current->next == 0)// condition conflicts with that in the while() above
{
...

The other code in the while loop looks good. The while loop will terminate with current pointing to the last node and before_current pointing to the one before that so you can move the code in the if() statement to follow the while loop.
Note that cout<<current<<"\n"; will print the memory address which current is pointing to. You probably want cout<<current->name<<"\n"; instead.

...the second pointer gets deleted because that will be pointing at the last value.

No. The second pointer, before_current, will be pointing to the node before the last one.
Delete current then assign before_current->next = 0; since this is where the list now ends.

This function will seg-fault (crash) if the list has less than 2 nodes in it. You can rewrite it to avoid this. Example:
Your code:

current = current->next;
behind_current = behind_current->next;

That will work, but I prefer:

behind_current = current;
current = current->next;

This permits starting one node closer to the front of the list. ie with before_current = 0; and current = p; If you also check for (and handle) p == 0 in the function then the seg-fault potential is eliminated.

Use a similar method in your add_before_find() to find the node (current) with the matching name, and a before_current node*, which points to the node to insert the new node after. ie, when current->name == s you want to assign:

before_current->next = n;
n->next = current;

EDIT: Watch for special cases, eg. s is the 1st name in the list.

[domaa]

Thanks a ton for the reply. I'm kicking myself for not looking at the while loop and thinking it was the pointers. We are just going over the pointer stuff in class and i figured that was where the mistake was. I do like the tip on the much cleaner looking pointers you posted.

Thanks again for the help.