deleting nodes in a linear list

This is a discussion on deleting nodes in a linear list within the C++ Programming forums, part of the General Programming Boards category; well, i was able to write the code for deleting a node in a linear list when the data contained ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Location
    delhi
    Posts
    4

    deleting nodes in a linear list

    well, i was able to write the code for deleting a node in a linear list when the data contained in it was specified....BUT how should i proceed if there are multiple occurences of the same data element,and i wish to delete all those occurences in one go....AND please guide me for deleting the even/odd occurences of that data element

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,762
    > BUT how should i proceed if there are multiple occurences of the same data element
    Keep going until you reach the end of the list, rather than bailing out when you find (and delete) the first node which matches.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2006
    Location
    delhi
    Posts
    4

    Question well that's what i also thought but could'nt write it correctly

    this is what i was able to write ,the problem is that it deletes only the first occurence of the desired number.so please help me out..... and kindly rectify the errors.
    Code:
    void remove(struct node **q)
    {
    	struct node *temp,*old;
    	int n,num;
            cout<<"\nenter the no. u want to remove\n";
    	cin>>num;
    	temp=*q;
    	if(*q==NULL)
    	{
    		cout<<"empty list,can't remove";
    	}
    	while(temp->next!=NULL)
    	{
    		if(temp->data==num)
    		{
    			if(temp==*q)  //first node
    			{
    			    (*q)=temp->next;
    			}
    
    			else
    			{
    			     old->next=temp->next;
    			}
    			free(temp);
    			return;
    		}
    		else
    		{
    			old=temp;
    			temp=temp->next;
    		}
    
           }
           cout<<"\n"<<num<<" not found\n";
    }

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,762
    So remove the return statement from within if(temp->data==num)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Jun 2006
    Location
    delhi
    Posts
    4

    doesn't help

    on removing return ,it prints "not found " everytime , and still deletes only the first occurence.Please check the looping statements....I will be GRATEFUL.( I AM ENCLOSING FULL CODE IF U HAVE TIME PLEASE TRY THIS AND KINDLY GIVE UR SUGGESTIONS)
    Code:
    #include<iostream.h>
    #include<conio.h>
    #include<process.h>
    #include<alloc.h>
    
    struct node
    {
    	int data;
    	struct node *next;
    };
    void append(struct node **);
    void display(struct node *);
    int count(struct node*);
    void addatbeg(struct node**);
    void remove(struct node**);
    void main()
    {       clrscr();
    	char ch,c;
    	struct node *p;
    	p=NULL;
    	c='1';
    	while(c=='1'||c=='1')  \
    	{
    	      cout<<"enter ur choice\n1: add\n2: display\n3: count\n"
    	            "4: add at beginning\n5: remove\n any other no. to exit\n";
    	      cin>>ch;
    
    	      switch(ch)
    	      {
    			case '1':   append(&p);
    				    break;
    
    			case '2':   display(p);
    				    break;
    			case '3':   count(p);
    				    break;
    			case '4':   addatbeg(&p);
    				    break;
    			case '5':   remove(&p);
    				    break;
    			default:    exit(0);
    	      }
    	      cout<<"\n\n\nwould u like to contnue(1/2)";
    	      cin>>c;
    
    	}
    	getche();
    }
    void append(struct node **q)
    {       int num,n,i;
    	struct node *temp,*r;
    	cout<<"how many no do u want to add at a stretch";
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    	cout<<"enter the no.";
    	cin>>num;
    
    
    
    	if(*q==NULL)
    	{
    		temp=(struct node *)malloc(sizeof(struct node));
    		temp->data=num;
    		temp->next=NULL;
    		*q=temp;
    	} //if
    	else
    	{      temp=*q;
    	       while(temp->next!=NULL)
    	       temp=temp->next;
    	       r=(struct node *)malloc(sizeof(struct node));
    	       r->data=num;
    	       r->next=NULL;
    	       temp->next=r;
    
    	}//else
    
    
    
    
    	}
    
    }//append
    
    void display(struct node *q)
    {
    	while(q!=NULL)
    	{
    		cout<<"  "<<q->data;
    		q=q->next;
    	 }
    }
    int count(struct node *q)
    {
    	int c=0;
    	while(q!=NULL)
    	{
    		c++;
    		q=q->next;
    	}
    	cout<<"the no of numbers entered are  "<<c;
    	return 0;
    }
    void addatbeg(struct node **q)
    {       int num,i,n;
    	cout<<"\nenter the no. u want to add at a stretch\n";
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    
    	cout<<"enter the no.";
    	cin>>num;
    	struct node *temp;
    	temp=*q;
    	if(*q==NULL)
    	{        temp=(struct node *)malloc(sizeof(struct node));
    		 temp->data=num;
    		 temp->next=NULL;
    		 *q=temp;
    	}
    	else
    	     {	 temp=(struct node *)malloc(sizeof(struct node));
    		 temp->data=num;
    		 temp->next=*q;
    		 *q=temp;
    	     }
          }
    
    }
    
    void remove(struct node **q)
    {
    	struct node *temp,*old;
    
    	int n,num;
    
    
    
    	cout<<"\nenter the no. u want to remove\n";
    	cin>>num;
    	temp=*q;
    	if(*q==NULL)
    	{
    		cout<<"empty list,can't remove";
    	}
    	while(temp->next!=NULL)
    	{
    		if(temp->data==num)
    		{
    			if(temp==*q)  //first node
    			{
    			    (*q)=temp->next;
    			}
    
    			else
    			{
    			     old->next=temp->next;
    			}
    			free(temp);
    
    		}
    		else
    		{
    			old=temp;
    			temp=temp->next;
    		}
    
           }
           cout<<"\n"<<num<<" not found\n";
    }
    Last edited by Salem; 06-24-2006 at 11:31 AM. Reason: fix code wrapping

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    main() is int main().

    You should use new instead of malloc() in C++.

    Maybe this loop
    Code:
    while(temp->next!=NULL)
    should be
    Code:
    while(temp!=NULL)
    Code:
    #include<alloc.h>
    What compiler are you using?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,762
    > on removing return ,it prints "not found " everytime
    Because your "logic" is now broken.
    Of course it prints this, because you always now get to the end of the list.
    What you also need is a flag to tell you whether you deleted any items at all.
    If this flag remains unset, then (and only then) should you print "not found".

    > I AM ENCLOSING FULL CODE
    We don't appreciate YELLING on message boards.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Jun 2006
    Location
    delhi
    Posts
    4

    thanks,......

    and sorry for yelling.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 11:01 PM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 02:29 AM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21