Linked List Delete

[henpecked1]

I'm having trouble getting my delete function to work for a singly linked list. If I try to delete anything other than the entire list, it deletes everything up to that node.

I know there is something wrong with it, but I can't tell what it is. I would like to structure it so that it can delete any one node in the list, then I'd like to be able to print the list to the screen. btw, insert and print work fine, just not the delete. Here is the code

bool list::del(Contributor Del)
{
	 Contributor infoIn=Del;
	 
	node *pprev= plist; 
	node *ptrav= plist; 

	if (empty())	//empty list
	     {
		cout<<"The list is empty "<<endl;	
	     }

	if (pprev==ptrav)	//list beginning
	     {
				
	                   plist = ptrav->next;	  //sends plist to next node
		   delete ptrav;			  //delete Node
	      }
			
	 while((ptrav!=NULL) && (ptrav->infoIn!=Del))
	      {
		pprev= ptrav;
		ptrav= ptrav->next;
	       }			
	
                  if (pprev==ptrav) 
	                 return false;
                   else
	               if(pprev==NULL)
                                    { 
			plist= plist->next;
			delete ptrav;			
		      }
		else
		      {
			pprev->next =ptrav->next;
			delete ptrav;
		       }

	   return true;
}

[findsyntax]

Hi,
I am Rammohan from Bangalore and working as a Technical lead in big IT firm .

Solution for your answer is follows:

The way you have written is only for the deleting a node. For that also you have not verified weather the node is exist in the list or not.
Please have a look at my style fo code and use it where ever you want.

struct node *DeleteNode ( struct node *p, int node_no )
{
	struct node *prev, *curr ;
	int i;
	if (p == NULL )
	{
		printf("There is no node to be deleted \n");
	}
	else
	{
		if ( node_no > length (p))
		{
			printf("Error\n");
		}
		else
		{
			prev = NULL;
			curr = p;
			i = 1 ;
			while ( i < node_no )
			{
				prev = curr;
				curr = curr-> link;
				i = i+1;
			}
			if ( prev == NULL )
			{
				p = curr -> link;
				free ( curr );
			}
			else
			{
				prev -> link = curr -> link ;
				free ( curr );
			}
		}
	}
	return(p);
}

Regards,
Rammohan Alampally,
<snip false signature>

[VernonDozier]

I'm having trouble getting my delete function to work for a singly linked list. If I try to delete anything other than the entire list, it deletes everything up to that node.

I know there is something wrong with it, but I can't tell what it is. I would like to structure it so that it can delete any one node in the list, then I'd like to be able to print the list to the screen. btw, insert and print work fine, just not the delete. Here is the code

bool list::del(Contributor Del)
{
	 Contributor infoIn=Del;
	 
	node *pprev= plist; 
	node *ptrav= plist; 

	if (empty())	//empty list
	     {
		cout<<"The list is empty "<<endl;	
	     }

	if (pprev==ptrav)	//list beginning
	     {
				
	                   plist = ptrav->next;	  //sends plist to next node
		   delete ptrav;			  //delete Node
	      }
			
	 while((ptrav!=NULL) && (ptrav->infoIn!=Del))
	      {
		pprev= ptrav;
		ptrav= ptrav->next;
	       }			
	
                  if (pprev==ptrav) 
	                 return false;
                   else
	               if(pprev==NULL)
                                    { 
			plist= plist->next;
			delete ptrav;			
		      }
		else
		      {
			pprev->next =ptrav->next;
			delete ptrav;
		       }

	   return true;
}

I think you need to post more code or comment the code you have or something. We have no idea what these variables represent and what the classes are.

[henpecked1]

I commented, as the other code might prove overly long

bool list::del(Contributor Del)
{
	 Contributor infoIn=Del;   //Contributor is the object, infoIn is the specific object
	                                      
	node *pprev= plist;         //plist is the beginning of the list, ptrav is what some
	node *ptrav= plist;          // would call "temp" or "head", and pprev is the "tail"

	if (empty())	     // checking for empty list
	     {
		cout<<"The list is empty "<<endl;	
	     }

	if (pprev==ptrav)	                             //to delete from beginning of list
	     {
				
	                   plist = ptrav->next;	              //sends plist to next node
		   delete ptrav;                        //delete Node
	      }
			
	 while((ptrav!=NULL) && (ptrav->infoIn!=Del))
	      {
		pprev= ptrav;
		ptrav= ptrav->next;
	       }			             //These functions should search for the
	                                                             // proper item to delete, and delete it
                  if (pprev==ptrav) 
	                 return false;
                   else
	               if(pprev==NULL)
                                    { 
			plist= plist->next;
			delete ptrav;			
		      }
		else
		      {
			pprev->next =ptrav->next;
			delete ptrav;
		       }

	   return true;
}

