Adding and removing from double linked list

Question

I have this structure

typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

typedef struct head
{
    unsigned int length;
    struct node  *first;
    struct node *last;
}HEAD;


STATUS addNode(HEAD *head, NODE *newNode, int loc)
{
int i;
STATUS ret = SUCCESS;

NODE *curPtr;

if(head && newNode && loc && (loc <= (head->length)+1))
{
    if(loc == 1)
    {
        newNode->prev = NULL;
        newNode->next = head->first;

        if(head->first)
            head->first = newNode;
    }
    else
    {
        curPtr = head->first;

        for(i=1; i<(loc-1); i++){
            curPtr = curPtr->next;
        }

        newNode->prev = curPtr;
        newNode->next = curPtr->next;

        if(curPtr->next){
            curPtr->next->prev = newNode;
        }
        curPtr->next = newNode;

    }

    head->length++;
}
else
    ret = FAILURE;

return ret;
}



STATUS removeNode(HEAD *head,NODE *nodeToRemove)
{
    STATUS ret = SUCCESS;

    NODE *curPtr;

    if(head && head->first)
    {
        curPtr = nodeToRemove->prev;
        curPtr->next = nodeToRemove->next;
        if(!(curPtr->next)){
            curPtr->next = head->first;
        }
        head->length--;
    }
    else
        ret = FAILURE;

    return ret;
}

I know I am not calling free(node) in remove from list, this call is made somewhere else

my problem is, that sometimes on the line newNode->next = curPtr->next; in the add node it falls for segmentation fault

can you please tell me the reason that it might happen ?

If `loc == 1`, what does the old first nodes `prev` pointer points to? And if the list is empty, why don't you add the node at all? — Some programmer dude, Jan 11 '15 at 20:02
As for your segmentation fault, what if you want to add the new node last? I.e. when `curPtr` is `NULL`? — Some programmer dude, Jan 11 '15 at 20:05
And lastly, what happens if you provide a `loc` larger than there are nodes in the list? — Some programmer dude, Jan 11 '15 at 20:05
first question - should point to the tail, 2nd question add it to the tail, 3rd question circle the list round a few times, until you consume the location — Lena Bru, Jan 11 '15 at 20:30

Some programmer dude · Answer 1 · 2015-01-12T08:21:12.487

Okay, lets start with the first of my comments: What happens when you call the addNode function with loc == 1: You initialize the new node, so it's next pointer points to the old head of the list, and the prev pointer points to NULL. This is all well and good, but then your problem starts. You only add the new node to the list if the list is not empty. You also do not change the previous head-nodes prev pointer.

That means that if the list is empty (i.e. when head->first is NULL) then you will not add the node, and the list will continue to be empty. If the list is not empty then you have a double-linked list where you can only go one way (from the (new) first node to the (new) second node, you can't go the opposite direction since you don't have a link set up that way.

Now for the second and third of my comments: The loop when loc != 1. First of all it will not run at all if loc == 0, meaning it will add to the head (which is what you attempt to do when loc == 1). This will not work if the list is empty, as curPtr will then be NULL and you will have undefined behavior when you dereference that pointer.

Secondly, lets assume you have managed to add some nodes to the list, and you pass a value larger than the number of nodes plus one in the list as loc (i.e. if you have one node, and you pass a value larger than 2, or you have five nodes and pass a value larger than 6), then the loop will iterate once to many, leaving you with curPtr being NULL. You don't check for that anywhere, which means you will sooner or later (in the loop or after) try to dereference a NULL pointer which leads to undefined behavior.

Undefined behavior is the most common reason for crashes such as the one you have. And next time you have a crash, the first thing you should do is to use a debugger and run your program in it. The debugger will stop at the location of the crash, letting you examine the function call stack, as well as walk up the call stack. You will also be able to examine values of variables at each level of the call stack (if the debugger have information for that level). You should also try to step through the code, line by line, in the debugger for different scenarios to see that what you intend to happen actually happens If you're still stumped, then you can come to SO and post a question about it. Next to the compiler, a debugger is the best tool for a programmer. Oh, ad speaking of compilers, always build with as many warnings enabled as possible, as compilers are pretty good at detecting things that are suspect and that might lead to UB (undefined behavior).

score 0 · Answer 2 · edited May 23 '17 at 10:25

Its possible that the curptr->next is not assigned to anything which won't necessarily make it point to NULL and hence you can run into segmentation faults at runtime. Make sure when you build your list, all your pointers in the NODE get initialized to NULL before any assignment/operation on them.

See this: C: Why do unassigned pointers point to unpredictable memory and NOT point to NULL?

and this: Why am I getting a segmentation fault?

Adding and removing from double linked list

2 Answers2