Thread: problem with dual dereference of a struct pointer

Hello, I'm having some confusion using the struct dereference operator to set a pointer inside a struct that is being pointed to.

This is for a double linked list. Here is the node struct.

Code:

typedef struct _Node Node;


struct _Node
{
    Node* previous_node;
    Node* next_node;
    DATA_TYPE* data;
};

Basically, I'm writing a remove function and trying to deal with the case where the node which gets deleted is the last. The list is null terminated. That is, the last node's next_node element should point to NULL.

When I'm iterating through the list, I keep track of the current node with a place_holder node pointer. In the case of deleting the last node, I want something to do something like this:

place_holder->previous_node->next_node = NULL;

However when I do this, the program crashes and the "process" returns a non-zero number.

Here is the code:

Code:

void remove_node(Node* head, DATA_TYPE data)
{
    Node* place_holder = head->next_node;
    while(place_holder!=NULL)
    {
        if(*place_holder->data==data)
        {
            if(place_holder->next_node==NULL)
            {
                place_holder->previous_node->next_node = NULL; ///this causes error
                node_destructor(place_holder);


                return;
            }
            else
            {
                place_holder->previous_node->next_node = place_holder->next_node;
                place_holder->next_node->previous_node = place_holder->previous_node;
                node_destructor(place_holder);
                return;
            }
        }
        if(*place_holder->data>data)
        {
            return;
        }
        place_holder = place_holder->next_node;
    }
    return;
}

FYI, "DATA_TYPE" is a macro definition for the data type. In this case it's int although I don't think that should matter.

Thanks for any advice!

Thanks for your reply. I understand what you're saying. I believe I've already "trouble shot" the other potential pitfalls you mentioned and believe I've isolated the error to the line where I try to assign the NULL pointer (commented in the code from my original post):

Code:

place_holder->previous_node->next_node = NULL;

The destructor is quite simple, it merely frees the dynamically allocated memory so I don't think that is the source of my problem:

Code:

void node_destructor(Node* node)
{
    free(node->data);
    free(node);
    return;
}

I've tested the list with a print function which relies on the NULL termination and that works fine. This leads me to think the list is properly formatted and NULL terminted when I pass it to the remove function (in original post). Further, if remove_node() isn't removing from the last position, it works fine. Everything works until I try to assign the NULL pointer. For reference, here is the print function which works properly:

Code:

void print_list(Node* head)
{
    Node* place_holder = head->next_node;
    while(place_holder!=NULL)
    {
        printf("%d\n",*place_holder->data);
        place_holder = place_holder->next_node;
    }
}

Bloody brilliant! You debugged a function you weren't even shown. You were right, the bug was in the insertion. In the case where the node was inserted at the end of the list, I pointed the previous last node to the new node but I didn't point the new last node's previous_node pointer back. The previous_node should never be NULL so in a sense it is good the this caused the program to crash.

Assuming your insertion function has behaved correctly (which you assert, and expect me to accept on faith) I can also see your deletion code failing if the node you are removing is at the head of the list ....
in that case, I would expect that place_holder->previous_node would be NULL - despite your code's implicit assumption otherwise.

Actually, the first node's previous_node points to the head. The "head" in my implementation is essentially "outside" the list.

Your print_list() function only relies on next_node being valid until the end of the list (which is NULL). It also implicitly assume that head is non-NULL.

If the list is empty, the head's next_node is NULL and therefor the while loop is not entered.

Thanks again, saved me a few gray hairs.

For posterity, here's the insertion code:

Code:

void insert(Node* head, DATA_TYPE* data)
{
    /**
    note: Client is responsible for memory allocation.
          None-duplicating insert, data passed to function
          is freed if dupication found    
    */
    Node* new_node = node_constructor(data);
    Node* place_holder = head->next_node;


    if(head->next_node==NULL||*data<=*head->next_node->data)
    {
        new_node->next_node=head->next_node;
        if(head->next_node!=NULL)
        {
            if(*data==*head->next_node->data)
            {
                node_destructor(new_node);
                return;
            }
            head->next_node->previous_node = new_node;
        }
        new_node->previous_node=head;
        head->next_node = new_node;
        return;
    }
    while(place_holder->next_node!=NULL)
    {
        if(*data <= *place_holder->next_node->data)
        {
            if(*data==*place_holder->next_node->data)
            {
                node_destructor(new_node);
                return;
            }
            new_node->next_node = place_holder->next_node;
            place_holder->next_node->previous_node = new_node;
            new_node->previous_node = place_holder;
            place_holder->next_node = new_node;
            return;
        }
        place_holder = place_holder->next_node;
    }
    //insertion at end of list
    new_node->previous_node = place_holder;///This was missing, cause of bug.
    place_holder->next_node = new_node;
    return;
}