Several problems with Linked Lists functions

Question

I tried to create several functions for linked lists. Here are all of them, but i have problem with function delete_All and delete.

delete_All need to delete all elements with given value, and delete only first.

The first mistake that i cannt find is free(_) (marked in code as "HERE!!!") and also endless program work in delete_All when we put in head of Linked List and at the same time in the next element value which needs to be removed.

For example (1,1,2,3,4,) cannt remove first pair "1". delete and some other functions cannt use free function.

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

struct uzel {
    int n;
    struct uzel *next;
};

struct uzel *
initializef(struct uzel *head)
{
    static int c = 0;
    int a;

    printf("uzel[%d] = ", c);
    scanf("%d", &a);
    if (a == 0) {
        head->next = NULL;
    }
    else {
        c++;
        head->n = a;
        head->next = malloc(sizeof(struct uzel));
        initializef(head->next);
    }
    return head;
}

void
gprint(struct uzel *head)
{
    printf("(");
    while (head->next != NULL) {
        printf("%d ", head->n);
        head = head->next;
    }
    printf(")\n");
}

struct uzel *
delete(struct uzel *head, int val)
{
    if (head->n == val) {
        struct uzel *newhead = head;

        newhead = head->next;
        struct uzel *del = head;

        // free(del);//HERE!!!!!!!!!
        return newhead;
    }
    struct uzel *right = head;
    struct uzel *left = right;

    while (left->next) {
        right = left->next;
        if (right->next != NULL) {
            if (right->n == val) {
                struct uzel *del = right;

                left->next = right->next;
                free(del);
            }
        }                               // but here is ok!!!
        left = left->next;
    }
    return head;
}

struct uzel *
delete_all(struct uzel *head, int val)
{
    struct uzel *newhead = head;

    while (newhead->n == val) {
        newhead = head->next;
        // struct uzel* del=head;//here!!!!!!!!!!!!!!
        // free(del);
        if ((newhead->n) == NULL) {
            printf("No more elements to work with,ERROR");
            return 0;
        }
    }
    struct uzel *right = newhead;
    struct uzel *left = newhead;

    while (left->next) {
        right = right->next;
        if (right->n == val) {
            struct uzel *tmp = right;

            left->next = right->next;
            free(tmp);
        }
        else {
            left = left->next;
        }
    }
    return newhead;
}

void
addAfter(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((left->n) != after_what) {
        right = right->next;
        left = left->next;
    }
    right = right->next;
    struct uzel *newelem = malloc(sizeof(struct uzel));

    newelem->n = info;
    newelem->next = right;
    left->next = newelem;
}

void
addAfterALL(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((right->next)) {
        while (((left->n) != after_what)) {
            right = right->next;
            left = left->next;
        }
        right = right->next;
        struct uzel *newelem = malloc(sizeof(struct uzel));

        newelem->n = info;
        newelem->next = right;
        left->next = newelem;
    }
}

int
main()
{
    int a, b;
    struct uzel head2;
    struct uzel *mainhead1 = initializef(&head2);

    gprint(mainhead1);
    printf("Enter a number to delete: ");
    scanf("%d", &a);
    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        struct uzel *mainhead = delete_all(mainhead1, a);

        gprint(mainhead);
    }
    else {
        struct uzel *mainhead = delete(mainhead1, a);

        gprint(mainhead);
    }
    printf("Enter after what number u want to insert smth: ");
    int r;

    scanf("%d", &r);
    printf("Enter what number u want to insert: ");
    int u;

    scanf("%d", &u);
    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;

    scanf("%d", &g);
    if (g == 2) {
        addAfter(u, r, mainhead1);
        gprint(mainhead1);
    }
    if (g == 1) {
        addAfterALL(u, r, mainhead1);
        gprint(mainhead1);
    }
}

Answer 1

The code for delete and delete_All is very similar, so it can be moved to a common function.

Here's a refactored version (with some annotations) that simplifies the delete code and makes it work for both cases.

Note the use of the extra next variable to prevent "use after free" [which may have been the source of the issues with calling free].

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

struct uzel {
    int n;
    struct uzel *next;
};

