CODEWITHSUNDEEP
cdoubly-linked-list
Josh Bair
Josh Bair

Reputation: 11

Deleting a node from a doubly linked list

This is my current code which i have messed with so how im dealing with the first item or only item are wrong, which are the first 2 parts to this function. For some reason i am getting memory errors if i just try to set node=node->next_.. i would assume this would be the easiest way but when i throw that back into the program i start getting memory access issues. all other parts work fine as long as i don't manipulate the head address.

void removeNode(struct student_record_node* node)
{
    struct student_record_node *temp=NULL;
    temp=node;
    if(node->next_==NULL&&node->prev_==NULL)
    {
        node=node->next_
        free(node->prev_);
    }
    else if(node->prev_==NULL&& node->next_!=NULL)
    {
        node=node->next_
        free(node->prev_);
    }

    else if(node->next_!=NULL && node->prev_!=NULL)
    {
        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;
        student_record_node_deallocate(node);
    }
    else if(node->prev_!=NULL&& node->next_==NULL)
    {
        node->prev_->next_=node->next_;
        student_record_node_deallocate(node);
    }
}

Upvotes: 1

Views: 103

Answers (2)

Kugelblitz
Kugelblitz

Reputation: 582

Since you did not provide, what your linked list looks like, I am going to assume for my code-example, that it is a struct containing a pointer to the head of the linked list (the first element). It is referred to by your_list.

The problem lies within the first two if-blocks in your code;

  • The first if: if(!node->next_ && !node->prev_):

    This means you are deleting the head-element of the list. In this case, you will have to explicitly set the head to NULL, instead of setting the pointer to the node you wish to delete to NULL (by setting it to its predecessor, which is NULL). Also, you are freeing a NULL-Pointer, by freeing the previous node. This is in it self not a problem, but you want to delete node, not it's predecessor.

  • The second if: if(!node->prev_ && node->next_):

    This means you are deleting the head, but the list will not be empty after the node is deleted. In this case, you must set the head of the list to point to the new head, which will be the node pointed to by node->next_. Also, you have the similar problem with free() as before.

Addressing those two points, your code should do something along the lines of this:

void removeNode(struct student_record_node *node){
    if(!node->next_ && !node->prev_){
        your_list->head = NULL; // Remove head - List is now empty.
        student_record_node_deallocate(node);
        node = NULL; // Set freed pointer to NULL, for safety.
    }
    else if(!node->prev_ && node->next_){
        your_list->head = node->next_; // Set the head to the new head.
        student_record_node_deallocate(node);
        node = NULL; // Set freed pointer to NULL, for safety.
    }
    else if(node->next_ && node->prev_){
        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;
        student_record_node_deallocate(node);
        node = NULL; // Set freed pointer to NULL, for safety.
    }
    else if(node->prev_ && !node->next_){
        node->prev_->next_ = NULL;
        student_record_node_dealocate(node);
        node = NULL; // Set freed pointer to NULL, for safety.
    }
}

Upvotes: 1

seamaner
seamaner

Reputation: 91

There are several errors：

  1. The node may be the head, so struct student_record_node* should be returned, instead of void.

  2. node may be NULL

  3. if node->prev_ is NULL, make sure to free the node deleted.

Upvotes: 1

Related Questions