[Salem]

Sheesh - 200 posts, and the indentation is still crap.

Your super IDE may be able to make sense of your crazy mix of spaces and tabs, but most everything else will (sooner or later) make a complete pig's ear of it.

Do everyone a favour and turn OFF tabs, and turn on smart indenting with spaces. It won't cost you any extra keystrokes, and it'll make for a much better experience all round.

Here, indented with spaces only

bool list::del(Contributor Del)
{
    Contributor infoIn=Del;     // Contributor is the object, 
                                // infoIn is the specific object
    
    node *pprev= plist;         // plist is the beginning of the list, 
                                // ptrav is what some
    node *ptrav= plist;         // would call "temp" or "head",
                                // and pprev is the "tail"

    if (empty())                // checking for empty list
    {
        cout<<"The list is empty "<<endl;    
    }

    if (pprev==ptrav)           //to delete from beginning of list
    {
        
        plist = ptrav->next;    //sends plist to next node
        delete ptrav;           //delete Node
    }
    
    while((ptrav!=NULL) && (ptrav->infoIn!=Del))
    {
        pprev= ptrav;
        ptrav= ptrav->next;
    }                           //These functions should search for the

    // proper item to delete, and delete it
    if (pprev==ptrav) 
        return false;
    else
    if(pprev==NULL)
    { 
        plist= plist->next;
        delete ptrav;            
    }
    else
    {
        pprev->next =ptrav->next;
        delete ptrav;
    }

    return true;
}

Rejoice in the consistency of formatting no matter what editor or forum you post it on.

[henpecked1]

My apologies for the formatting in my recent posts. I no longer have an IDE at work and must "troubleshoot" my errors in a text editor until I get home.

Unfortunately, it doesn't hold the formatting of an IDE well, and makes things even worse when it is copied and pasted into the forum.

I assure you my intent is not to confuse or irritate, nor bring your wrath down upon me. Your experience in this subject, and indeed on this board is vastly superior to mine and I only ask your patience since even after 200 posts, I am, by all standards, still a beginner in both.

[VernonDozier]

