delete elements in a singular linked list

in this code i am deleting the element in the linked list

11->12->13->14->15->12->16

if i want to delete 12 it deletes only the first time occurrence element i.e o/p wll be

11->13->14->15->12->16

but i want to delete all the occurrence of 12, how to do that?

can anyone give me some inputs?

    #include<stdio.h>
    #include<stdlib.h>
    void insertbeg();
    void delpos();
    void display();
    struct node
    {
            int info;
            struct node *link;
    }*first=NULL;

    struct node *create();
    int item,key;
    main()
    {
            int choice;
            while(1)
            {
                            printf("\nchoices are:\n");
                            printf("\n1.Insertbeg\n 2.delpos\n 3.display\n 4.exit\n");
                            printf("Enter U'r choice: ");
                            scanf("%d",&choice);
                            switch(choice)

                            {
                                            case 1: insertbeg(); break;
                                            case 2: delpos(); break;
                                            case 3: display(); break;
                                            case 4: exit(1);
                          default: printf("INVALID CHOICE TRY AGAIN\n");
                           }
            }
    }
    struct node *create()
    {
            struct node *new;
            new=(struct node*)malloc(sizeof(struct node));
            return(new);
    }
    void insertbeg()
    {
            struct node *new;
            new=create();
            printf("Enter element to be inserted: ");
            scanf("%d",&item);
            if(first==NULL)
            {
                            new->info=item;
                            new->link=NULL;
                            first=new;
            }
            else
            {
                            new->info=item;
                            new->link=first;
                            first=new;
            }
    }


    void delpos()
    {
            int key;
            struct node *temp,*prev;
            if(first==NULL)
            {
            printf("LIST IS EMPTY\n");
                            return;
            }
            else
            {
                            temp=first;
                            printf("Enter the KEY element which is to be deleted: ");
                            scanf("%d",&key);
                       /*     while(temp->info!=key&&temp->link!=NULL)
                    {
                                            prev=temp;
                                            temp=temp->link;
                            }
                            if(temp->info==key)
                     {
                                            prev->link=temp->link;
                                            free(temp);
                            }
                            else
                                          printf("key element not found in the list\n");
            */

                while(temp->link != NULL)
                    {
                        if(temp->info == key)
                        {
                        prev->link = temp->link;
                        free(temp);
      开发者_开发技巧                  temp = prev->link;
                        temp = temp->link; 
                        }
                        else
                            temp = temp->link;
                    }
            }
    }

    void display()
    {
            struct node *temp;
            temp=first;
            if(temp==NULL)
            {
                            printf("LIST IS EMPTY\n");
                            return;
            }
            else
            {
                            printf("Elements in Linked Lists: ");       

            while(temp!=NULL)
                            {
                                           printf("%d->",temp->info);
                                            temp=temp->link;
                            }
            }
    }

---

I can find two problems with your code but none of them would exhibit a problem with your sample input.

1-

while(temp->link != NULL)

Should be

while(temp!=NULL)

2- The temp = temp->link; is superfluous in the

if(temp->info == key)
{
   prev->link = temp->link;
   free(temp);
   temp = prev->link;
   temp = temp->link; 
}

and skips one element.

---

If you delete the first element, then you never enter here while(temp->info!=key&&temp->link!=NULL) and prev is uninitialized and prev->link will cause segfault (because you dereference uninitialized pointer).

So you probably get it here: prev->link=temp->link;

---

I think here prev->link=temp->link prev is dangling. If its the first node, just move the pointer and free

---

The problem is in delpos:

prev->link=temp->link;

When you are at the first element of the list (i.e. 11), prev has not been set to anything. The while loop

while(temp->info!=key&&temp->link!=NULL)

Is never executed in this case, and hence prev remains unset.

Another problem is that when you remove the first element of the list, the variable first will still point to the original first element of the list, not to the second element.

One solution would be something like

 ...

 temp=first;
 prev=NULL;                  /* Added */
 printf("Enter the KEY element which is to be deleted: ");
 scanf("%d",&key);
 while(temp->info!=key&&temp->link!=NULL)
 {
     prev=temp;
     temp=temp->link;
 }
 if(temp->info==key)
 {
     if (prev==NULL)         /* Added */      
         first=temp->link;   /* Added */
     else                    /* Added */
         prev->link=temp->link;
     free(temp);
 }

 ...

---

Remove the check temp->info!=key from the file and do it with an if inside the while body would be a starter.

---

And finally,

Doesn't prev need assigning?

I can see it assigned in the commented out section but no where else. And obviously need a null check around it in case the first element matches the key.

---

The main problem with your delete code is that the first element needs to be considered as a special case, since that first is potentially the node that is about to be deleted and so first might need to be updated with a new node. This could be solved by the use of a double pointer like struct node ** temp = &first; . However I tried to be close to your original post.

    // special condition if first should be removed.
    temp = first;
    while ( temp != NULL && temp->info == key ){
        first = temp->link;
        free(temp);
        temp = first;
    }

    // Here temp->info should not be removed(or it is NULL)
    // lets look at temp->link->info and remove temp->link
    while (temp!=NULL && temp->link != NULL) {
        if (temp->link->info == key) {

            struct node *to_free = temp->link;
            // temp checks the next node.
            temp->link = temp->link->link;
            free(to_free);
        } else {
            // next link
            temp = temp->link;
        }
    }

Note that prev is unnecessary.