CODEWITHSUNDEEP
calgorithmlistpointers
user123454321
user123454321

Reputation: 1058

Delete elements from singly linked list

i would like to delete some elements from list specified by value in function. My function doesn't work if function's 'val' is equal to my first element in list. Otherwise it works well. Any ideas?

struct elem {
    int val;
    struct elem *next;
};

void del(struct elem *list, int val) {
    struct elem* tmp = list;
    struct elem* prev = NULL;

    while (tmp != NULL) {
        if (tmp->val == val) {
            if (prev == NULL) {
                tmp = tmp->next;
                free(list);
                list = tmp;
            } else {
                prev->next = tmp->next;
                free(tmp);
                tmp = prev->next;
            }
        } else {
            prev = tmp;
            tmp = tmp->next;
        }
    }
}

Upvotes: 1

Views: 120

Answers (1)

M Oehm
M Oehm

Reputation: 29126

Your calling function cannot know that list has been updated. It will even go on referring to the same list, which has been deleted. Which is not good.

One solution is to pass the list as struct elem **list:

void del(struct elem **list, int val) {
    struct elem* tmp = *list;
    struct elem* prev = NULL;

    while (tmp != NULL) {
        if (tmp->val == val) {
            if (prev == NULL) {
                tmp = tmp->next;
                free(*list);
                *list = tmp;
            } else {
                prev->next = tmp->next;
                free(tmp);
                tmp = prev->next;
            }
        } else {
            prev = tmp;
            tmp = tmp->next;
        }
    }
}

Edit: There are other solutions. You could return the new list pointer:

struct elem *del(struct elem *list, int val) { ... }

And you call it like this:

list = del(list, 12);

This solution has the disadvantage that list is somewhat redundant in the call and that it is legal to omit the return value, thus actually not updating the list.

A solution I like is to define a control struct for your list. At the moment, that just contains the head pointer:

struct list {
    struct elem *head;
};

Your functions that operate on the list then take a pointer to this structure as argument:

void del(struct list *list, int val) {
    struct elem* tmp = list->head;
    struct elem* prev = NULL;

    while (tmp != NULL) {
        if (tmp->val == val) {
            if (prev == NULL) {
                tmp = tmp->next;
                free(list->head);
                list->head = tmp;
            } else {
                prev->next = tmp->next;
                free(tmp);
                tmp = prev->next;
            }
        } else {
            prev = tmp;
            tmp = tmp->next;
        }
    }
}

The struct list can have additional fields, for example the tail pointer for quick appending to the end. You could also keep track of the list length.

Upvotes: 5

Related Questions