bool list::del(Contributor Del)
{
    Contributor infoIn=Del;     // Contributor is the object, 
                                // infoIn is the specific object
    
    node *pprev= plist;         // plist is the beginning of the list, 
                                // ptrav is what some
    node *ptrav= plist;         // would call "temp" or "head",
                                // and pprev is the "tail"

Contributor is NOT an object. It looks like Contributor is a class or a struct. What relationship it has to the node class/struct is not clear. plist appears to have a type of node* and points to the first node in the list.

It appears that after this code is executed, pprev, plist, and ptrav are all pointing to the same node.

if (pprev==ptrav)           //to delete from beginning of list
    {
        
        plist = ptrav->next;    //sends plist to next node
        delete ptrav;           //delete Node
    }

Since ptrav and pprev will always point to the same node at this point, this if statement is unnecessary since it will always evaluate to true. plist now points to the second node in the list. Is this if statement supposed to ALWAYS execute? If not, I'd put some debugging statement inside of it that displays something and find out if it is ever skipped. It appears to me that it is never skipped.

while((ptrav!=NULL) && (ptrav->infoIn!=Del))
    {
        pprev= ptrav;
        ptrav= ptrav->next;
    }

You define infoIn as type Contributor above. It also appears to be a data member of the node class/struct. So does each node store data of type Contributor and infoIn is the Contributor member of the node class? The function is passed not the node to delete itself but rather the data that the node to delete contains? If you aren't careful, using the same name for both a specific class/struct object and a class/struct data member can get confusing. The infoIn object form this line:

Contributor infoIn=Del;

is never used as far as I can see, so can be deleted. It's different from the infoIn from this line:

while((ptrav!=NULL) && (ptrav->infoIn!=Del))

I think you need to provide at least the header of the Contributor, list, and node classes/structs. Not the method implementation code itself, but the header that lists at least what each struct/class's data members are and how they relate to each other. Posting the entire header with the method declarations included could be helpful.

[henpecked1]

Vernon,

Here is the code you requested. I would have posted it all, but it seemed like it would be terribly long, so I attached it instead.

[VernonDozier]

This won't compile. contributor.cpp has this line:

#include "Contributor.h"

You haven't provided this file.

[henpecked1]

bah...I attached the wrong cpp file. try this one

and it should be asking for ContributorClass.h no space, add a space, whichever...I caught it after I attached it

[VernonDozier]

From NodeClass.h:

class node
{
	public:
		node();
		Contributor infoIn;
		node *next;
		node (Contributor i, node *pnext) 
		{
			infoIn=i;
			next=pnext;
		}
		~node();

};

You have no data member in the node class called pnext or pNext. The pnext in red above is NOT a data member of the node class.

From NodeClass.cpp:

node::node()
{
	pNext=NULL;
}

This line above is assuming that there is a data member in the node class called pNext. There is not, so I assume you are getting an error here when compiling.

[henpecked1]

okay, I made pnext a data member of node, and I corrected all the pNexts and made them pnext.

Now, it will print all the inserts fine, but then the program ends and gives me an error dialog box killing the program

[VernonDozier]

okay, I made pnext a data member of node, and I corrected all the pNexts and made them pnext.

Now, it will print all the inserts fine, but then the program ends and gives me an error dialog box killing the program

So you added line 7?

If so, I hope you are not still using the name pnext in lines 8 and 11 because that could be confusing to have a function parameter with the same name as a data member. You should probably post your updated code.

class node
{
	public:
		node();
		Contributor infoIn;
		node *next;
                node *pnext;
		node (Contributor i, node *pnext) 
		{
			infoIn=i;
			next=pnext;
		}
		~node();

};

[henpecked1]

well...yes...all I did was add line 7.

I'm really making a mess of this aren't I? Could that be what's killing the program when it runs?

The more I change, the more lost I get

#include "Contributor Class.h"
#include <iostream>

using namespace std;

class node
{
     public:
	node();
	node (Contributor i, node *pnext); 
	~node();

	Contributor infoIn;
	node *next;
	node *pnext;

};

This is now the header, but after your last post, I'm sure it's not right

and the node cpp

#include "NodeClass.h"

node::node()
{
     pnext=NULL;
}

node::node(Contributor i, node *pnext)
{
     infoIn=i;
     next=pnext;
}

node::~node()
 {
     pnext=NULL;
 }

Here is the list header

#include "NodeClass.h"

using namespace std;


class list
{
public:
	list();
	list(const list &rhs);	
	bool empty();
	bool insert(Contributor In);
	bool del(Contributor Del);
	friend ostream & operator << (ostream &out ,list & listin);	
	~list();
	node *plist;
};

[VernonDozier]

well...yes...all I did was add line 7.

I'm really making a mess of this aren't I? Could that be what's killing the program when it runs?

The more I change, the more lost I get

#include "Contributor Class.h"
#include <iostream>

using namespace std;

class node
{
     public:
	node();
	node (Contributor i, node *pnext); 
	~node();

	Contributor infoIn;
	node *next;
	node *pnext;

};

This is now the header, but after your last post, I'm sure it's not right

and the node cpp

#include "NodeClass.h"

node::node()
{
     pnext=NULL;
}

node::node(Contributor i, node *pnext)
{
     infoIn=i;
     next=pnext;
}

node::~node()
 {
     pnext=NULL;
 }

Well, what does pnext represent? Generally a linked list will store two things. One, it stores some data, which I assume is what infoIn is. Two, it stores a pointer to the next node in the list, which I assume is what next represents. I don't know what pnext represents. Generally, and this can vary, you'll have a node class that looks something like this (to make things easy, I'm going to make everything public, even though usually some things are private.

class node
{
    public:
        // data members
        Data data;
        node* next;

        // constructors and other methods
};

Data could be any class or struct of some type. It's the data that you are storing. In your case you would probably replace:

Data data;

with:

Contributor infoIn;

You can have a variety of different insertion and deletion functions and constructors, all of which will be passed zero or more parameters. The names of these parameters should NEVER be next or infoIn to avoid confusion.

For example, if you wanted to insert a new node with data at the end of the list, you might have a function like this:

node* node::Insert (node* frontNode, Contributor infoin);

Note infoin versus infoIn . C++ is case-sensitive, so the names are different. Also notice that the node class DOES NOT contain the front node in the linked list. Somewhere this needs to be kept track of, but not in the node class. If the node class has an Insert method, it needs to have that information passed to it or have access to it in some other way. In this case, it's passed. On the other hand, you could have a list class (not a node class) that does store the front node:

class list
{
    public:
        node* frontnode;
        // constructors and other methods
};

The point of all this is to point out that what you shouldn't store more than you have to in the node class and any parameters you pass to any constructor or any other method must have a different name than any data member of the node class to avoid confusion.

Hopefully this helps clarify rather than confuse. :)

[henpecked1]

so as usual..I overcomplicated it for myself...ookay...try again I guess...lol

do I even need a copy constructor in the node class?

and I took out the references to next in the node class.

to explain my pointer variables...

plist is the head of the list

ptrav is the front, head, temp pointer that traverses the nodes looking for the correct insertion/deletion point

pprev is the rear, tail, temp2 pointer that keeps track of the previously visited node

pnext is the pointer to the next node

Here is the revised header class

#include "Contributor Class.h"
#include <iostream>

using namespace std;

class node
{
      public:
	node();
	node (Contributor i, node *pnext);    //do I need this?  is it even written correctly?
	~node();

	Contributor infoIn;                  // data to be stored in the node
	node *pnext;                         // to store info to next node

};

and the cpp file

#include "NodeClass.h"

node::node()
{
     pnext=NULL;
}

node::node(Contributor i, node *pnext)
{
     infoIn=i;
}

node::~node()
{
}

[VernonDozier]

Is there any order to the Contributor class? If so, is this to be an ordered linked list, as in

1 --> 6 --> 14 --> 20 --> 25

the order being determined by the "value" of Contributor? In that case, when you insert, you could be inserting into the middle of the list. Or are you always inserting to the beginning or the end of the list. I saw earlier that you have a list class in addition to the node class. So consider having your Delete and Insert functions be list functions. list has access to plist, where node does not unless it is passed plist as a parameter. Regarding what you should have in your node class, quite possibly have only constructors and a destructor (assuming data members are public). Which constructors you need will depend on the program, but I'd consider these could work:

node (); // default constructor
node (const Contributor& con);  // constructor

You may want to just go with these two and not have a node copy constructor. I think at this stage it's easier to just assign pnext to be null in both of these constructors.

If you make things private later, you'll need to add some methods, but simplify life and keep them public for now, in my opinion.

For sure, do not have this function:

node::node(Contributor i, node *pnext)

Remember the rule about not naming your parameters with the same name as the data member name. If you did want to keep it (I probably wouldn't), rename the parameter:

node::node(Contributor i, node *pNext)
{
    pnext = pNext;
    infoIn =  new Contributor(i); // or some other code
                                     // depending on need
}

Frankly, I'd keep my node class minimal and have the list::Insert and list::Delete function handle the responsibility of making sure plist and pnext point to the correct node, so I might just have the list class have the two constructors and destructor, and later if you make things private, some "get" and "set" functions in the node class.

The important thing is to decide what class has what responsibility and stick with it. I'd have the list class do most of the work. There's no right or wrong answer, except if you can't decide what class does what, in which case you'll almost certainly have problems. You need to decide whether this is an ordered or unordered linked list. If it's unordered, stick any new node into the front or the back of the list. Sticking it in the front would mean less traversal. If it's ordered and you're inserting, traverse till you find a node whose Contributor value is greater than or equal to the new node's Contributor value and stick it in front of that node. If there is no node that's greater than or equal, stick the new node in the back. Any insertion or deletion will require tidying up of the plist and/or pnext pointers.

[henpecked1]

The list class does indeed do most of the work. All my list manipulation happens there (insert etc)

It is an ordered list, and the insert puts everything in the correct order. With the current files, the delete gives no outward appearance that it's doing anything and then the OS kills the file. I'm quite sure this has to do with what you're telling me.

I'll change the node class again and we'll see where we end up this time. Just a passing thought, could my contributor class files be interfering some how?

[VernonDozier]

The list class does indeed do most of the work. All my list manipulation happens there (insert etc)

It is an ordered list, and the insert puts everything in the correct order. With the current files, the delete gives no outward appearance that it's doing anything and then the OS kills the file. I'm quite sure this has to do with what you're telling me.

I'll change the node class again and we'll see where we end up this time. Just a passing thought, could my contributor class files be interfering some how?

Anything's possible, but I haven't seen your updated node and list classes with the constructors and Insert and Delete functions. It's one of those things where you have to either post the new code each time or explain that you've done nothing to change the old code. Fastest way is probably to just zip all of the files each time and then post the zip file each time you post if you've changed anything at all.

[henpecked1]

Vernon, thank you for your help. I finally figured it out. I was using assignment in a couple places where I meant to be doing comparison/equality