How to free a linked list with pointers

Question

I was trying to free memory for a linked list iteratively. The list has a struct which looks like this, and in this linked list, I don't add a url if it's in this list.

struct Node {
    char *url;
    struct Node *next;
};

Once done working with this linked list, I tried to free it, but got segmentation fault, I'm still in the way of learning c, I haven't got much clue of how to debugging such error other than directly searching for related topics. Referenced a few SOs this one, this one and this one, still cannot figure out where it got crashed.

Here's my code. Free feel to add comments if you think anything I missed in this implementation.

void url_push(struct Node *head, const char *url, size_t url_size) {
    struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));

    new_node->url = malloc(url_size);
    new_node->next = NULL;

    for (int i = 0; i < url_size; i++)
        *(new_node->url + i) = *(url + i);

    struct Node *current = head;
    while(1) {
        if (strcmp(current->url, new_node->url) == 0) {
            printf("Seen page %s!!!!!\n", new_node->url);
            free(new_node);
            break;
        } else if (current->next == NULL) {

            current->next = new_node;
            break;
        } else {
            current = current->next;
        }
    }
}

int main() {
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    head->url = "/";
    head->next = NULL;

    char *url = "www.google.com";
    url_push(head, url, strlen(url));

    url = "www.yahoo.com";
    url_push(head, url, strlen(url));

    url = "www.google.com";
    url_push(head, url, strlen(url));

    url = "www.wsj.com";
    url_push(head, url, strlen(url));

    struct Node *current = NULL;

    while ((current = head) != NULL) {
        printf("url: %s\n", head->url);

        head = head->next;
        free(current->url);
        free(current);
    }
}

Edited: To reduce the confusions, I revised the struct. The purpose of using strcmp is to avoid adding a url that already seen.

Answer 1

head->url = "/";

That is not malloced data so you can't free it!

Your other problem is in url_push() with new_node->url = malloc(url_size); which does not allocate enough space for the terminating 0 in the string (nor does it copy the terminating 0 so you end up not "stomping on memory" but do have unterminated strings...). Try new_node->url = strdup(url); instead.

Style wise: calculate url_size in url_push() instead of making each caller call strlen() do it once inside the function being called (note if you use strdup() then you don't need the url_size at all.

Final note: A tool like valgrind would find both of these problems easily.

Answer 2

There are multiple problems in your code:

• you do not allocate space for the null terminator for the new_node->url strings in url_push, causing strcmp() too have undefined behavior.
• the first node is not properly constructed: its url pointer is not allocated.
• you so not check for memory allocation failure

You should make url_push() more generic: it should handle empty lists by returning the new head pointer. You do not need to pass the length of the url string, just use strdup(), and you should avoid allocating a new node before checking for duplicates.

Here is a modified version:

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

struct Node {
    char *url;
    struct Node *next;
};

struct Node *url_push(struct Node *head, const char *url) {

    struct Node *current = head;
    if (current != NULL) {
        for (;;) {
            if (strcmp(current->url, url) == 0) {
                printf("Seen page %s before!!!!!\n", url);
                return head;
            } else if (current->next == NULL) {
                break;
            } else {
                current = current->next;
            }
        }
    }
    struct Node *new_node = malloc(sizeof(struct Node));

    if (new_node == NULL || (new_node->url = strdup(url)) == NULL) {
        fprintf(stderr, "memory allocation failure\n");
        exit(1);
    }
    new_node->next = NULL;

    if (current == NULL) {
        head = new_node;
    } else {
        current->next = new_node;
    }
    return head;
}

int main() {
    struct Node *head = NULL;

    head = url_push(head, "/");
    head = url_push(head, "www.google.com");
    head = url_push(head, "www.yahoo.com");
    head = url_push(head, "www.google.com");
    head = url_push(head, "www.wsj.com");

    while (head != NULL) {
        printf("url: %s\n", head->url);
        struct Node *current = head;
        head = head->next;
        free(current->url);
        free(current);
    }
    return 0;
}