delete node(s) in a singly linked list in c

Question

I created a singly linked list that accepts value from input. I tried to delete certain nodes from the input but the code isn't executing as intended.

here is my code

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

struct NODE {
     int value;
     struct NODE *prev;
};

struct NODE* head = NULL;

void insert(int data) {
   
    struct NODE *p;
    p = malloc(sizeof(struct NODE));
    
   (*p).value = data;
    
   
   (*p).prev = head;
    
   
   head = p;
}

void addBack(struct node **head, int val)
{
    
    struct NODE *newNode;
    newNode = malloc(sizeof(struct NODE));
    (*newNode).value = val;
    (*newNode).prev = NULL;

   
    if(*head == NULL)
         *head = newNode;
    else
    {
        struct NODE *headNode = *head;
        while((*headNode).prev != NULL)
        {
            headNode = (*headNode).prev;
        }
        (*headNode).prev = newNode;
    }

}
void printList(struct NODE* head)
{
        while (head != NULL) {
            
        printf("%d",(*head).value);
        
        if((*head).prev!= NULL){
            printf(",");
        }
                head = (*head).prev;
        }
}

void deleteNode(struct NODE** head, int new)
{
    
    struct NODE *tmp = *head, *sa;
    if (tmp != NULL && tmp->value == new) {
        
        free(tmp); 
        return;
    }
    while (tmp != NULL && tmp->value != new) {
        sa = tmp;
        tmp = tmp->prev;
    }
    if (tmp == NULL)
        return;
    sa->prev = tmp->prev;
    free(tmp); 
}
int main()
{
    int num;
    scanf("%d", &num);
    int array[num];
    
    
    for(int i = 0; i < num; i++){
        scanf("%d", &array[i]);
    }
    
    for(int j = num-1; j >= 0; j--){
    insert(array[j]);
    }
    
    int x;
    scanf("%d", &x);
    addBack(&head, x);
    deleteNode(&head, 3);
    printList(head);

    return 0;
}

9 is the size of the list, and the random number 3 on the third line is just a new integer that gets added to the list. In this problem, I was trying to remove the value of 3, in which there were 3 of them. The output only removed 1 so I'm wondering what the problem is.

"*I'm wondering what the problem is*". The way to answer that is to actually debug the code. Run your program in a debugger and/or add more debug print statement to trace the program execution. Have you done that? What did you find? [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — kaylum, Dec 02 '21 at 04:26
You may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) — Andreas Wenzel, Dec 02 '21 at 04:29
`if (tmp != NULL && tmp->value == new) { free(tmp);` That can't be right because you free the node but don't actually remove it from the list. And why do you treat that as a special case anyway? — kaylum, Dec 02 '21 at 04:34
This is typo: `addBack(struct node **head...` It should be `NODE`, not `node`. You should see a compiler warning for this. Don't use this notation `(*p).value`, just use `p->value`. Your node structure contains `prev`, that should be named `next`, because you start at `head` and you move forward. — Barmak Shemirani, Dec 02 '21 at 05:18
Also I suggest removing `scanf` input for the time being. Just declare the array as `int array[] = { 1,2,3,4,5 };`, then `addBack(&head, 100);` This will make it easier to focus on compiler warnings and debug messages. Put back `scanf` input once complete. — Barmak Shemirani, Dec 02 '21 at 05:32
Whenever the topic of deleting a node from a linked list comes up, it's kind of mandatory to refer to Linus Torvalds' remark, that most implementations lack elegance and are needlessly convoluted. Here's a nice post explaining this is detail: https://softwareengineering.stackexchange.com/questions/273666/the-right-way-to-remove-an-item-from-a-linked-list — datenwolf, Dec 02 '21 at 11:31
Always compile with *warnings enabled*, and **do not** accept code until it *compiles without warning*. To enable warnings add `-Wall -Wextra -pedantic` to your `gcc/clang` compile string (also consider adding `-Wshadow` to warn on shadowed variables) (*hint:* your global `head` and parameter `head`). For **VS** (`cl.exe` on windows), use `/W3`. All other compilers will have similar options. Read and understand each warning -- then go fix it. The warnings will identify any problems, and the exact line on which they occur. — David C. Rankin, Dec 02 '21 at 19:55

Allan Wind · Accepted Answer · 2021-12-02T19:50:22.000

deleteNode() will remove at most the head or the first non-head node with a matching value. Note, that in the first case you need to update *head to the previous node. You should also handle head being NULL.

Here is an implementation of deleteNodes() that removes all matching nodes. To avoid the special case of the head node being removed, introduce a tmp node so we only have to deal with the non-head case:

void deleteNodes(struct NODE **n, int v) {
    if(!n) return;
    struct NODE tmp = {.prev = *n};
    for(struct NODE *p = &tmp; p->prev; ) {
        if(p->prev->value == v) {
            struct NODE *match = p->prev;
            p->prev = p->prev->prev;
            free(match);
        } else {
            p = p->prev;
        }
    }
    *n = tmp.prev;
}

delete node(s) in a singly linked list in c

1 Answers1

Linked