C - Deleting any node from a doubly linked list

Question

I ran into some trouble while attempting to remove a Node form a doubly linked list. While I can generally remove the nodes, the moment I attempt to remove the first element, it crashes my program and returns Error 3221225477.

I create my list with a header, like this:

typedef struct Inode2*Task;                                     
typedef struct Inode2{
        int ID;
        int Priority;
        int Status;
        char *Description;
        Person *person;
        Date   *creation;
        Date   *deadline;
        Date   *conclusion;                             
        Task next;
        Task previous;
    }Task_node2;    

Task TaskCreate()                                                                                                           {
    Task aux=(Task)malloc(sizeof(Task));
    aux->next=NULL;
    aux->previous=NULL;
    return aux;
}

So as far as I'm aware, this is creating a list with a header, which is given to me to manipulate further.

I have a function to insert a node at the tail of this List. That seems to be working perfectly.

Whenever I use this removal function on the first element, it crashes:

int TaskRemove(Task h,int IDREMOVE)                                                                                         {
    int val;
    for(;h;h=h->next)
    {
        if (h->ID==IDREMOVE)
        {
            h->previous->next = h->next;
            val++;
            if (h->previous->previous==NULL)
            {
                h->previous->next = h->next;
            }
        }
    }
    if (val==0)
    {
        printf("\n\tNo node with such ID\n");
        sleep(1);
    }
    return val;
}

This works on every element but the last. What's happening? Thanks in advance.

OT: typedef struct Inode2*Task; oh, don't typedef pointers. Especially not to a strange name like Task. Your code will be unreadable for others and - probably - also yourself — 4386427
– 4386427, Commented May 21, 2018 at 10:50
Your first bug (due to type def of pointer) is here: Task aux=(Task)malloc(sizeof(Task));. Should be (at least) Task aux=malloc(sizeof(struct Inode2)); but better would be: Task_node2* aux=malloc(sizeof *aux); — 4386427
– 4386427, Commented May 21, 2018 at 10:52

Sergey Kalinichenko · Accepted Answer · 2018-05-21 10:53:25Z

1

The problem is that your code accesses a two-away node without checking if the corresponding one-away node exists. Deleting the last node in the list will give you a similar problem.

You need to NULL-check each pointer before applying -> operator to it. Specifically, the code that checks h->previous->previous == NULL needs to first make sure that h->previous is not NULL. You need to add NULL checking of the first pointer in all places where you do a two-away check or assignment.

Note: Your code has other issues, for example, malloc(sizeof(Task)) yields memory of incorrect size. The root case of the confusion is that Task is a pointer type, but it is used without an asterisk. You should avoid this situation if possible by using Inode2* directly or by renaming Inode2 to Task for better readability.

answered May 21, 2018 at 10:53

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

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

Comments

Community · Accepted Answer · 2020-06-20 09:12:55Z

First issue with your code is how you allocate memory for a node.

Task aux=(Task)malloc(sizeof(Task));

This line allocates sizeof(Task) bytes of memory. Task is a pointer, not the actual node. Depending on the compiler, it most likely will allocate just enough space for a pointer. You should use the following to allocate space for Inode2:

Task aux=(Task)malloc(sizeof(struct Inode2));

The second issue is in these lines:

h->previous->next = h->next;
val++;
if (h->previous->previous==NULL)
{
    h->previous->next = h->next;
}

For the first element, h->previous should be NULL, so when you try to access h->previous->next, the program is trying to access a NULL pointer, which causes the crash. You have to check if h->previous is NULL or not before trying to access further.

Notes:

As mentioned in a comment, do NOT typedef pointers.
You said it crashes on the first element, then said it works on every element but the last. I'm assuming the former.

Collectives™ on Stack Overflow

C - Deleting any node from a doubly linked list

2 Answers 2

Comments

Notes:

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Notes:

Comments

Your Answer

Sign up or log in

Post as a guest

Related