Doubly-linked list in C, insert by value

Question

I decided to do a project on doubly-linked list in order to understand it better. I have already made functions that insert nodes at the head and at the tail but now I'm having trouble in inserting nodes by value. Here is the function:

void f_insert_by_value(the_individual **head, char *str, int a) {
    the_individual *current = *head, *temp = f_create(str, a);

    if (*head == NULL) *head = temp;
    else {
        if (temp->age < (*head)->age) {
            temp->next = (*head);
            (*head)->prev = temp;
            (*head) = (*head)->prev;
        }
        else {
            while (temp->age > current->age && current->next != NULL) current = current->next;
            if (current->next = NULL) {
                temp->prev = current;
                current->next = temp;               
                current = current->next;
            }
            else {
                temp->prev = current->prev;
                temp->next = current;
                current->prev->next = temp;
                current->prev = temp;
            } 
        }
    }
    return;
}

Segmentation fault occurs on line "current->prev->next = temp". I tried to print addresses to see why this happens and found out that node which is first in the input always ends up having it's previous element pointing to NULL. Can someone explain why that happens and how can it be fixed? Thank you.

To avoid all those border cases (first, prev = NULL) etc. a lot of people implement those lists such, that they have a static dummy element which is wired to the edges of the list. Then you do not ask for NULL but if your pointer is the address of the dummy to find out you are at the front or the rear of your list. When you insert new nodes, this small trick saves you testing for NULL pointers all over the place. — BitTickler
@user2225104 has good advice. Hacky workarounds like that make C fun — Marshall Tigerus

Dimitri Mockelyn Dimitri Mockelyn · Accepted Answer · 2015-01-30T16:42:38

On the first node, current->prev is null because current is the first one, you got it right.

temp->prev = current->prev;
temp->next = current;

This thing is right, you are setting the new node at the right place, but now currentdoesn't lead to the right thing. You schema is this one at this point :

NULL <= temp => current
NULL <= current <=> ...

And you want

NULL <= temp <=> current <=> ...

So the only thing missing is that the previous element of current is temp. So I guess that just removing the line

current->prev->next = temp

Should do the trick for the first element insertion, because you set current->prev right after.

So I guess your condition block should be like this :

temp->prev = current->prev;
temp->next = current;
if (current->prev != NULL) {
    current->prev->next = temp;
}
current->prev = temp;

As said in the comments, if you want to avoid the null pointer problem with linked list, you can add a dummy at the beginning and at the very end of your list, which are controllers telling that you reach the limit. You can find more information on these types of linked list (with a Sentinel Node) here

Doubly-linked list in C, insert by value

1 Answers