How to deallocate the linked list?

Question

This is my code.

struct node_struct {
    char *data;
    struct node_struct *next;
};

typedef struct node_struct Node;

struct queue_struct {
    Node *head, *tail;
};

typedef struct queue_struct Queue;

void push(Queue **q, char *word) 
{
    // q hasn't been allocated
    if (*q == NULL) {
        (*q) = malloc(sizeof(Queue));
    }

    Node *temp;
    temp = malloc(sizeof(Node));
    temp->data = malloc(sizeof(char)*strlen(word));
    strcpy(temp->data, word);
    temp->next = NULL;

    if ((*q)->head == NULL) {
        (*q)->head = (*q)->tail = temp;
    }
    else {
        (*q)->tail->next = temp;
        (*q)->tail = temp;
    }
}

I will use push to pushes a string word to the back of a queue q. Instead of keeping the pointer to the array, it keeps a copy of the word inside the queue.

Finally, I want to deallocates the queue as well as all items in it. So, I use free() and this is what I write.

void delete(Queue *q) 
{
    Node *temp;
    for (temp = q->head; temp != NULL; temp = temp->next) {
        free(temp->data);    
        free(temp);
    }
    free(q);
}

But, this lead to segmentation fault. Why this happen, and how can I fix this?

Answer 1

1. When you malloc() a string you need to allocate an extra byte for the terminating '\0'.
2. In delete() you need to have two frees in the loop followed by a free of the queue (reverse order of what would happen in the push; except in this case it's easier to deallocate from head). You need temporary variable t2 here to remember the next element so you can update your loop variable t.
3. You need to initialize head when creating the initial queue.
4. (Not fixed) Check that malloc() and strdup() succeed.

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

typedef struct node_struct {
    char *data;
    struct node_struct *next;
} Node;

typedef struct queue_struct {
    Node *head;
    Node *tail;
} Queue;

void push(Queue **q, const char *word) {
    if (!*q) {
        *q = malloc(sizeof(Queue));
        (*q)->head = NULL;
    }

    Node *temp = malloc(sizeof(Node));
    temp->data = malloc(strlen(word) + 1);
    strcpy(temp->data, word);
    temp->next = NULL;

    if (!(*q)->head) {
        (*q)->head = temp;
        (*q)->tail = temp;
    } else {
        (*q)->tail->next = temp;
    }
}

void delete(Queue *q) {
    for(Node *t = q->head; t;) {
        free(t->data);
        Node *t2 = t->next;
        free(t);
        t = t2;
    }
    free(q);
}

int main(void) {
    Queue *q = NULL;
    push(&q, "test");
    push(&q, "test2");
    delete(q);
}

and here is the valgrind output:

==762222== HEAP SUMMARY:
==762222==     in use at exit: 0 bytes in 0 blocks
==762222==   total heap usage: 5 allocs, 5 frees, 59 bytes allocated
==762222== 
==762222== All heap blocks were freed -- no leaks are possible
==762222== 
==762222== For lists of detected and suppressed errors, rerun with: -s
==762222== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

To simplify push() a bit you can use a double pointer to Node (p), calloc() to initialize head and strdup() to allocate and copy the string:

#define _POSIX_C_SOURCE 200809L // for strdup()
#include <string.h>

void push(Queue **q, const char *word) {
    Node **p;
    if (!*q) {
        (*q) = calloc(1, sizeof(Queue));
        p = &(*q)->tail;
    } else
        p = &(*q)->tail->next;

    (*p) = malloc(sizeof(Node));
    (*p)->data = strdup(word);
    (*p)->next = NULL;
    
    if (!(*q)->head)
        (*q)->head = *p;
}