struct uzel *
initializef(struct uzel *head)
{
    static int c = 0;
    int a;

    printf("uzel[%d] = ", c);
    scanf("%d", &a);
    if (a == 0) {
        head->next = NULL;
    }
    else {
        c++;
        head->n = a;
        head->next = malloc(sizeof(struct uzel));
        initializef(head->next);
    }
    return head;
}

void
gprint(struct uzel *head)
{
    printf("(");
    while (head->next != NULL) {
        printf("%d ", head->n);
        head = head->next;
    }
    printf(")\n");
}

struct uzel *
delete_common(struct uzel *head, int val, int allflg)
{
    struct uzel *cur;
    struct uzel *prev;
    struct uzel *next;

    prev = NULL;
    for (cur = head;  cur != NULL;  cur = next) {
        next = cur->next;

        // wait for match
        if (cur->n != val) {
            prev = cur;
            continue;
        }

        // remove from middle/end of list
        if (prev != NULL)
            prev->next = next;

        // remove from head of list
        else
            head = next;

        // release the storage for the node we're deleting
        free(cur);

        // stop if we're only deleting the first match
        if (! allflg)
            break;
    }

    return head;
}

struct uzel *
delete(struct uzel *head, int val)
{

    head = delete_common(head,val,0);

    return head;
}

struct uzel *
delete_all(struct uzel *head, int val)
{

    head = delete_common(head,val,1);

    return head;
}

void
addAfter(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((left->n) != after_what) {
        right = right->next;
        left = left->next;
    }
    right = right->next;
    struct uzel *newelem = malloc(sizeof(struct uzel));

    newelem->n = info;
    newelem->next = right;
    left->next = newelem;
}

void
addAfterALL(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((right->next)) {
        while (((left->n) != after_what)) {
            right = right->next;
            left = left->next;
        }
        right = right->next;
        struct uzel *newelem = malloc(sizeof(struct uzel));

        newelem->n = info;
        newelem->next = right;
        left->next = newelem;
    }
}

int
main()
{
    int a, b;
    struct uzel head2;
    struct uzel *mainhead1 = initializef(&head2);

    gprint(mainhead1);
    printf("Enter a number to delete: ");
    scanf("%d", &a);
    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        struct uzel *mainhead = delete_all(mainhead1, a);

        gprint(mainhead);
    }
    else {
        struct uzel *mainhead = delete(mainhead1, a);

        gprint(mainhead);
    }
    printf("Enter after what number u want to insert smth: ");
    int r;

    scanf("%d", &r);
    printf("Enter what number u want to insert: ");
    int u;

    scanf("%d", &u);
    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;

    scanf("%d", &g);
    if (g == 2) {
        addAfter(u, r, mainhead1);
        gprint(mainhead1);
    }
    if (g == 1) {
        addAfterALL(u, r, mainhead1);
        gprint(mainhead1);
    }
}

---

UPDATE:

just checked code, still have problems with free(cur) when trying to use it in delete_all actually the problem appears when delete a head of a list

Okay. There are two ways to have/use a head of a linked list:

1. It can be the first valid node (with data).
2. It can be a "dummy" node (where we ignore the data) and the first valid data node is what head->next points to.

I coded up the delete functions assuming (1). But, after looking over the code some more, I believe you're using (2).

It is perfectly valid to do either. But, if using (2), it is reusing a node struct as a list struct. This is still valid, but I prefer to add an explicit list struct to make things more clear.

What added to my confusion was doing a return head;. This is what we'd do for (1). If we do (2), we can eliminate the return altogether and just update head->next.

My original fix assumed (1) and that made it incompatible with (2), which is what the other functions were using.

I've refactored the code to use a separate list struct.

Also, after getting that working, the addAfter function(s) needed some work because the addAfter didn't handle the case where we added an element after back to back nodes with the same value. For example, trying to add 9 after 5 with a list of:

1 1 2 3 4 5 5 6 7

Produced:

1 1 2 3 4 5 9 6 7

Instead of:

1 1 2 3 4 5 9 5 6 7

Once again, the two addAfter functions can be combined and simplified.

Some additional thoughts on the use of the list struct ...

When we pass a list pointer around, the caller does not have to worry about whether the callee had to adjust the head of the list. The called function just does it.

