Thread: delete multiple numbers from linked list

When you find a match in the while loop of find() you then advance to the next entry in the list and delete that entry. You probably want to delemiddle(q) there instead, since q was set to point to the duplicate. Another problem there is that you advance twice in that function if you find a match, which could be causing it to skip additional duplicates. You may want to try something like:

Code:

if (q->data==p->data)
{
    delemiddle (q);
    p = q->next;
}

q=p;
p=p->next;

I didn't try to run the program yet, but that extra move could be throwing things off.

orginally posted by Exile:
if (q->data==p->data)
{
delemiddle (q);
p = q->next;
}

q=p;
p=p->next;

tried this one, but it didn't work for me.

I have modified this program a little: FREE & delemiddle functions where removed. find function has a little addition of scanning all list with all members plus free() the duplicate members.
still I dont get good results.

Code:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct ITEM  {
	int data;
	struct ITEM *next;
}item;


void display (item *S)
{
	if (S==NULL) return;
		
	printf ("%d\t", S->data);
	display(S->next);
	
}



void addfirst (item **hp, int dt)
{
	item *temp;
	temp=(item *)malloc (sizeof (item));
	if (!temp) exit (1);
	temp->data=dt;
	temp->next =(*hp);
	(*hp)=temp;
}

void add (item **hp, int dt)
{
	item  *move =(*hp);
	item *newitem;
	newitem=(item *)malloc (sizeof (item));
	if (!newitem) exit (1);
	newitem->data=dt;
	while (move->next!=NULL)
		move=move->next;
	newitem->next =move->next;
	move->next=newitem;
}


void find (item **hp)
{

	item *q=(*hp);
	item *p=(*hp)->next, *temp;
	while (q->next)
	{	
		while (p)
		{
			if (q->data==p->data)
			{				
					temp=q;
					(*hp)=p;
					free(temp);
					q=(*hp);
					p=q->next;
			}
		p=p->next;
		}
	q=q->next;
	p=p->next;
	}
}

int main (void)
{
	item *head=NULL;
	int i, dt, num;
	printf ("enter number of items\n");
	scanf ("%d", &num);
	for (i=0;i<num;i++)
	{
		printf ("enter number\n");
		scanf ("%d", &dt);
	if (head==NULL)
		addfirst (&head, dt);
	else
		add (&head, dt);
	}

	display (head);
	find (&head);
	putchar ('\n');
	display (head);
	putchar ('\n');
}

Code:

void find (item **hp)
{
	item *q=(*hp); 
	item *p=(*hp)->next, *temp;

	while (q->next)
	{//This loop appears to loop through all elements in the list
		while (p)
		{//This loop also appears to loop through all elements in the list, I don't think you need both

			if (q->data==p->data)
			{//We found a matched value, the second copy of the value, p, should be removed

					temp=q;
					(*hp)=p;
                                        //when you change the value of hp you change the head of the list
                                        //this will effectively remove all entries before p
					free(temp);
					q=(*hp);
					p=q->next;
			}
		p=p->next;
		}
	q=q->next;
	p=p->next;
	}
}

I think you are a little further from the solution on this version. When you remove a value you need to remove the value from p not q. You don't save any information on previous entries in your list so you can reset the next value in the list entry before q.

What you need to do is adjust the next value in q, then free() p, then adjust your p value and continue looping.

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp;

    while (q->next)
    {
        if (q->data == p->data)
        {//Remove the duplicate in p
            q->next = p->next;
            free(p);
        }
        else
        {//Only advance to the next list entry if no match occurs
            q = q->next;
        }
        //Always reset p so that you keep moving through the list
        p = q->next;
    }

You were OK with the delemiddle() function since thats what it did. The trouble you had was that when you advanced twice it was possible for you to try to advance past the end of the list which caused the memvory protection faults, or jump past a value that was a match.

That's perfect!
Let’s go one step further. If want to check for duplication number accross the list.This is what I wrote & I get errors.

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp;

    while (q->next)
    {
		while (p->next)
		{
			if (q->data == p->data)
			{
				temp=p;
				p = p->next;
				free(p);
				p=temp;
			}
			else
			{
				p = p->next;
			}
		}
        q = q->next;
    }
}

Code:

temp=p;
p = p->next;
free(p);
p=temp;

You set temp equal to p, then got rid of p by free()-ing it. So when you set p equal to temp you aren't getting anything useful in p, so next time through the loop when you try to read from p->next its gonna bomb with a memory protection error, since that buffer is gone.

Next issue is you aren't updating the entry in the list before p. So when you remove p, the previou list entry will still point to the entry that was removed. You will need to keep track of that previous entry to do that update.

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp, *Prev;

    while (q->next)
    {
        Prev = q; //Set the initial previous value
        while (p->next)
        {
            if (q->data == p->data)
            {
                Prev->next=p->next; //Correct the previous enty
                temp = p->next;
                p = p->next;
                free(p);
                p=temp;
            }
            else
            {
                Prev = p; //Update the previous value
                p = p->next;
            }
        }
        q = q->next;
    }
}

