Home > database >  delete node(s) in a singly linked list in c
delete node(s) in a singly linked list in c

Time:12-03

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;
}

enter image description here

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.

CodePudding user response:

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;
}
  • Related