Linked Lists C Deleting Node

Question

I'm just starting to learn linked lists and i was practicing by writing some basic functions such as add or delete. The program was working for some time but then i guess i did something and it starting giving me segmentation fault at my delete function which is this. The segmentation fault is in the while loop in if. Any idea why? Thanks in advance and sorry for my bad english :).

void deleteNode(struct node **first, int age)    
{

    struct node *tempNode;
    if((*(*first)).age == age)
    {
        tempNode = *first;
        *first = (*first)->next;
        free(tempNode);
    }

    struct node *currentNode = (*first)->next;
    struct node *lastNode = *first;

    while(currentNode!=NULL)
    {
        //Segmentation Fault
        if(currentNode->age == age)
        {
            tempNode = currentNode;
            lastNode->next = currentNode->next;
            free(tempNode);
        }
        lastNode = currentNode;
        currentNode = currentNode->next;
    }
}

I'm pretty sure it has something to do with the last 2 lines where i change the previous and the current node. — Roronoa
– Roronoa, Commented Apr 21, 2016 at 18:06
few lines above you've freed it through tempNode = currentNode; free(tempNode). now you are trying to get next from the free memory. — fukanchik
– fukanchik, Commented Apr 21, 2016 at 18:16

user295691 · Accepted Answer · 2016-04-21 18:11:49Z

1

The problem here is that you are referencing lastNode after it has been freed. If we look at the trace of the loop, you free tempNode, which you have assigned to currentNode, and then you set lastNode to currentNode. You want lastNode to point to the last valid node, so the update lastNode = currentNode is only valid if currentNode has not been freed.

In short, the fix is to only assign lastNode = currentNode if you don't remove the current node.

answered Apr 21, 2016 at 18:11

user295691

7,2681 gold badge28 silver badges37 bronze badges

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

Comments

jxh · Accepted Answer · 2016-04-21 18:55:27Z

The trick with freeing nodes from a list is to get the information out of the node before you free it. Attempting to access memory that has been freed results in undefined behavior.

In this case you are only dealing with next, and you are tracking lastNode. So, lastNode->next is the logical currentNode.

In the beginning of your function, you account for the case that the first node matches age. However, if that is the case, the next node may also match age. So, your first matches age case also needs to be a loop.

Instead of writing two loops, use the concept of address of previous node's next to represent lastNode. This works well since first is already a pointer to a pointer to node.

struct node **lastNode = first;

while (*lastNode != NULL) {
    struct node *currentNode = *lastNode;
    if (currentNode->age != age) {
        lastNode = &currentNode->next;
        continue;
    }
    /* remove currentNode */
    *lastNode = currentNode->next;
    free(currentNode);
}

Collectives™ on Stack Overflow

Linked Lists C Deleting Node

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related