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
– BitTickler, Commented Jan 30, 2015 at 16:36
@user2225104 has good advice. Hacky workarounds like that make C fun — Marshall Tigerus
– Marshall Tigerus, Commented Jan 30, 2015 at 16:42

Dimitri Mockelyn · Accepted Answer · 2015-01-30 17:14:42Z

2

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

edited Jan 30, 2015 at 17:14

answered Jan 30, 2015 at 16:42

Dimitri Mockelyn

1,5452 gold badges11 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

BitTickler Over a year ago

Yes, even though the wikipedia article is a bit silly regarding the fact that they actually allocate the sentinel node. This is a waste. You simply make 1 static for all lists of the same type in your list implementation module and it does not matter that it gets wired to 10000 instances of lists. Why that? Because you never use sentinel->next etc. You only set it for convenience of your insert-code.

lukasm Over a year ago

@Dimitri but say if I have element1, element2, temp and current is pointing at element2. I want to insert temp between these two elements. temp->prev = current->prev, temp->next = current, current->prev = temp, but now element1->next is still pointing to element2 not temp so I think that current->prev->next = temp is necessary because it make element1->next point to temp?

Dimitri Mockelyn Over a year ago

Oh you're absolutely right. I only thought about the process for the first element. For other elements, you want to keep this line indeed. I'll edit my answer

Collectives™ on Stack Overflow

Doubly-linked list in C, insert by value

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related