Why am I getting a segmentation fault after successfully removing a node from a linked list?

Question

I have a linked list that I'm attempting to turn into a "heap" that stores its content dynamically. I thought that my delete_node function was working properly but when I try to heapify the list I get a segmentation fault.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
    int content;
    struct Node* next;
};
struct Heap {
    char* type;
    int* array;
    int head;
    int tail;
    int heap_capicity;
};
struct Node* add(struct Node* list, int x) {
    if (list == NULL) {
        struct Node* new_nd = malloc(sizeof(struct Node));
        new_nd->content = x;
        new_nd->next = NULL;
        return new_nd;
    }    
    list->next = add(list->next, x);
    return list;
}
struct Node* delete_node(struct Node* node, int x) {
    if (node == NULL || node->next == NULL) return NULL;
    if (node->next->content == x) {
        struct Node* temp = node->next;
        node->next = node->next->next;
        // temp = NULL;
        free(temp);
        return node;
    }
    node->next = delete_node(node->next, x);
    return node;
}
struct Heap* new_heap(char* type) {
    struct Heap* new_heap = malloc(sizeof(struct Heap));
    new_heap->type = type;
    new_heap->array = malloc(2 * sizeof(int));
    new_heap->array[0] = 0;
    new_heap->head = -1;
    new_heap->tail = -1;
    new_heap->heap_capicity = 2;
    return new_heap; 
} 
void double_it(struct Heap* heap) {
    heap->array = realloc(heap->array, heap->heap_capicity * 2);
    heap->heap_capicity *= 2;
    return;
}
void add_hp(struct Heap* heap, int content) {
    if (heap->head < 0) {
        heap->head = 1;
        heap->tail = 1;
        heap->array[heap->head] = content;
        return;
    }
    if (heap->tail + 1 == heap->heap_capicity) double_it(heap);
    heap->array[++heap->tail] = content;
    // swim(&heap, heap->tail);
    return;
}
void heapify_from_linked_list(struct Heap* heap, struct Node* node) {
    if (node == NULL) return;
    add_hp(heap, node->content);
    heapify_from_linked_list(heap, node->next);
    return;
}
int main () {
    struct Node* my_list = NULL;
    my_list = add(my_list, 1);
    my_list = add(my_list, 2);
    my_list = add(my_list, 3);
    my_list = add(my_list, 4);
    my_list = add(my_list, 5);
    my_list = add(my_list, 6);
    my_list = add(my_list, 7);
    my_list = add(my_list, 8);
    my_list = add(my_list, 9);
    my_list = add(my_list, 10);
    delete_node(my_list, 7);
    
    struct Heap* maxPQ = new_heap("max");
    heapify_from_linked_list(maxPQ, my_list);
    return 0;
}

OUTPUT:

[1000, 100, 10, 1, 11, 111, 1111, 636, 422, 838, 166, 799, 945, 506, 676, 454, 677]
Deleting 111
[1000, 100, 10, 1, 11, 1111, 636, 422, 838, 166, 799, 945, 506, 676, 454, 677]
Calling heapify
Node is: 1000
Node is: 100
Node is: 10
Node is: 1
Node is: 11
Node is: 1
Segmentation fault: 11

Weirdly enough, some of the values can be removed with no issue, for instance 1 can be removed and the program runs fine. I found that the issue was me not nullifying the pointer before freeing it. My question is, although I know it's good practice to nullify pointers that are not in use, why would the next pointer of a node point to an arbitrary node in one case (when heapify is called) but not another (when delete_node is called)?

Any non-null pointer points to something in memory. Without having debugged the code, I'd wager your pointer points to a block of memory that previously was initialized with node data. — Eric J., Mar 25 '23 at 00:10
See also [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/110821650) — Brian61354270, Mar 25 '23 at 00:10
OT: Have you tried `delete_node()` when there is only one node on the list? Looks like it will be impossible to scrub out that last node... — Fe2O3, Mar 25 '23 at 00:12
You're using recursion in places where iteration will suffice. Replace it with a simple loop. — Tom Karzes, Mar 25 '23 at 00:19
`delete_node` will fail if the node to be deleted is the first node. — Tom Karzes, Mar 25 '23 at 00:21
It segfaults in `heap->array = realloc(heap->array, heap->heap_capicity * 2);`. It's also an unsafe construct as it will leak memory if `realloc()` fails. — Allan Wind, Mar 25 '23 at 02:48

Allan Wind · Answer 1 · 2023-03-25T06:06:31.307

Your program segfaults in double_it(): heap->array = realloc(heap->array, heap->heap_capicity * 2);. This is because you allocate the wrong amount of data. new_heap->heap_capicity tracks the number of number of objects, but you need to scale with size of object (in this case int):

    heap->array = realloc(heap->array, sizeof *heap->array * heap->heap_capicity * 2);

With this change I am no longer able to reproduce the segfault.

The way you call recalloc() is not safe, instead you want to use use temporary variable tmp:

    int *tmp = realloc(heap->array, sizeof *heap->array * heap->heap_capicity * 2);
    if(!tmp) {
      // handle error
    }
    heap->array = tmp;

Prefer using the variable rather than type as arguments to sizeof (DRY; and you can leave out the () so there is less noise).

Why am I getting a segmentation fault after successfully removing a node from a linked list?

1 Answers1