Programming Forums - Linked List problem

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Linked List problem - Deleting a node (http://www.programmingforums.org/showthread.php?t=14745)

Linked List problem - Deleting a node

I have created a simple Linked List. The list stores a username, a IP address associated with the username, and a socket associated with the username. Most of the functions I have created for it work fine except the del() function. I wanted this function to delete a node, but it doesn't delete the node. Could someone show me where I went wrong?

Using OpenWatcom compiler on Windows XP.

Here is the code:

#ifndef LIST_H
#define LIST_H
 
struct user
{
        char uname[50];
        char address[15];
        int socket;
        user *next;
};
 
user *head_ptr;
user *current_ptr;
 
 
void move_current_to_end()
{
        current_ptr=head_ptr;
 
        while(current_ptr->next!=NULL)
        {
                current_ptr=current_ptr->next;
        }
}
 
 
void add_user(char *name, char *addr, int sock)
{
        user *new_rec_ptr;
 
        new_rec_ptr=new user;
 
        strcpy(new_rec_ptr->uname,name);
        strcpy(new_rec_ptr->address,addr);
        new_rec_ptr->socket=sock;
 
        move_current_to_end();
        current_ptr->next=new_rec_ptr;
}
 
 
 
 
void disp()
{
        current_ptr=head_ptr;
        cout<<"--USERS--ONLINE--\n";
        do
        {
                cout<<"-----------------------\n";
                cout<<"username: "<<current_ptr->uname<<endl;
                cout<<"IP: "<<current_ptr->address<<endl;
                cout<<"socket: "<<current_ptr->socket<<endl;
                cout<<"-----------------------\n";
        }while(current_ptr!=NULL);
}
 
void del(char *name)
{
        //user *temp_ptr;
 
        current_ptr=head_ptr;
 
        while(current_ptr!=NULL)
        {
                if(strcmp(current_ptr->uname,name)==0)
                {
                        delete [] current_ptr;
                        //current_ptr=temp_ptr;
                        break;
 
 
                }        
                else
                {
                        current_ptr=current_ptr->next;        
                }
        }
 
}
 
int search(char *name)
{  
    current_ptr=head_ptr;
 
    while(current_ptr != NULL)
    {
                if(strcmp(current_ptr->uname,name)==0)
                {       
                        return -1;                
                }
                else
                {
                        current_ptr=current_ptr->next;
                }
    }
 
        return -2;
}
 
#endif

Re: Linked List problem - Deleting a node

Quote:

OpenWatcom compiler

lolwhat

Tip: This is the C forum.

Re: Linked List problem - Deleting a node

The textbook response to linked list problems is to draw it out on paper, then walk through your code on said paper and see what happens. Your problem is fairly easy if you're looking at a picture. Hint: you're breaking the chain instead of removing a link.

Side note about style: using a global variable for current_ptr is a poor practice. Your code would be better if you declared a local variable in each function where you iterate over the list.

Re: Linked List problem - Deleting a node

Quote:

Originally Posted by peaceofpi (Post 138391)

Quote:

OpenWatcom compiler

lolwhat

Tip: This is the C forum.

Yeah, and he posted C code, didn't he? And he's compiling with the Open Watcom C++/Fortran compiler.

Re: Linked List problem - Deleting a node

peaceofpi was most likely referring to the author's use of cout (part of the C++ standard) and the "new" operator (C++ only), among other possible inconsistencies with C.

Re: Linked List problem - Deleting a node

> Could someone show me where I went wrong?
Well you had a linked list which looked like this

+=====+      +=====+      +=====+      +=====+      +=====+            

|  A  |----->|  B  |----->|  C  |----->|  D  |----->|  E  |----->NULL

+=====+      +=====+      +=====+      +=====+      +=====+

What you should end up with, after deleting 'D' is

+=====+      +=====+      +=====+      +=====+            

|  A  |----->|  B  |----->|  C  |----->|  E  |----->NULL

+=====+      +=====+      +=====+      +=====+

But instead, you've got

+=====+      +=====+      +=====+      

|  A  |----->|  B  |----->|  C  |----->junk

+=====+      +=====+      +=====+

You can't just blow away the node you want to delete, you need to repair the pointer chain to jump over the node you're going to delete, before you delete it.

You also need some extra care when the node being deleted is also the head node in the list.

Re: Linked List problem - Deleting a node

Sorry, Salem, you missed the real problem ...

There is also a problem that will emerge when creating the list. head_ptr is never initialised so it points to anything valid (i.e. a data structure). The first call to add_user will therefore introduce undefined behaviour. The code that creates a struct pointed at by current is fine, although it stores the address of the created struct in a local variable. Then move_current_to_end() is called, which does;

current_ptr=head_ptr;

while(current_ptr->next!=NULL)

{

    current_ptr=current_ptr->next;

}

which is chock full of undefined behaviour since head_ptr has never been initialised..... if current_ptr does not point at anything valid, accessing the value of current_ptr->next yields undefined behaviour.

Re: Linked List problem - Deleting a node

Ok, I have revised the code a bit, and I still having problems with the del() function.

#ifndef LIST_H
#define LIST_H
 
struct user
{
        char uname[50];
        char address[15];
        int socket;
        user *next;
};
 
user *head_ptr;
user *current_ptr;
 
 
void move_current_to_end()
{
        current_ptr=head_ptr;
 
        while(current_ptr->next!=NULL)
        {
                current_ptr=current_ptr->next;
        }
}
 
 
//initializes linked list with some junk values
void init()     
{
        head_ptr = new user;
 
        strcpy(head_ptr->uname, "BEGIN");
        strcpy(head_ptr->address, "0.0.0.0");
        head_ptr->socket = 0;
        head_ptr->next = NULL;
}
 
void add_user(char *name, char *addr, int sock)
{
        user *new_rec_ptr;
 
        new_rec_ptr=new user;
 
        strcpy(new_rec_ptr->uname,name);
        strcpy(new_rec_ptr->address,addr);
        new_rec_ptr->socket=sock;
 
        move_current_to_end();
        current_ptr->next=new_rec_ptr;
}
 
 
 
 
void disp()
{
        current_ptr=head_ptr;
        cout<<"--USERS--ONLINE--\n";
        do
        {
                cout<<"-----------------------\n";
                cout<<"username: "<<current_ptr->uname<<endl;
                cout<<"IP: "<<current_ptr->address<<endl;
                cout<<"socket: "<<current_ptr->socket<<endl;
                cout<<"-----------------------\n";
                current_ptr=current_ptr->next;
        }while(current_ptr!=NULL);
}
 
void del(char *name)
{
        user *temp_ptr;
 
        current_ptr=head_ptr;
 
        while(current_ptr!=NULL)
        {
                if(strcmp(current_ptr->uname,name)==0)
                {
                        temp_ptr=current_ptr->next; //store node after current
                        delete current_ptr;  //delete current node
                        current_ptr=temp_ptr;   //set current to temp
 
                        break;
                }        
                else
                {
                        current_ptr=current_ptr->next;        
                }
        }
 
}
 
int search(char *name)
{  
    current_ptr=head_ptr;
 
    while(current_ptr != NULL)
    {
                if(strcmp(current_ptr->uname,name)==0)
                {       
                        return -1;                
                }
                else
                {
                        current_ptr=current_ptr->next;
                }
    }
 
        return -2;
}
 
 
#endif

Re: Linked List problem - Deleting a node

You need to keep track of the last_ptr. Then when you delete, last_ptr.next is loaded with current_ptr.next before you delete current_ptr.

Re: Linked List problem - Deleting a node

Thanks for all of the help, I finally got it to work. Here is the code:

#ifndef LIST_H
#define LIST_H
 
#include<string>
#include<iostream>
 
struct user
{
        char uname[50];
        char address[15];
        int socket;
        user *next;
};
 
user *head_ptr;
user *current_ptr;
 
 
 
void move_current_to_end()
{
        current_ptr=head_ptr;
 
        while(current_ptr->next!=NULL)
        {
                current_ptr=current_ptr->next;
        }
}
 
void init()
{
        head_ptr = new user;
 
        //head_ptr->next = NULL;
}
 
void add_user(char *name, char *addr, int sock)
{                
        user *new_rec_ptr;
 
        new_rec_ptr=new user;
        if(new_rec_ptr!=NULL)
    {
                strcpy(new_rec_ptr->uname,name);
                strcpy(new_rec_ptr->address,addr);
                new_rec_ptr->socket=sock;        
                move_current_to_end();
                current_ptr->next=new_rec_ptr;
        }
        else
        {
                cout<<"memory error, new user cannot be added\n";
        }
}
 
 
 
 
void disp()
{
        current_ptr=head_ptr;
        cout<<"--USERS--ONLINE--\n";
        do
        {
                cout<<"-----------------------\n";
                cout<<"username: "<<current_ptr->uname<<endl;
                cout<<"IP: "<<current_ptr->address<<endl;
                cout<<"socket: "<<current_ptr->socket<<endl;
                cout<<"-----------------------\n";
                current_ptr=current_ptr->next;
        }while(current_ptr!=NULL);
}
 
 
void delete_from_head()
{
    current_ptr=head_ptr;
    if(head_ptr->next==NULL)
    {
        head_ptr=current_ptr->next;
    }
    else
    {
        head_ptr=NULL;
    }
    delete current_ptr;
}
 
void delete_from_end(user *previous_ptr)
{
    delete current_ptr;
    previous_ptr->next=NULL;
    current_ptr=head_ptr;
}       
 
void delete_from_middle(user *previous_ptr)
{
    previous_ptr->next=current_ptr->next;
    delete current_ptr;
    current_ptr=head_ptr;
}
 
void delete_node(user *previous_ptr)
{
    if(current_ptr==head_ptr)
    {
        delete_from_head();
    }
    else
    {
        if(current_ptr->next==NULL)
        {
            delete_from_end(previous_ptr);
        }
        else
        {
            delete_from_middle(previous_ptr);
        }
    }
}
 
 
void del(char *name)
{
        user *prev_ptr;
 
        prev_ptr=NULL;
        current_ptr=head_ptr;
 
 
        while((strcmp(current_ptr->uname, name)!=0)&&(current_ptr!=NULL))
    {
        prev_ptr=current_ptr;
        current_ptr=current_ptr->next;
    }
 
    if(current_ptr!=NULL)
    {
        delete_node(prev_ptr);
    }
}
 
 
 
 
 
int search(char *name)
{  
    current_ptr=head_ptr;
 
    while(current_ptr != NULL)
    {
                if(strcmp(current_ptr->uname,name)==0)
                {       
                        return -1;                
                }
                else
                {
                        current_ptr=current_ptr->next;
                }
    }
 
        return -2;
}
 
 
#endif