In the original code, the delete* functions passed back the [possibly] modified head. The addAfter* functions could not [due to their nature] change the head of the list, so they didn't have to return an updated head value. In both cases, the caller of these functions (i.e. main) had to "know" this.

If we added a similar set of functions to addAfter* that did the insert before the info value (e.g. insertBefore*), they might have to update the head. Again, the caller would have to know about this.

So, using struct list actually simplifies the code for most functions and allows them to have a more unified set of parameters. (e.g.) The list is the first argument and the function can fully manipulate it as it chooses without needing to return anything.

As I was doing all that, I noticed the initializef was recursive. While it is valid to do that, IMO, that's not a good use of recursion. An iterative solution is cleaner.

Anyway, here's the updated code. Hopefully, I tested it for the edge cases a bit more. But, you may want to test it thoroughly to be sure.

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

struct uzel {
    int n;
    struct uzel *next;
};

struct list {
    struct uzel *head;
};

void
initializef(struct list *list)
{
    int c = 0;
    int a;
    struct uzel *newelem;
    struct uzel *prev;

    prev = NULL;
    while (1) {
        printf("uzel[%d] = ", c);

        scanf("%d", &a);

        if (a == 0)
            break;

        newelem = malloc(sizeof(*newelem));
        newelem->n = a;
        newelem->next = NULL;

        if (prev != NULL)
            prev->next = newelem;
        else
            list->head = newelem;

        prev = newelem;

        ++c;
    }
}

void
gprint(struct list *list)
{
    struct uzel *cur;

    printf("(");

    for (cur = list->head;  cur != NULL;  cur = cur->next)
        printf("%d ",cur->n);

    printf(")\n");
}

void
delete_common(struct list *list, int val, int allflg)
{
    struct uzel *cur;
    struct uzel *prev;
    struct uzel *next;

    prev = NULL;
    for (cur = list->head;  cur != NULL;  cur = next) {
        next = cur->next;

        // wait for match
        if (cur->n != val) {
            prev = cur;
            continue;
        }

        // remove from middle/end of list
        if (prev != NULL)
            prev->next = next;

        // remove from head of list
        else
            list->head = next;

        // release the storage for the node we're deleting
        free(cur);

        // stop if we're only deleting the first match
        if (! allflg)
            break;
    }
}

void
delete(struct list *list, int val)
{

    delete_common(list,val,0);
}

void
delete_all(struct list *list, int val)
{

    delete_common(list,val,1);
}

void
addAfter_common(struct list *list, int info, int after_what, int allflg)
{
    struct uzel *cur;
    struct uzel *newelem;

    for (cur = list->head;  cur != NULL;  cur = cur->next) {
        // wait for a match
        if (cur->n != after_what)
            continue;

        // get new element to add
        newelem = malloc(sizeof(*newelem));
        newelem->n = info;

        // insert new element after the match
        newelem->next = cur->next;
        cur->next = newelem;

        // ensure that we don't infinitely add elements if the element value
        // we're adding matches the value(s) we're searching for
        // (e.g.) if info and after_what are the same
        cur = newelem;

        // stop unless adding after _all_ matches
        if (! allflg)
            break;
    }
}

void
addAfter(struct list *list, int info, int after_what)
{

    addAfter_common(list,info,after_what,0);
}

void
addAfterALL(struct list *list, int info, int after_what)
{

    addAfter_common(list,info,after_what,1);
}

int
main(void)
{
    int a, b;
    struct list listx = { .head = NULL };
    struct list *list = &listx;

    initializef(list);
    gprint(list);

    printf("Enter a number to delete: ");
    scanf("%d", &a);

    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        delete_all(list, a);
        gprint(list);
    }
    else {
        delete(list, a);
        gprint(list);
    }

    printf("Enter after what number you want to insert something: ");
    int r;
    scanf("%d", &r);

    printf("Enter what number you want to insert: ");
    int u;
    scanf("%d", &u);

    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;
    scanf("%d", &g);

    if (g == 2) {
        addAfter(list, u, r);
        gprint(list);
    }
    if (g == 1) {
        addAfterALL(list, u, r);
        gprint(list);
    }

    return 0;
}