C - delete an element from singly linked list

Question

I can't figure out where the problem is,

And why del function is not working as expected?

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

typedef struct list List;

struct list
{
    int data;
    List* next;
};

void prl(List* head);
void ins(List** head, int value);
void del(List** head, int value);

int main()
{
    List* head = NULL;

    ins(&head, 10);
    ins(&head, 50);
    ins(&head, 20);
    ins(&head, 150);
    ins(&head, 120);

    del(&head, 150);

    prl(head);

    //freeing dynamically allocated memory for each nodes

    while(head!=NULL)
    {
        List* t = head;
        head = head->next;
        free(t);
    }

    return 0;
}

void prl(List* head)
{
    if(head == NULL)
        printf("List is empty\n");
    else
    {
        while(head != NULL)
        {
            printf("%d ", head->data);
            head = head->next;
        }
     }
}

void ins(List** head, int value)
{
    List* node = malloc(sizeof *node);

    node->data = value;
    node->next = NULL;

    node->next =*head;
    *head = node;

}


void del(List** head, int value)
{
    List* p,*q;
    p=q=*head;

    if((*head)->data == value)
    {
        *head = (*head)->next;
        free(p);
        return;
    }
    else
    {
        while(p->next != NULL)
        {
            if(p->data == value)
            {
                q->next = p->next;
                free(p);
            }
            else
            {
                q = p;
                p = p->next;
             }
        } // while loop ends

    } // outer else ends

} // del function ends

After running this, output is blank and I think something (logically) is wrong inside del function outer else loop, however the first value can be deleted by using this function.

If you haven't used a debugger before, now is the perfect time. With a debugger you can step over the code, line by line, while monitoring variables and their values. You can of course also step into functions as they are called. When you have problems like this, you should first try to use a debugger to try and figure out the problem. — Some programmer dude, Feb 02 '17 at 13:59
Why does your `del` function only delete one copy of the value if it occurs at the head of the list? But if it doesn't occur at the head of the list, it iterates the whole list and tries to delete all copies of the value? — Kaz, Feb 02 '17 at 13:59
The purpose of well-formatted code is so that you and others can read and understand it. Please format your code next time. — Paul Ogilvie, Feb 02 '17 at 14:01
@Someprogrammerdude I haven't actually used debugger, in fact it's new to me — some user, Feb 02 '17 at 14:04

score 2 · Answer 1 · answered Feb 02 '17 at 14:06

2

Despite my comment I decided to help you.

Lets take a look at these lines:

while(p->next != NULL)
{
    if(p->data == value)
    {
        q->next = p->next;
        free(p);
    }
    else
    {
        // Irrelevant...
    }
}

Lets say that the condition inside the loop, p->data == value, happens to be true, what happens then? You make q->next point to p->next, that's probably okay, and then you continue the loop without making p point anywhere else.

When the loop continues p is pointing to the data you just called free on, so dereferencing p with e.g. p->next in the loop condition will lead to undefined behavior.

The solution is to update p and q appropriately.

answered Feb 02 '17 at 14:06

Some programmer dude

400,186
35
402
621

thanks for let me understanding easily, I think using `return;` statement is fixing my issue (for deletion of first occurrence), isn't it? – some user Feb 02 '17 at 14:15
1

@someuser If you only want to remove the first matched element, then yes you should return (or at least exit the loop). – Some programmer dude Feb 02 '17 at 14:27

score 1 · Accepted Answer · answered Feb 02 '17 at 13:59

1

I think you did not add a return statement here:

if(p->data == value)
    {
        q->next = p->next;
        free(p);
        return;
    }

answered Feb 02 '17 at 13:59

Sapna Jindal

412
3
11

1

That depends on whether he wants to delete only the first appearance of the target value, or all of them. – John Bollinger Feb 02 '17 at 14:12
@JohnBollinger yes you are right, it is fixing for deletion of the first occurrence of target value. – some user Feb 02 '17 at 14:17

score 0 · Answer 3 · edited May 09 '21 at 16:51

0

while(p->next != NULL) { 
  if(p->data == value) { 
    q->next = p->next; 
    free(p); 
  } else { 
    q = p->link; //here.... 
    p = p->next; 
  }
}

edited May 09 '21 at 16:51

Laurel

5,965
14
31
57

answered May 08 '21 at 05:14

Amarjit Yanglem

1

C - delete an element from singly linked list

3 Answers3