Fix: delete from a list – Data Structures Practice

Repair a linked-list delete function that has three separate bugs.

What to build

A corrected delete_value that works at the front, in the middle, at the end and for a missing value.

Requirements

The starter's delete_value works only for a value in the middle or at the end of the list, and even then it reads freed memory. Fix all of its bugs.
Delete the first node that holds each given value. If no node holds it, the list is unchanged.
Print the list after all the deletions, or empty.

Input

The first line has n, and the second has the n numbers. The third line has q, and the fourth has the q values to delete.

Output

The remaining numbers on one line, separated by spaces, or empty.

Constraints

1 ≤ n ≤ 100 and 1 ≤ q ≤ 100.

Example

Input:

4
10 20 30 40
2
30 10

Output:

20 40

Why it works

The three cases that break list code are the missing value, the first node and the order of unlinking and freeing. Checking for NULL in the loop, moving head when there is no previous node, and freeing last cover all three.

Examples

Example 1 · Input

4
10 20 30 40
2
30 10

Expected output

20 40

Example 2 · Input

Expected output

empty

Hints

Hint 1

What happens in the search loop when the value is not in the list at all?

Hint 2

Which pointer is NULL when the node to delete is the first one?

Hint 3

The chain must be joined round the node before the node is freed.

Solution

Show one correct solution (try it yourself first)

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

typedef struct node {
    int value;
    struct node *next;
} Node;

Node *delete_value(Node *head, int value) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL && cur->value != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return head;
    if (prev == NULL) head = cur->next;
    else prev->next = cur->next;
    free(cur);
    return head;
}

int main(void) {
    int n, q;
    scanf("%d", &n);
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *p = malloc(sizeof(Node));
        scanf("%d", &p->value);
        p->next = NULL;
        if (head == NULL) head = p;
        else tail->next = p;
        tail = p;
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int value;
        scanf("%d", &value);
        head = delete_value(head, value);
    }
    if (head == NULL) printf("empty");
    for (Node *p = head; p != NULL; p = p->next) {
        if (p != head) printf(" ");
        printf("%d", p->value);
    }
    printf("\n");
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
    return 0;
}

Lesson: Data structure bugs →