I think that will cover the correction of the previous entry. The whole point of that is to keep the links in the list correct.

I had to modify this function a bit, & it still doesn't fluently do the job. What i noticed was that on smaller lists: up to 5 five numbers, its OK. above it: list got lost...

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp, *Prev;
    while (q->next)
    {
        Prev = q;
        while (p)
        {
            if (q->data == p->data)
            {
                Prev->next=p; 
                temp = p->next ;
                free(p);
                p=temp;
	Prev->next=p;
	p=Prev;
           }
            else
            {
                Prev = p; 
         
            }
            p = p->next;
        }
        q = q->next;
        p=q->next;

    }
}

please help me with the fine tuning of it.

TIA,

Ronen.

After compiling and playing with the program for a bit I saw a few issues with the code. It seems you caught them and attempted some fixes. Guess thats what I get for not testing it before posting.

Anyway,

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp, *Prev;
    while (q->next)
    {
        Prev = q;
        while (p)
        {
            if (q->data == p->data)
            {
//p is the list entry you are about to get rid of.  You need to have 
//The list skip it, so this should be: Prev->next = p->next;
                Prev->next=p; 
                temp = p->next ;
                free(p);
                p=temp;
//You just free()-ed p, so its an invalid buffer you definately do not
//want to save a pointer to an invalid buffer
	Prev->next=p;
	p=Prev;
           }
            else
            {
                Prev = p; 
         
            }
            p = p->next;
        }
        q = q->next;
        p=q->next;

    }
}

Once I made those couple changes it seemed to work fine for lists of up to 20 entries. The line Prev->next = p; is the one that is causing the crashes. Next pass through the loop causes it to attempt to access the invalid buffer which causes a memory protection fault.

Aside from the two comments I have in the code block above, everything else seemed fine.

tried to run code & its still no good.

//p is the list entry you are about to get rid of. You need to have
//The list skip it, so this should be: Prev->next = p->next;

this comment is clear & I've fixed it.

//You just free()-ed p, so its an invalid buffer you definately do not
//want to save a pointer to an invalid buffer

didn't understand this one , though. what is the buttom line here?

Theres probably a few other cleanup type things that could be done. Like temp holds the same information as Pre->next, so you may be able get rid of temp.

And you aren't cleaning up all of the list properly. The original FREE() function didn't actually release the buffers. You said you got rid of that function so I can't say how that works now.

I think though the core logic you were looking for is working.

this is the code i'm rubning without Prev->next=p; & i still get errors.

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp, *Prev;

    while (q->next)
    {
        Prev = q;
        while (p)
        {
		
            if (q->data == p->data)
            {
                Prev->next=p->next; 
                temp = p->next ;
                free(p);
                p=temp;
				p=Prev;
			}
            else
            {
                Prev = p; 
            
            }
			p = p->next;
        }
        q = q->next;
		p=q->next;

    }
}

What are the numbers you enter, and what is the error you are getting?

this is a sample of input:
enter number of items
10
enter number
1
enter number
2
enter number
3
enter number
1
enter number
2
enter number
3
enter number
1
enter number
2
enter number
3
enter number
1

this is the error i get in the debbuger: "unhandalled exception in “filename: memory adress” access violation"

Code:

void find (item **hp)
{
    item *q=(*hp); 
    item *p=(*hp)->next, *temp, *Prev;

    while (q->next)
    {
        Prev = q;
        while (p)
        {
		
            if (q->data == p->data)
            {
                Prev->next=p->next; 
                temp = p->next ;
                free(p);
                p=temp;
		p=Prev;
	    }
            else
            {
                Prev = p; 
            
            }
	    p = p->next;
        }

//These updates are causing the problem, comments below
        q = q->next;
	p=q->next;

    }
}

In your example the list becomes:
1, 2, 3, 1, 2, 3, 1, 2, 3, 1
On the first pass through all the 1's are removed, so the list becomes:
1, 2, 3, 2, 3, 2, 3
On the second pass all of the 2's are removed, so the list becomes:
1, 2, 3, 3, 3
As it goes through that it removes the extra 3's, and the list is:
1, 2, 3
And q is pointing to the 3. Now q then gets set to q->next, which is NULL sine its the last entry in the list. When the loop goes through the condition looks at q->next, since q is NULL its crashing because NULL is an invalid pointer. So to fix it you can change the end of the loop to be:

Code:

if (q->next != NULL)
{
    q = q->next;
    p=q->next;
}
else
{
    break;
}

You may be able to get away with setting the condition of the outer loop to:

Code:

while ((q != NULL)&&(q->next != NULL))

but I didn't test that to see how well it worked.