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