C - Inserting into sorted linked list with double pointers

Question

I'm trying to create a sorted linked list in C with the following code but I am getting a segmentation fault before any of my input is printed. I believe it is because I'm checking ((*link)->value < val) in my while loop, but at the beginning, it is NULL. I also tried adding a conditional for if there are no elements in the list but that didn't work. How could I check to see if the value to add is smaller without getting seg. fault?

struct NodeTag {
    int value;
    struct NodeTag *next;
};
typedef struct NodeTag Node;

typedef struct {
    Node *head;
    int length;
} List;

void insertSorted(List *list, int val) {
    Node **link = &(list->head);

    while (*link != NULL || (*link)->value < val) {
        //move node to correct place in list
        link = &((*link)->next);
    }
    //create new node
    Node *n = (Node *)malloc(sizeof(Node));
    n->value = val;

    //set next to null
    n->next = NULL;

    //insert new node
    *link = n;
}

Here is printList:

void printList(List *list) {
    printf("%d elements :", list->length);

    for (Node *n = list->head; n; n = n->next)
        printf( " %d", n->value);
    printf( "\n" );
}

Input: 72 19 47 31 8 36 12 88 15 75 51 29

Expected output: 8 12 15 19 29 31 36 47 51 72 75 88

Answer 1

Here are some problems in your code:

• you use || instead of &&. If the next member is NULL, you are at the end of the list, insert right there.

• the argument name is list but you use link in the body

• you don't need to cast the return value of malloc() in C and it is considered counterproductive, especially if you forget to include <stdlib.h>.

• you do not test for allocation failure

• you do not link the rest of the list to the inserted node.

• the function should return a pointer to the inserted node, giving the caller a chance to check for memory allocation failure.

• you should not comment the obvious.

Here is a corrected version:

#include <stdlib.h>

Node *insertSorted(List *list, int val) {
    Node **link = &list->head;
    while (*link != NULL && (*link)->value < val) {
        //skip this node
        link = &(*link)->next;
    }
    //create new node
    Node *n = malloc(sizeof(Node));
    if (n != NULL) {
        n->value = val;
        n->next = *link; // link the rest of the list
        *link = n;   //insert new node
    }
    return n;
}