Linked list program question..

[SKP]

Hi,
I am trying do a basic liked list program, where i am adding nodes at
the end. Adding part is fine, but removing part is not working.
Here is the code:
---------

#include<string>
class List {

struct node {
string *s;
node *next;
} *head;
public:
List() { head = 0;};
~List() {delete head;}
void Add(string *str);
string *Remove();
void print();
};
void List::Add(string *str)
{
cout<< *str <<endl;
if(head) {
struct node* cnode = head;
while(cnode->next) cnode=cnode->next;
struct node *temp = new struct node;
temp->s = str;
temp->next = NULL;
cnode->next = temp;
}
else {
head = new struct node;
head->s = str;
head->next = NULL;
}
}
string *List::Remove()
{
struct node *cnode = head;
while(cnode->next) {
cnode = cnode->next;
}
string *p = cnode->s;
cnode = NULL;
delete cnode;
return p;
}
void List::print()
{
struct node *cnode = head;
while(cnode) {
cout<< *(cnode->s)<<endl;
cnode = cnode->next;
}
}
int main()
{
string StrObjs[] = {"str1","str2","str3","str4"};
List L;
const int total =sizeof(StrObjs)/sizeof(*StrObjs);
for(int i = 0;i < total;i++)
L.Add(&StrObjs[i]);
L.print();
string *temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
L.print();
return 0;
}
---------

The output it gives is:

--
str1
str2
str3
str4
str1
str2
str3
str4
popped element = str4
popped element = str4
popped element = str4
popped element = str4
str1
str2
str3
str4
--------

which is not the expected one. Please help in correcting it and any
suggestions on improving this program are appreciated.

Thanks in adv,

SKP.

[Rolf Magnus]

SKP wrote:

Hi,
I am trying do a basic liked list program, where i am adding nodes at
the end. Adding part is fine, but removing part is not working.
Here is the code:
---------
I'll add some style comments, too.
#include<string>
class List {

struct node {
string *s;
Why do you use pointers to strings?
Also, it should be std::string.
node *next;
} *head;
public:
List() { head = 0;};
List() : head(0) {}
~List() {delete head;}
void Add(string *str);
Again, I wouldn't use a pointer here. The string should also be const. A
reference would be best, so it would be:

void Add(const std::string& str);
string *Remove();
void print();
This function doesn't modify your object. Such functions should be made
const, like:

void print() const;
};
void List::Add(string *str)
{
cout<< *str <<endl;
if(head) {
struct node* cnode = head;
You can leave out the struct keyword here (and in all the following uses of
your node struct). It's superfluous.
while(cnode->next) cnode=cnode->next;
struct node *temp = new struct node;
temp->s = str;
temp->next = NULL;
cnode->next = temp;
}
else {
head = new struct node;
head->s = str;
head->next = NULL;
}
}
string *List::Remove()
{
struct node *cnode = head;
while(cnode->next) {
cnode = cnode->next;
}
string *p = cnode->s;
cnode = NULL;
delete cnode;
Well, here's your problem. First, you overwrite your cnode pointer with a
null pointer, then _afterwards_, you try to delete it. So in fact, you
delete a null pointer, which does nothing. The object that cnode was
pointing to before is still existing.
What you need to do is remember the pointer to the previous node, because
that one's next pointer needs to be deleted and then set to null. And that
means you can't just exchange the cnode = NULL and the delete line, because
cnode is not the last node's next pointer, but a copy of it. I don't give
you a solution to save you the learning experience.
return p;
}
void List::print()
{
struct node *cnode = head;
while(cnode) {
cout<< *(cnode->s)<<endl;
cnode = cnode->next;
}
}
int main()
{
string StrObjs[] = {"str1","str2","str3","str4"};
List L;
const int total =sizeof(StrObjs)/sizeof(*StrObjs);
for(int i = 0;i < total;i++)
L.Add(&StrObjs[i]);
L.print();
string *temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
cout<<"popped element = "<<*temp<<endl;
cout<<"popped element = "<<*temp<<endl;
temp = L.Remove();
L.print();
return 0;
}
---------