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

This only outputs the smallest 4 out of 12 values. The input is: 72 19 47 31 8 36 12 88 15 75 51 29 and the list prints as: 8 12 15 29 — , Nov 05 '16 at 23:51
Possible duplicate of [C Double Pointer to Structure](http://stackoverflow.com/questions/7638612/c-double-pointer-to-structure) — , Feb 14 '17 at 20:28

chqrlie · Answer 1 · 2016-11-05T23:47:39.217

2

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;
}

edited Nov 05 '16 at 23:47

answered Nov 05 '16 at 22:09

chqrlie

131,814
10
121
189

Sorry, I forgot to include the line: Node **link = &( list->head ); at the beginning of the code – Nov 05 '16 at 23:44
@AaronHiller: OK, and you also forgot to post the definitions of `List` and `Node`. – chqrlie Nov 05 '16 at 23:46
Added it, how can I get it to not skip values? – Nov 06 '16 at 00:06
@AaronHiller: Does the corrected code skip values? Can you post a complete program with the printing function and the main function along with the input values and the expected output? – chqrlie Nov 06 '16 at 00:35
Posted. The current code(with && rather than ||) seems to be skipping some values – Nov 06 '16 at 01:09

C - Inserting into sorted linked list with double pointers

1 Answers1